为什么在Python3.x中，整数的2*x*x比2*(x*x)快？

Question

以下Python3.x整数乘法的平均运算时间在1.66s到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))

如果将2*x*x替换为2*(x*x)，则需要在2.04和2.25之间。怎么会呢？

另一方面，在Java中则相反:2*(x*x)在Java中更快。Java测试链接：为什么在Java中2*(i*i)比2*i*i快？

我运行每个版本的程序10次，以下是结果。

   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

Answer 1

首先,请注意,我们在Python2.x中没有看到相同的东西：

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

所以这让我们相信这是由于整数在Python 3中的变化：具体地说，Python 3到处使用long（任意大的整数）。

对于足够小的整数（包括我们在这里考虑的整数），CPython实际上只使用O(MN)grade-school逐位数乘法算法（对于较大的整数，它切换到Karatsuba算法）。你可以在源代码中看到这一点。

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

再次将其与Python2进行比较,Python2不会到处使用任意长度的整数：

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

（一个有趣的注意：如果您查看源代码，您会发现该算法实际上有一个平方数的特例（我们在这里正在做），但即使这样也不足以克服2*(x*x)只需要处理更多数字的事实。）