Velocity Reviews > Does Python optimize low-power functions?

# Does Python optimize low-power functions?

John Ladasky
Guest
Posts: n/a

 12-06-2013
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
Guest
Posts: n/a

 12-06-2013
On 2013-12-06, John Ladasky <(E-Mail Removed)> wrote:
> 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.

--
Neil Cerutti

Robert Kern
Guest
Posts: n/a

 12-06-2013
On 2013-12-06 19:01, Neil Cerutti wrote:
> On 2013-12-06, John Ladasky <(E-Mail Removed)> wrote:
>> 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) */

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
Guest
Posts: n/a

 12-06-2013
>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:0
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import dis
>>> dis.dis(lambda x: x*x)

1 0 LOAD_FAST 0 (x)
3 LOAD_FAST 0 (x)
6 BINARY_MULTIPLY
7 RETURN_VALUE
>>> dis.dis(lambda x: x**2)

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
Guest
Posts: n/a

 12-06-2013
On Friday, December 6, 2013 11:32:00 AM UTC-8, Nick Cash wrote:

> 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
Guest
Posts: n/a

 12-06-2013
On 6 December 2013 18:16, John Ladasky <(E-Mail Removed)> wrote:
> 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/07...tobject.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/07...object.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/07...xobject.c#l151

Oscar

Michael Torrie
Guest
Posts: n/a

 12-08-2013
On 12/06/2013 12:32 PM, Nick Cash wrote:
> Nope:
>
> Python 3.3.0 (default, Sep 25 2013, 19:28:0
> [GCC 4.7.2] on linux2
> Type "help", "copyright", "credits" or "license" for more information.
>>>> import dis
>>>> dis.dis(lambda x: x*x)

> 1 0 LOAD_FAST 0 (x)
> 3 LOAD_FAST 0 (x)
> 6 BINARY_MULTIPLY
> 7 RETURN_VALUE
>>>> dis.dis(lambda x: x**2)

> 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 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.

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Elmar C Programming 14 03-25-2010 12:03 AM zyraco C++ 0 11-10-2009 01:44 PM zyraco C++ 0 11-10-2009 01:44 PM zyraco C++ 0 11-10-2009 01:44 PM ruxandra C++ 0 04-14-2009 07:00 PM

Advertisments