42

The following Python 3.x integer multiplication takes on average between 1.66s and 1.77s:

import time
start_time = time.time()
num = 0
for x in range(0, 10000000):
    # num += 2 * (x * x)
    num += 2 * x * x
print("--- %s seconds ---" % (time.time() - start_time))

if I replace 2 * x * x with 2 *(x * x), it takes between 2.04 and 2.25. How come?

On the other hand it is the opposite in Java: 2 * (x * x) is faster in Java. Java test link: Why is 2 * (i * i) faster than 2 * i * i in Java?

I ran each version of the program 10 times, here are the results.

   2 * x * x        |   2 * (x * x)
---------------------------------------
1.7717654705047607  | 2.0789272785186768
1.735931396484375   | 2.1166207790374756
1.7093875408172607  | 2.024367570877075
1.7004504203796387  | 2.047525405883789
1.6676218509674072  | 2.254328966140747
1.699510097503662   | 2.0949244499206543
1.6889283657073975  | 2.0841963291168213
1.7243537902832031  | 2.1290600299835205
1.712965488433838   | 2.1942825317382812
1.7622807025909424  | 2.1200053691864014
smci
  • 32,567
  • 20
  • 113
  • 146
Waqas Gondal
  • 467
  • 6
  • 15
  • 15
    Little hint: Use the `timeit` module for better statistics – user8408080 Dec 01 '18 at 12:43
  • For good measure you might as well throw in `2 * pow(x,2)` and `2 * x**2` as well. Also, please redo your timings using [`timeit`](https://docs.python.org/3/library/timeit.html), it's much more accurate than `time.time()` for short processes. – smci Dec 02 '18 at 01:16
  • Related near-duplicate, although not very clearly-stated: [Times-two faster than bit-shift, for Python 3.x integers?](https://stackoverflow.com/questions/37053379/times-two-faster-than-bit-shift-for-python-3-x-integers) – smci Dec 02 '18 at 01:31

4 Answers4

30

First of all, note that we don't see the same thing in Python 2.x:

>>> timeit("for i in range(1000): 2*i*i")
51.00784397125244
>>> timeit("for i in range(1000): 2*(i*i)")
50.48330092430115

So this leads us to believe that this is due to how integers changed in Python 3: specifically, Python 3 uses long (arbitrarily large integers) everywhere.

For small enough integers (including the ones we're considering here), CPython actually just uses the O(MN) grade-school digit by digit multiplication algorithm (for larger integers it switches to the Karatsuba algorithm). You can see this yourself in the source.

The number of digits in x*x is roughly twice that of 2*x or x (since log(x2) = 2 log(x)). Note that a "digit" in this context is not a base-10 digit, but a 30-bit value (which are treated as single digits in CPython's implementation). Hence, 2 is a single-digit value, and x and 2*x are single-digit values for all iterations of the loop, but x*x is two-digit for x >= 2**15. Hence, for x >= 2**15, 2*x*x only requires single-by-single-digit multiplications whereas 2*(x*x) requires a single-by-single and a single-by-double-digit multiplication (since x*x has 2 30-bit digits).

Here's a direct way to see this (Python 3):

>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
5.796971936999967
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
4.3559221399999615

Again, compare this to Python 2, which doesn't use arbitrary-length integers everywhere:

>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
3.0912468433380127
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
3.1120400428771973

(One interesting note: If you look at the source, you'll see that the algorithm actually has a special case for squaring numbers (which we're doing here), but even still this is not enough to overcome the fact that 2*(x*x) just requires processing more digits.)

user2357112
  • 260,549
  • 28
  • 431
  • 505
arshajii
  • 127,459
  • 24
  • 238
  • 287
  • Is Karatsuba algorithm slower than digit multiplication algorithm? – Banghua Zhao Dec 01 '18 at 14:11
  • 1
    @BanghuaZhao It has a better runtime complexity (wrt to number of digits), but the number of digits has to be large enough for it to actually be worth it. – arshajii Dec 01 '18 at 14:13
  • 2
    source : #define KARATSUBA_CUTOFF 70 . So the Karatsuba algorithm is only used if ints have about 600 decimal digits. it is not the problem here. – B. M. Dec 01 '18 at 17:35
  • 2
    In Python, a "digit" is a 30 or 60-bit chunk, right? So base `2^30`, not a *decimal* digit. Also critically important: Java `int` wraps at 2^32, while Python does arbitrary precision. Plus Java JIT-compiles to (inefficient) native code using 32-bit registers, while CPython interprets all the way. So those are massive differences. – Peter Cordes Dec 01 '18 at 18:15
  • @B.M. The point seems to be that Karatsuba is *not* being used, right? So it appears this argument could be tested by checking performance when x is larger than 70 digits long. If the difference is smaller, that suggests this is correct. (Or have I misunderstood?) – senderle Dec 01 '18 at 18:47
  • 2
    The numbers involved in the question are small enough that Karatsuba is not involved, and beyond that, they are small enough that asymptotic considerations are completely irrelevant. All operands and results involved fit in two 30-bit internal "digits". – user2357112 Dec 01 '18 at 19:30
  • @user2357112 The point is that `2*x*x` only requires multiplying 1-digit numbers whereas `2*(x*x)` requires a 2-digit multiplication. The Karatsuba mention was just a side note, not at all relevant to the answer. – arshajii Dec 01 '18 at 19:50
  • @PeterCordes Yes that's right. I just noted that in the answer as well. – arshajii Dec 01 '18 at 19:56
  • Just been looking at the source and found that Python2 special cases "small integer ops" and this was dropped in Python3 as it only seemed to affect micro-benchmarks and have little effect on real-world performance. see: https://bugs.python.org/issue21955 and https://github.com/python/cpython/blob/ec13b9322d95a651606219469fc7b7e9c977f248/Python/ceval.c#L1277 – Sam Mason Dec 02 '18 at 18:39
8

Python intern representation of integers is special, it uses slots of 30 bits :

In [6]: sys.getsizeof(2**30-1)
Out[6]: 28 # one slot + heading

In [7]: sys.getsizeof(2**30)
Out[7]: 32 # two slots

So everything happens as if Python counts in base B = 2**30 = 1 073 741 824 ~1 billion.

For a human who want to calculate 2*4*4, two ways :

  • (2*4)*4 = 8*4 =32 = 30 + 2 is immediate if you knows your add tables.
  • 2*(4*4) = 2*16 = 2*10 + 2*6 = (2*10+10) + 2 = 30 + 2 since we have to put the operation down.

Python have the same problem. If x is a number such than 2x < B < x² , let x² = aB+b , with a,b <B. x² is stored in 2 slots, which I note (a|b). Computations leads to (without managing carries here):

   (x*x)*2 =>  (a|b)*2 => (2*a|2*b)
   (2*x)*x =>  (2x)*x =>(2a|2b)

in the first case the 2* operation is done two times, against only one in the first case. That explains the difference.

B. M.
  • 18,243
  • 2
  • 35
  • 54
  • 3
    Where do `a`, `b` and `X` come from, what do they represent and how do they relate to the value of `x`? – Bergi Dec 01 '18 at 15:55
  • @Bergi: `a` and `b` are the high and low 30-bit chunks of `x*x`. (Capital `X` no longer appears in the current revision of the answer.) – user2357112 Dec 01 '18 at 19:36
4

If your benchmark is right (didn't check), it may come from the fact that Python integers may be two different things : native integers when they are small (with a quick computation), and big integers when they increase in size (slower computation). The first syntax keeps the size smaller after the first operation while the second syntax may lead to two operations involving big integers.

Thomas Baruchel
  • 7,236
  • 2
  • 27
  • 46
  • 11
    Seems more like a guess (albeit a good guess) than an answer. Using `timeit` with different size `x` might give the needed evidence to push it from a guess to an answer. – John Coleman Dec 01 '18 at 13:00
  • python has "cached" integers for -5 to 256 [Dok](https://docs.python.org/3.6/c-api/long.html#c.PyLong_FromLong) - this would be easily veryfied if both formulas are closer to the same times if only small integers are in play? The max value goes to 2e+14 which is small enough to fit a 64-bit signed int so processor int calculation limitations is probably out of the game - it is too big for 32-bit unsigned int, so on 32-bit this might factor in? – Patrick Artner Dec 01 '18 at 13:12
  • 4
    I still [measure a 5% difference](https://gist.github.com/vxgmichel/6fd2d13590eb5c9ef74ac764fea4444b) using 2 as a value for x. – Vincent Dec 01 '18 at 13:13
  • 2
    The answer might seem more like a guess, though in my eyes it is helpful because I just learned something more about Python. – Ely Dec 01 '18 at 13:47
2

From what I can tell, it comes down to a little bit more memory access in the version using 2 * (x * x). I printed the disassembled bytecode and it seems to prove that:

Relevant part of 2 * x * x:

7          28 LOAD_FAST                1 (num)
           30 LOAD_CONST               3 (2)
           32 LOAD_FAST                2 (x)
           34 BINARY_MULTIPLY
           36 LOAD_FAST                2 (x)
           38 BINARY_MULTIPLY
           40 INPLACE_ADD
           42 STORE_FAST               1 (num)
           44 JUMP_ABSOLUTE           24

Relevant part of 2 * (x * x):

  7          28 LOAD_FAST                1 (num)
             30 LOAD_CONST               3 (2)
             32 LOAD_FAST                2 (x)
             34 LOAD_FAST                2 (x)
             36 BINARY_MULTIPLY                 <=== 1st multiply x*x in a temp value
             38 BINARY_MULTIPLY                 <=== then multiply result with 2
             40 INPLACE_ADD
             42 STORE_FAST               1 (num)
             44 JUMP_ABSOLUTE           24
Eric Fortin
  • 7,533
  • 2
  • 25
  • 33
  • If this was the case we'd see the same effect in Python 2, but we don't. – arshajii Dec 01 '18 at 14:22
  • 1
    it's just moved a `LOAD_FAST` one instruction later. how is this "more memory access"? – Sam Mason Dec 01 '18 at 14:42
  • @arshajii You are right, I checked the disassembled code for Python 2 and it shows the same thing. Although I still believe it might have an impact but is negligible compared to the one you noted. – Eric Fortin Dec 01 '18 at 14:43
  • @SamMason In the second case, it needs to write back the result of `x*x` in a temp value because it is needed for the next multiply whereas in the first case, it always writes in the same register. So the second case is a read after write. It is however a really small penalty but in a hot loop, it can have an impact. – Eric Fortin Dec 01 '18 at 14:52
  • CPython is a stack machine, it always leaves/writes results of computations to the top of the stack… there might be some cache related impact, but it's going to be incredibly small for code this close – Sam Mason Dec 01 '18 at 14:59