Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #61174 > unrolled thread

Does Python optimize low-power functions?

Back to article view | Back to comp.lang.python

Contents

  Does Python optimize low-power functions? John Ladasky <john_ladasky@sbcglobal.net> - 2013-12-06 10:16 -0800
    Re: Does Python optimize low-power functions? Neil Cerutti <neilc@norwich.edu> - 2013-12-06 19:01 +0000
    Re: Does Python optimize low-power functions? Robert Kern <robert.kern@gmail.com> - 2013-12-06 19:12 +0000
    RE: Does Python optimize low-power functions? Nick Cash <nick.cash@npcinternational.com> - 2013-12-06 19:32 +0000
      Re: Does Python optimize low-power functions? John Ladasky <john_ladasky@sbcglobal.net> - 2013-12-06 11:43 -0800
    Re: Does Python optimize low-power functions? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-12-06 20:57 +0000
    Re: Does Python optimize low-power functions? Michael Torrie <torriem@gmail.com> - 2013-12-07 19:00 -0700

#61174 — Does Python optimize low-power functions?

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?

[toc] | [next] | [standalone]

#61177

On 2013-12-06, John Ladasky <john_ladasky@sbcglobal.net> 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

[toc] | [prev] | [next] | [standalone]

#61178

On 2013-12-06 19:01, Neil Cerutti wrote:
> On 2013-12-06, John Ladasky <john_ladasky@sbcglobal.net> 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

[toc] | [prev] | [next] | [standalone]

#61179

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

[toc] | [prev] | [next] | [standalone]

#61181

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.

[toc] | [prev] | [next] | [standalone]

#61182

On 6 December 2013 18:16, John Ladasky <john_ladasky@sbcglobal.net> 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?

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

[toc] | [prev] | [next] | [standalone]

#61268

On 12/06/2013 12:32 PM, Nick Cash wrote:
> 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.
>>>> 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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web