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

Это следующий вопрос к ответу, который я дал несколько дней назад. Изменить: кажется, что OP этого вопроса уже использовал код, который я отправил ему, чтобы задать тот же вопрос, но я не знал о нем Это. Извиняюсь. Полученные ответы разные, хотя!

В основном я заметил, что:

>>> 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]

... или другими словами: с условием else выполняется быстрее, независимо от условия if, которое запускается или нет.

Я предполагаю, что он имеет отношение к другому байт-коду, сгенерированному этими двумя, но кто-нибудь может подтвердить/объяснить подробно?

РЕДАКТИРОВАТЬ: Кажется, что не все могут воспроизвести мои тайминги, поэтому я подумал, что было бы полезно дать некоторую информацию о моей системе. Я запускаю Ubuntu 11.10 64 бит с установленным по умолчанию python. python генерирует следующую информацию о версии:

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

Ниже приведены результаты разборки в Python 2.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

Ответы

Ответ 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__ vs without_else).

  • Слот заполнен и имеет точно значение хеша, которое мы хотим, затем Python проверяет, являются ли ключ и объект, который мы просматриваем, тот же объект (который в этом случае будет потому, что короткие строки которые могут быть идентификаторами, интернированы, поэтому идентичные идентификаторы используют точно такая же строка).

  • Наконец, когда слот заполнен, хеш точно соответствует, но клавиши не являются идентичным объектом, тогда и только тогда Python попытается сравнивая их для равенства. Это сравнительно медленно, но в случай поиска имен не должен происходить фактически.