Does Python optimize low-power functions?

[John Ladasky]

The following two functions return the same result:

x**2
x*x

But they may be computed in different ways. The first choice can accommodate non-integer powers and so it would logically proceed by taking a logarithm, multiplying by the power (in this case, 2), and then taking the anti-logarithm. But for a trivial value for the power like 2, this is clearly a wasteful choice. Just multiply x by itself, and skip the expensive log and anti-log steps.

My question is, what do Python interpreters do with power operators where the power is a small constant, like 2? Do they know to take the shortcut?

 

[Neil Cerutti]

The following two functions return the same result:

x**2
x*x

But they may be computed in different ways. The first choice
can accommodate non-integer powers and so it would logically
proceed by taking a logarithm, multiplying by the power (in
this case, 2), and then taking the anti-logarithm. But for a
trivial value for the power like 2, this is clearly a wasteful
choice. Just multiply x by itself, and skip the expensive log
and anti-log steps.

My question is, what do Python interpreters do with power
operators where the power is a small constant, like 2? Do they
know to take the shortcut?

It uses a couple of fast algorithms for computing powers. Here's
the excerpt with the comments identifying the algorithms used.

From longobject.c:

2873 if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
2874 /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
2875 /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */
....
2886 else {
2887 /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */

The only outright optimization of the style I think your
describing that I can see is it quickly returns zero when modulus
is one.

I'm not a skilled or experienced CPython source reader, though.

 

[Robert Kern]

It uses a couple of fast algorithms for computing powers. Here's
the excerpt with the comments identifying the algorithms used.
From longobject.c:

2873 if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
2874 /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
2875 /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */
...
2886 else {
2887 /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */

It's worth noting that the *interpreter* per se is not doing this. The
implementation of the `long` object does this in its implementation of the
`__pow__` method, which the interpreter invokes. Other objects may implement
this differently and use whatever optimizations they like. They may even (ab)use
the syntax for things other than numerical exponentiation where `x**2` is not
equivalent to `x*x`. Since objects are free to do so, the interpreter itself
cannot choose to optimize that exponentiation down to multiplication.

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco

 

[Nick Cash]

My question is, what do Python interpreters do with power operators where the power is a small constant, like 2? Do they know to take the shortcut?

Nope:

Python 3.3.0 (default, Sep 25 2013, 19:28:08)
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.1 0 LOAD_FAST 0 (x)
3 LOAD_FAST 0 (x)
6 BINARY_MULTIPLY
7 RETURN_VALUE 1 0 LOAD_FAST 0 (x)
3 LOAD_CONST 1 (2)
6 BINARY_POWER
7 RETURN_VALUE


The reasons why have already been answered, I just wanted to point out thatPython makes it extremely easy to check these sorts of things for yourself..

 

[John Ladasky]

The reasons why have already been answered, I just wanted to point out that Python makes it extremely easy to check these sorts of things for yourself.

Thanks for the heads-up on the dis module, Nick. I haven't played with that one yet.

 

[Oscar Benjamin]

The following two functions return the same result:

x**2
x*x

But they may be computed in different ways. The first choice can accommodate non-integer powers and so it would logically proceed by taking a logarithm, multiplying by the power (in this case, 2), and then taking the anti-logarithm. But for a trivial value for the power like 2, this is clearly awasteful choice. Just multiply x by itself, and skip the expensive log and anti-log steps.

My question is, what do Python interpreters do with power operators wherethe power is a small constant, like 2? Do they know to take the shortcut?

As mentioned this will depend on the interpreter and on the type of x.
Python's integer arithmetic is exact and unbounded so switching to
floating point and using approximate logarithms is a no go if x is an
int object.

For CPython specifically, you can see here:
http://hg.python.org/cpython/file/07ef52e751f3/Objects/floatobject.c#l741
that for floats x**2 will be equivalent to x**2.0 and will be handled
by the pow function from the underlying C math library. If you read
the comments around that line you'll see that different inconsistent
math libraries can do things very differently leading to all kinds of
different problems.

For CPython if x is an int (long) then as mentioned before it is
handled by the HAC algorithm:
http://hg.python.org/cpython/file/07ef52e751f3/Objects/longobject.c#l3934

For CPython if x is a complex then it is handled roughly as you say:
for x**n if n is between -100 and 100 then multiplication is performed
using the "bit-mask exponentiation" algorithm. Otherwise it is
computed by converting to polar exponential form and using logs (see
also the two functions above this one):
http://hg.python.org/cpython/file/07ef52e751f3/Objects/complexobject.c#l151


Oscar

 

[Michael Torrie]

Nope:

Python 3.3.0 (default, Sep 25 2013, 19:28:08)
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.1 0 LOAD_FAST 0 (x)
3 LOAD_FAST 0 (x)
6 BINARY_MULTIPLY
7 RETURN_VALUE1 0 LOAD_FAST 0 (x)
3 LOAD_CONST 1 (2)
6 BINARY_POWER
7 RETURN_VALUE


The reasons why have already been answered, I just wanted to point
out that Python makes it extremely easy to check these sorts of
things for yourself.

But this is just the interpreter bytecode that dis is showing. It's not
showing the underlying implementation of binary_power, for example.
That could be defined in C code with any number of optimizations, and
indeed it appears that some are being done. dis is great for showing
how python code breaks down, but it can't tell you much about the code
that underlies the byte codes themselves.