Почему удаление 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

Здесь происходит то, что 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 2

Для меня они практически одинаковы по скорости: (Python 2.6.6 на Debian)

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 3

Я подвергаю сомнению время. Эти две функции не повторяются сами по себе. fact1 и fact2 оба вызывают fact , который не отображается.

Как только это исправлено, дизассемблирование (как в Py2.6, так и в Py2.7) показывает, что оба работают с одинаковыми кодами операций, за исключением имени вернувшейся в функцию. Выбор имени вызывает небольшую разницу во времени, потому что fact1 может вставляться в словарь модуля без коллизий имен, в то время как * fact2) может иметь значение хеша, которое вступает в конфликт с другим именем в модуле.

Другими словами, любые различия, которые вы видите во времени, не связаны с выбором того, присутствует ли условие else: -)