为什么早退比其他方式慢？

Question

这是an answer I gave a few days back的后续问题。编辑：这个问题的操作似乎已经使用了我发给他的代码来询问the same question，但我对此一无所知。道歉。不过，提供的答案是不同的！

实质上，我注意到：

>>> def without_else(param=False):
...     if param:
...         return 1
...     return 0
>>> def with_else(param=False):
...     if param:
...         return 1
...     else:
...         return 0
>>> from timeit import Timer as T
>>> T(lambda : without_else()).repeat()
[0.3011460304260254, 0.2866089344024658, 0.2871549129486084]
>>> T(lambda : with_else()).repeat()
[0.27536892890930176, 0.2693932056427002, 0.27011704444885254]
>>> T(lambda : without_else(True)).repeat()
[0.3383951187133789, 0.32756996154785156, 0.3279120922088623]
>>> T(lambda : with_else(True)).repeat()
[0.3305950164794922, 0.32186388969421387, 0.3209099769592285]

……或者换句话说：不管是否触发了if条件，拥有else子句都更快。

我认为这与两个字节码产生的不同有关，但是有人能够详细地确认/解释吗？

编辑：似乎不是每个人都能复制我的计时，所以我想提供一些关于我的系统的信息可能会有用。我运行的是Ubuntu11.1064位，安装了默认的python。python生成以下版本信息：

Python 2.7.2+ (default, Oct  4 2011, 20:06:09) 
[GCC 4.6.1] on linux2

以下是Python2.7中反汇编的结果：

>>> dis.dis(without_else)
  2           0 LOAD_FAST                0 (param)
              3 POP_JUMP_IF_FALSE       10

  3           6 LOAD_CONST               1 (1)
              9 RETURN_VALUE        

  4     >>   10 LOAD_CONST               2 (0)
             13 RETURN_VALUE        
>>> dis.dis(with_else)
  2           0 LOAD_FAST                0 (param)
              3 POP_JUMP_IF_FALSE       10

  3           6 LOAD_CONST               1 (1)
              9 RETURN_VALUE        

  5     >>   10 LOAD_CONST               2 (0)
             13 RETURN_VALUE        
             14 LOAD_CONST               0 (None)
             17 RETURN_VALUE        

Answer 1

这是一个纯粹的猜测，我还没有找到一个简单的方法来检验它是否正确，但我有一个理论给你。

我尝试了您的代码，得到了相同的结果，without_else()重复地比with_else()稍慢：

>>> T(lambda : without_else()).repeat()
[0.42015745017874906, 0.3188967452567226, 0.31984281521812363]
>>> T(lambda : with_else()).repeat()
[0.36009842032996175, 0.28962249392031936, 0.2927151355828528]
>>> T(lambda : without_else(True)).repeat()
[0.31709728471076915, 0.3172671387005721, 0.3285821242644147]
>>> T(lambda : with_else(True)).repeat()
[0.30939889008243426, 0.3035132258429485, 0.3046679117038593]

考虑到字节码是相同的，唯一的区别是函数名。特别是计时测试对全局名称进行查找。尝试重命名without_else()，差异消失：

>>> def no_else(param=False):
    if param:
        return 1
    return 0

>>> T(lambda : no_else()).repeat()
[0.3359846013948413, 0.29025818923918223, 0.2921801513879245]
>>> T(lambda : no_else(True)).repeat()
[0.3810395594970828, 0.2969634408842694, 0.2960104566362247]

我的猜测是without_else与globals()中的其他内容有哈希冲突，因此全局名称查找稍微慢一些。

编辑：具有7个或8个键的字典可能有32个槽，因此在此基础上without_else与__builtins__存在哈希冲突：

>>> [(k, hash(k) % 32) for k in globals().keys() ]
[('__builtins__', 8), ('with_else', 9), ('__package__', 15), ('without_else', 8), ('T', 21), ('__name__', 25), ('no_else', 28), ('__doc__', 29)]

要澄清散列是如何工作的：

__builtins__散列到-1196389688，它将表大小（32）的模减小，这意味着它存储在表的8插槽中。

without_else散列到505688136，它将模32缩减为8，因此存在冲突。要解决此Python计算：

开始于：

j = hash % 32
perturb = hash

重复此操作，直到找到一个空闲插槽：

j = (5*j) + 1 + perturb;
perturb >>= 5;
use j % 2**i as the next table index;

这使它17用作下一个索引。幸运的是这是免费的，所以循环只重复一次。哈希表的大小是2的幂，因此2**i是哈希表的大小，i是哈希值j中使用的位数。

对表的每个探测都可以找到其中一个：

• 插槽是空的，在这种情况下，探测停止，我们知道 值不在表中。

• 这个插槽没有使用过，但在过去使用过，在这种情况下，我们可以尝试 下一个值按上述方式计算。

• 插槽已满，但表中存储的完整哈希值不是 和我们要找的密钥的散列一样 发生在__builtins__与without_else）的情况下。

• 插槽已满，并且正好具有我们所需的哈希值，然后是Python 检查我们正在查找的密钥和对象是否是 相同的对象（在本例中是因为短字符串 可能是标识符，所以相同的标识符使用 完全相同的字符串）。

• 最后当槽满时，散列完全匹配，但是键 不是同一个对象，那么只有这样Python才会尝试 比较他们是否平等。这是相对缓慢的，但在 名字查找的情况实际上不应该发生。