为什么删除else会减慢我的代码？

Question

考虑以下功能:

def fact1(n):
    if n < 2:
        return 1
    else:
        return n * fact1(n-1)

def fact2(n):
    if n < 2:
        return 1
    return n * fact2(n-1)

它们应该是等价的.但是有一个性能差异:

>>> T(lambda : fact1(1)).repeat(number=10000000)
[2.5754408836364746, 2.5710129737854004, 2.5678811073303223]
>>> T(lambda : fact2(1)).repeat(number=10000000)
[2.8432059288024902, 2.834425926208496, 2.8364310264587402]

没有的版本else慢了10%.这非常重要.为什么？

Answer 1

对我来说,它们的速度几乎相同:( Debian上的Python 2.6.6)

In [4]: %timeit fact1(1)
10000000 loops, best of 3: 151 ns per loop

In [5]: %timeit fact2(1)
10000000 loops, best of 3: 154 ns per loop

字节码也非常相似:

In [6]: dis.dis(fact1)
  2           0 LOAD_FAST                0 (n)
              3 LOAD_CONST               1 (2)
              6 COMPARE_OP               0 (<)
              9 JUMP_IF_FALSE            5 (to 17)
             12 POP_TOP             

  3          13 LOAD_CONST               2 (1)
             16 RETURN_VALUE        
        >>   17 POP_TOP             

  5          18 LOAD_FAST                0 (n)
             21 LOAD_GLOBAL              0 (fact)
             24 LOAD_FAST                0 (n)
             27 LOAD_CONST               2 (1)
             30 BINARY_SUBTRACT     
             31 CALL_FUNCTION            1
             34 BINARY_MULTIPLY     
             35 RETURN_VALUE        
             36 LOAD_CONST               0 (None)
             39 RETURN_VALUE        

In [7]: dis.dis(fact2)
  2           0 LOAD_FAST                0 (n)
              3 LOAD_CONST               1 (2)
              6 COMPARE_OP               0 (<)
              9 JUMP_IF_FALSE            5 (to 17)
             12 POP_TOP             

  3          13 LOAD_CONST               2 (1)
             16 RETURN_VALUE        
        >>   17 POP_TOP             

  4          18 LOAD_FAST                0 (n)
             21 LOAD_GLOBAL              0 (fact)
             24 LOAD_FAST                0 (n)
             27 LOAD_CONST               2 (1)
             30 BINARY_SUBTRACT     
             31 CALL_FUNCTION            1
             34 BINARY_MULTIPLY     
             35 RETURN_VALUE        

唯一的区别是带有else包含代码的版本None控件到达函数体的末尾.

Answer 2

这里发生的事情是在模块全局变量中fact2存在哈希冲突__name__.这使得全局的查找fact2变得如此轻微.

>>> [(k, hash(k) % 32) for k in globals().keys() ]
[('__builtins__', 8), ('__package__', 15), ('fact2', 25), ('__name__', 25), ('fact1', 26), ('__doc__', 29)]

即为什么早期回归比其他人慢？除了存在哈希冲突之外__builtins__

Answer 3

我质问时间.这两个函数没有递归到它们自己. fact1和fact2都调用了未显示的事实.

一旦修复,反汇编(在Py2.6和Py2.7中)显示两者都运行相同的操作码,除了递归到函数的名称.名称的选择会触发时间上的小差异,因为fact1可能会在模块字典中插入而没有名称冲突,而*fact2)可能具有与模块中的另一个名称冲突的哈希值.

换句话说,你在时间上看到的任何差异都不是由于选择是否存在else子句:-)