Why does 2*i*i tend to be faster than 2*(i*i) when i is integer?

Question

The two multiplications, 2*i*i and 2*(i*i), are equal and must generate the same result, what changes is only the order that the multiplications are made, but apparently are treated differently by the interpreter.

In the first multiplication, given the absence of parentheses and considering that all transactions have the same precedence, the interpreter will execute from left to right; that is, first will be done 2*i and the result multiplied by i.

In the second multiplication, given the presence of the parentheses, the order of execution is changed because the multiplication i*i takes precedence over multiplication by 2, so the interpreter will first make i*i and the result will multiply by 2.

Mathematically, the order of the factors does not change the product, so the result should be the same, but using the native package timeit it is possible to see a difference between the execution times between these multiplications:

>>> print('2*i*i:', timeit("for i in range(1000): 2*i*i"))
2*i*i: 276.91411599100684

>>> print('2*(i*i):', timeit("for i in range(1000): 2*(i*i)"))
2*(i*i): 279.21798045100877

^{Tests were done on Repl.it}

Note: important to stress that the function timeit will run, by default, 1,000,000 times the specified code snippet and that the exact execution time may vary due to processor and inter-computer oscillations.

Why is there this time difference? The presence of parentheses in the expression changes the executed algorithm?

Stressing that the analysis should be done in the official implementation of Python, Cpython, in version 3+. Comparisons with other versions or implementations will be welcome as a way to increase the response.

Answer 1

"You already know, but it doesn’t hurt to repeat" if you think you need optimizations at this level in a chunk of Python code, you are writing this chunk of code in the language wrong (or any other very high-level language such as ruby, php, and even Java).

Now there are some things you can answer in your question, and speculate a little, even without arriving at a definitive answer.

First - when you want to know differences of this type in Python, it is worth looking at which bytecode was generated for each snippet of code. Comparing the bytecode is easier to speculate what the differences may be. In Python, the function dis of the module of the same name allows to see the bytecode:

In [54]: def a(): 
    ...:     return 2 * i * i 
    ...:                                                                                                 

In [55]: def b(): 
    ...:     return 2 * (i * i) 
    ...:                                                                                                 

In [56]: import dis                                                                                      

In [57]: dis.dis(a)                                                                                      
  2           0 LOAD_CONST               1 (2)
              2 LOAD_GLOBAL              0 (i)
              4 BINARY_MULTIPLY
              6 LOAD_GLOBAL              0 (i)
              8 BINARY_MULTIPLY
             10 RETURN_VALUE

In [58]: dis.dis(b)                                                                                      
  2           0 LOAD_CONST               1 (2)
              2 LOAD_GLOBAL              0 (i)
              4 LOAD_GLOBAL              0 (i)
              6 BINARY_MULTIPLY
              8 BINARY_MULTIPLY
             10 RETURN_VALUE

So as you can see, there is actually a small difference: In the first case, the bytecode switches to load the values to be multiplied on the Python virtual machine stack with the multiplication calls themselves. In the second case, it puts all the values on the virtual machine stack, and then calls the multiplication operator twice in a row. It may be that CPU microcode level optimizers can optimize this repeated call then the function that will be called by the opcode BINARY_MULTIPLY (for example, the following call can give more hits on the CPU’s Prediction branch).

Anyway, if it’s not exactly that, I would still bet my chips that what happens is exactly some level optimization of the CPU microcode that is activated in the second case.

Exactly the kind of thing you will rarely worry about even if you are coding in C, let alone in Python. And in that case, before you say "wow, let me use Inline Assembler," it would be the case to look for high-level solutions that could use the computer resources more appropriately - code that uses the GPU or CPU vector processing units for example, that would earn orders of magnitude greater than staying micro-optimizing a single operation. (And in the case of Python, the "first" remedy will always be to use Numpy) .

To remove the web if by chance it is nothing within the Pyton code even, just checking also the code that will be called for BINARY_MULTIPLY - which certainly has optimizations for when both operands are Python Integers, but not beyond that (for example, an extra optimization if one of the operators is '2' - anyway, Runtime has to call the code that is in int.__mul__ for this) - but I’m talking about optimizations that will be between the VM find the opcode and call the int.__mul__.

By the way, the difference really is so insignificant that other changes make things change - see what happens when I measure times for functions a and b above:

In [59]: i = 10                                                                                          

In [60]: %timeit a()                                                                                     
119 ns ± 1.71 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

In [61]: %timeit b()                                                                                     
123 ns ± 0.725 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

That is, on this machine, the shape 2 * i * i is faster!