为什么 2 * x * x 在 Python 3.x 中比 2 * ( x * x ) 对于整数快？

Question

下面的Python 3.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 测试 link:

我运行每个版本的程序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

如果您的基准测试是正确的（未检查），则可能是因为 Python 整数可能是两种不同的东西：较小的本机整数（具有快速计算），以及大整数时它们的大小增加（计算速度较慢）。第一种语法在第一次操作后保持较小的大小，而第二种语法可能导致涉及大整数的两次操作。

Answer 2

Python 整数的 intern 表示是特殊的，它使用 30 位的槽：

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

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

所以一切都发生了，就好像 Python 以 B = 2**30 = 1 073 741 824 ~1 billion 为底。

对于想要计算 2*4*4 的人，有两种方法：

(2*4)*4 = 8*4 =32 = 30 + 2 如果您知道您的添加表，则立即计算。
2*(4*4) = 2*16 = 2*10 + 2*6 = (2*10+10) + 2 = 30 + 2 因为我们要放下运算。

Python有同样的问题。如果 x 是一个数字，例如 2x < B < x² ，让 x² = aB+b 和 a,b <B。 x² 存储在 2 个插槽中，我注意到 (a|b)。计算结果（此处不管理进位）：

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

在第一种情况下，2* 操作执行了两次，而在第一种情况下只执行了一次。这就解释了差异。

Answer 3

首先，请注意我们在 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

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

对于足够小的整数（包括我们在这里考虑的整数），CPython 实际上只使用 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.

x*x的位数大约是2*x或x的两倍（因为log(x²) = 2日志（x））。请注意，此上下文中的 "digit" 不是以 10 为底的数字，而是 30 位值（在 CPython 的实现中被视为单个数字）。因此，2 是一位数，x 和 2*x 是循环所有迭代的一位数，但 x*x 是两位数 x >= 2**15。因此，对于 x >= 2**15，2*x*x 只需要一位乘一位数，而 2*(x*x) 需要一位乘一位和一位乘两位数（因为 x*x 有 2 个 30 位数字）。

这是查看此内容的直接方法 (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

再次将其与 Python 2 进行比较，后者并未在任何地方使用任意长度的整数：

>>> 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) 只需要处理更多数字。）

Answer 4

据我所知，归结为使用 2 * (x * x) 的版本中的内存访问多了一点。我打印了反汇编的字节码，它似乎证明了：

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

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

为什么 2 * x * x 在 Python 3.x 中比 2 * ( x * x ) 对于整数快？

Why is 2 * x * x faster than 2 * ( x * x ) in Python 3.x, for integers?

python

performance

benchmarking

python-3.x

integer-arithmetic