为什么在Python中减法比加法快?

38

我在优化一些 Python 代码,并尝试了以下实验:

import time

start = time.clock()
x = 0
for i in range(10000000):
    x += 1
end = time.clock()

print '+=',end-start

start = time.clock()
x = 0
for i in range(10000000):
    x -= -1
end = time.clock()

print '-=',end-start
第二个循环更可靠地更快,取决于我运行它的系统,速度从微不足道的到10%。我尝试了改变循环顺序、执行次数等方法,它似乎仍然有效。
陌生人,
for i in range(10000000, 0, -1):

(倒序运行循环)比

更快
for i in range(10000000):

即使循环内容相同,也会出现这种情况。有什么原因,这里还有更一般的编程教训吗?


4
你尝试过使用xrange()而不是range()吗?这样Python就不必为一千万个整数分配空间。另外,你是在运行Python 2.x还是Python 3.x版本?它们的range()实现方式有很大不同。 - Greg Hewgill
你能在频率可变的CPU上运行这段代码吗? - tzot
10个回答

89

我可以在我的 Q6600 (Python 2.6.2) 上复现这个问题;将范围增加到 100000000:

('+=', 11.370000000000001)
('-=', 10.769999999999998)
首先需要注意以下一些事项:
  • 对于一个微不足道的操作,这占用了5%的时间。 这是非常显著的。
  • 本地加减操作码的速度无关紧要。 它在噪声水平上,完全被字节码评估所掩盖。 这是指在数千个左右的本地指令中,只有一两个。
  • 字节码生成完全相同的指令数; 唯一的区别是INPLACE_ADD与INPLACE_SUBTRACT以及+1与-1。

查看Python源代码,我可以猜到。 这在ceval.c中处理,在PyEval_EvalFrameEx中。 INPLACE_ADD具有显着的额外代码块,用于处理字符串连接。 在INPLACE_SUBTRACT中不存在该块,因为您无法从字符串中减去。 这意味着INPLACE_ADD包含更多的本地代码。 根据编译器如何生成代码(非常重要!),此额外代码可能与其余的INPLACE_ADD代码内联,这意味着加法会比减法更加频繁地命中指令缓存。 这可能导致额外的L2缓存命中,从而导致显着的性能差异。

这在很大程度上取决于您所使用的系统(不同的处理器具有不同数量的缓存和缓存体系结构)、编译器,包括特定版本和编译选项(不同的编译器将以不同方式确定哪些代码位于关键路径上,这决定了汇编代码如何组合在一起)等等。

另外,在Python 3.0.1中,差异被颠倒(+:15.66,-:16.71); 毫无疑问,这个关键函数已经变化很多。


9
该回答真的很好,可惜没有被采纳 :( - mgiuca

13
$ python -m timeit -s "x=0" "x+=1"
10000000 loops, best of 3: 0.151 usec per loop
$ python -m timeit -s "x=0" "x-=-1"
10000000 loops, best of 3: 0.154 usec per loop

看起来你有一些 测量偏差


3
测量偏差的关键在于,你的一个反例并不能证明它是对还是错。所以我可能存在一些测量偏差! - Statto
你的输出稍微慢了一点.. ;) - Pod
1
在Windows Vista上使用Python 2.5.2,我像pixelbeat一样使用python -mtimeit进行测试,并发现在OP比较方面没有显著差异。(我得到的微小差异更快,但我确定在多次运行中也会看到相反的情况。) - Anon
在这种情况下,我认为加法更快,因为它“需要解释的字符少一个”。我知道这可能看起来没有用,但这是我的见解。 - LiraNuna
1
如果他的时间差与处理器缓存大小有关,使用更有效的计时系统--本质上命中较少本地代码的系统--将消除这种差异。(我没有一个好的指令/缓存分析工具来进行比较,但这才是 OP 真正需要比较的。)当然,您也可以拥有更多的 L1 缓存、一个做出更好猜测的编译器等系统。 - Glenn Maynard

8
我认为“通用编程课程”的教训是,仅通过查看源代码很难预测哪个语句序列会最快。各级程序员经常陷入这种“直觉”优化的困境。你所认为的可能不一定是正确的。
实际上,没有什么比实际测量程序性能更好的替代方法。赞扬你这样做;在这种情况下回答“为什么”无疑需要深入了解Python的实现。
对于像Java、Python和.NET这样的字节编译语言,仅在一台机器上测试性能是不足够的。VM版本之间的差异、本地代码转换实现、特定于CPU的优化等等将使这种问题变得更加棘手。

5
“第二个循环通常更快……”这就是你的解释。重新排列脚本,使减法测试首先计时,然后是加法,突然之间加法再次成为更快的操作。”
-= 3.05
+= 2.84

很明显,脚本的后半部分发生了一些让它运行更快的事情。我猜测第一次调用range()速度较慢是因为Python需要为如此长的列表分配足够的内存,但它能够重复利用那些内存以供第二次调用range()使用:

import time
start = time.clock()
x = range(10000000)
end = time.clock()
del x
print 'first range()',end-start
start = time.clock()
x = range(10000000)
end = time.clock()
print 'second range()',end-start

这个脚本的几次运行表明,第一个range()所需的额外时间几乎占据了上述'+='和'-='之间时间差的全部。
first range() 0.4
second range() 0.23

dtmunir的回答的复制品;OP已经说过,无论顺序如何,他都得到相同的结果。我已经重现了这个问题,以及当两个测试分别运行时,以及使用xrange而不是range时的情况。 - Glenn Maynard
@Glenn:我把“尝试改变循环顺序”解释为“使用range(10000000,0,-1)而不是range(10000000)”因为他随后详细说明了如何使用反向范围(reversed range())。他并没有明确说过他尝试将减法测试放在首位。dtmunir的回答也存在同样的模棱两可,这可能就是它被投票否决的原因。 - too much php
我不会“立即”详细介绍如何使用反向范围!我尝试先放置减法循环,也多次以各种顺序运行这两个测试。 - Statto

4

提问时,最好说明你使用的平台和Python版本。有时候这并不重要,但这不是这种情况:

  1. time.clock()仅适用于Windows。放弃自己的测量代码,使用-m timeit,如pixelbeat的答案所示。

  2. Python 2.X的range()会构建一个列表。如果您使用的是Python 2.x,请将range替换为xrange,看看会发生什么。

  3. Python 3.X的int相当于Python2.X的long


3
这里是否有更一般的编程经验教训?

更一般的编程经验教训是,直觉在预测计算机代码运行时性能方面是一个较差的指导。

人们可以推理算法复杂度,假设编译器优化,估计缓存性能等等。然而,由于这些因素可能以非平凡的方式相互作用,唯一确定特定代码片段的速度的方法是在目标环境中对其进行基准测试(正如您已经正确地做到了)。


0

那将是非常卓越的表现,因此我已经彻底评估了您的代码,并设置了实验,因为我认为更加“正确”(所有声明和函数调用都在循环外)。 我已经运行了五次两个版本。

  • 运行您的代码确认了您的说法: -= 始终需要更少的时间; 平均为3.6%
  • 然而,运行我的代码与您的实验结果相矛盾: += 平均需要更少的时间(并非总是)0.5%。

为了显示所有结果,我已将图形放在线上:

因此,我得出结论,您的实验存在偏见,并且这是显著的。

最后,这是我的代码:

import time

addtimes = [0.] * 100
subtracttimes = [0.] * 100

range100 = range(100)
range10000000 = range(10000000)

j = 0
i = 0
x = 0
start = 0.


for j in range100:
 start = time.clock()
 x = 0
 for i in range10000000:
  x += 1
 addtimes[j] = time.clock() - start

for j in range100:
 start = time.clock()
 x = 0
 for i in range10000000:
  x -= -1
 subtracttimes[j] = time.clock() - start

print '+=', sum(addtimes)
print '-=', sum(subtracttimes)

0

在Python 2.5中,最大的问题是使用range,它将分配一个如此巨大的列表来迭代。当使用xrange时,对我来说,无论哪个先完成都会稍微快一点。(不确定range在Python 3中是否已成为生成器。)


我在2.6.2中使用xrange进行测试,结果无论哪种操作先执行,-= 1对我来说始终比+= 1快。 - Glenn Maynard

0

你的实验有误。这个实验应该设计成编写两个不同的程序——一个用于加法,一个用于减法。它们应该完全相同,在相同的条件下运行,并将数据存入文件。然后,您需要对运行进行平均(至少数千次),但您需要一位统计学家告诉您适当的数量。

如果您想分析不同的加法、减法和循环方法,那么每个方法都应该是一个单独的程序。

实验误差可能来自处理器的热量和其他正在CPU上运行的活动,因此我会以各种模式执行运行...


他应该这样做,但这不是问题所在。我已经测试过两种方式,无论哪种方式,减法情况在2.6中始终更快。 - Glenn Maynard

-1

循环倒序运行更快,因为计算机在比较数字是否等于0时更容易。


1
虽然在优化的汇编语言中这可能是正确的,但通常情况下对于高级语言(如Python)来说并不正确,在任何情况下也不太可能产生像10%那样显著的差异。 - Greg Hewgill
这里没有对 x 值进行任何比较? - Pod
两个循环都没有倒着运行。它们都向上运行,一个加1,另一个减去-1。 - Glenn Maynard
@Glenn Maynard:我认为这个答案是指range(10000000, 0, -1)这部分。 - Greg Hewgill

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接