Почему удаление другого замедляет мой код?

Рассмотрим следующие функции:

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% медленнее. Это очень важно. Почему?

Ответы

Ответ 1

Для меня они практически одинаковы: (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 в случае, когда управление достигает конца тела функции.

Ответ 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__

Ответ 3

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

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

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