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

Question

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

pythonpython-3.xperformancebenchmarkinginteger-arithmetic

43

以下是 Python 3.x 的整数乘法，平均需要花费 1.66 秒到 1.77 秒：

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

- Waqas Gondal

16

小提示：使用 timeit 模块可以获得更好的统计数据。 - user8408080

为了保险起见，您也可以加入2 * pow(x,2)和2 * x**2。另外，请使用timeit重新计时，对于短进程来说，它比time.time()更准确。 - smci

相关的近似重复，虽然没有表述得很清楚：Python 3.x 整数的乘二速度比位移快吗？ - smci

4个回答

8

Python中整数的内部表示是特殊的，它使用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〜10亿中计数一样。

对于想要计算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*操作执行了两次，而在第二种情况下只执行了一次。这就解释了差异。

- B. M.

3

a、b和X分别代表什么，它们是从哪里来的，又如何与x的值相关联？ - Bergi

@Bergi：a和b是x*x的高30位和低30位块。（当前答案修订版中不再出现大写字母X。） - user2357112

4

如果您的基准测试正确（未经检查），那么这可能是因为Python整数可能是两种不同的类型：当它们很小时（进行快速计算）时，它们是本地整数，当它们增加大小时（进行较慢的计算）则是大整数。第一种语法在第一次操作后保持尺寸较小，而第二种语法可能会导致涉及大整数的两个操作。

- Thomas Baruchel

11

这似乎更像是猜测（尽管是一个好的猜测），而不是答案。使用 timeit 并使用不同大小的 x 可能会提供所需的证据，将其从猜测变为答案。 - John Coleman

Python对于-5到256之间的整数有“缓存”，详情请参见Dok。如果只涉及小整数，那么这一点很容易验证，因为两个公式的计算时间会非常接近。最大值为2e+14，足以适应64位有符号整数，因此处理器整数计算限制可能不是问题——它对于32位无符号整数来说太大了，所以在32位上可能会有影响？ - Patrick Artner

4

使用2作为x的值，我仍然测得5％的差异。 - Vincent

2

答案可能看起来更像是猜测，但在我看来它很有帮助，因为我刚刚学到了更多关于Python的知识。 - Ely

2

据我所知，使用 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

- Eric Fortin

如果是这种情况，我们会在Python 2中看到相同的效果，但我们没有看到。 - arshajii

1

它只是将LOAD_FAST指令向后移动了一个位置。这怎么会变成“更多的内存访问”呢？ - Sam Mason

@arshajii 你是对的，我检查了Python 2的反汇编代码，它显示了同样的结果。虽然我仍然相信它可能会产生影响，但与你指出的那个相比微不足道。 - Eric Fortin

@SamMason 在第二种情况下，需要将x*x的结果写回到一个临时值中，因为它在下一次乘法中需要使用，而在第一种情况下，它总是写入同一个寄存器。因此，第二种情况是一种读取后写入的操作。然而，这只是一个非常小的惩罚，在热循环中可能会产生影响。 - Eric Fortin

CPython是一种堆栈机，它总是将计算结果留在堆栈顶部/写入堆栈顶部...可能会有一些与缓存相关的影响，但对于这么接近的代码来说，影响将非常小。 - Sam Mason

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- arshajii · Accepted Answer

首先，需要注意的是在 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)小学竖式乘法算法（对于更大的整数，它会切换到Karatsuba算法）。您可以在源代码中自行查看。 x*x的数字位数大约是2*x或x的两倍（因为log(x²) = 2 log(x)）。请注意，这里的“数字”不是十进制数字，而是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)需要处理更多数字的事实。