Does Python optimize low-power functions?

Discussion in 'Python' started by John Ladasky, Dec 6, 2013.

  1. John Ladasky

    John Ladasky Guest

    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?
    John Ladasky, Dec 6, 2013
    #1
    1. Advertising

  2. John Ladasky

    Neil Cerutti Guest

    On 2013-12-06, John Ladasky <> 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
    Neil Cerutti, Dec 6, 2013
    #2
    1. Advertising

  3. John Ladasky

    Robert Kern Guest

    On 2013-12-06 19:01, Neil Cerutti wrote:
    > On 2013-12-06, John Ladasky <> 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
    Robert Kern, Dec 6, 2013
    #3
  4. John Ladasky

    Nick Cash Guest

    >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 thatPython makes it extremely easy to check these sorts of things for yourself..
    Nick Cash, Dec 6, 2013
    #4
  5. John Ladasky

    John Ladasky Guest

    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.
    John Ladasky, Dec 6, 2013
    #5
  6. On 6 December 2013 18:16, John Ladasky <> 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/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
    Oscar Benjamin, Dec 6, 2013
    #6
  7. 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.
    Michael Torrie, Dec 8, 2013
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.

Share This Page