[issue44376] Improve performance of integer exponentiation

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

Under the released 3.9.5 for 64-bit Win10, raising to the power 2 is clearly much slower than multiplying directly:

C:\Windows\System32>py -3 -m timeit -s "x=151" "x*x"
10000000 loops, best of 5: 30 nsec per loop

C:\Windows\System32>py -3 -m timeit -s "x=151" "x**2"
1000000 loops, best of 5: 194 nsec per loop

Since the multiplication itself is cheap, overheads must account for it. Offhand, looks to me like the `x**2` spelling is actually doing 31 multiplications under the covers, although most of them are as cheap as Python-int multiplies get.

        for (i = Py_SIZE(b) - 1; i >= 0; --i) {
            digit bi = b->ob_digit[i];

            for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 1) {
                MULT(z, z, z);
                if (bi & j)
                    MULT(z, a, z);
            }
        }

Python ints on a 64-bit box are stored internally in base 2**30 (PyLong_SHIFT is 30). z starts life at 1. The first 28 trips through the loop are chewing up the 28 leading zero bits in exponent 2, so MULT(z, z, z) multiplies 1 by 1 to get 1, 28 times. Then again on the 29th iteration, but now "bi & j" is finally true (we finally found the leading one bit in exponent 2), so z is replaced by 1 times the base = the base. On the final, 30th, iteration, MULT(z, z, z) replaces z with its square, and we're done.

It would probably be worthwhile to add code special-casing the leading Python "digit" of the exponent, fast-forwarding without any multiplies to the leading one bit, and setting z directly to the base then.

----------
nosy: +tim.peters

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue44376>
_______________________________________