Dlaczego wczesny powrót jest wolniejszy niż inne?

Question

Dlaczego wczesny powrót jest wolniejszy niż inne?

Jest to pytanie uzupełniające odpowiedź, którą udzieliłem kilka dni temu . Edit: wydaje się, że OP tego pytania użył już kodu, który mu wysłałem, aby zadać to samo pytanie , ale nie byłem tego świadomy. Przepraszam. Odpowiedzi są jednak inne!

Zasadniczo zauważyłem, że:

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

...innymi słowy: posiadanie klauzuli else jest szybsze, niezależnie od tego, czy warunek if jest wyzwalany, czy nie.

Zakładam, że ma do czynienia z różnymi bajtami generowanymi przez te dwa, ale czy ktoś jest w stanie potwierdzić/wyjaśnić szczegółowo?

EDIT: wydaje się, że nie każdy jest w stanie odtworzyć moje czasy, więc pomyślałem, że przydałoby się podać trochę informacji o moim systemie. Używam Ubuntu 11.10 64 bit z domyślnym zainstalowanym Pythonem. python generuje następujące informacje o wersji:

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

Oto wyniki demontażu w Pythonie 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

158

python optimization python-2.7

Author: Community, 2011-11-25

Source

1 answers

score 347 · Accepted Answer

To czysty domysł, i nie wymyśliłem łatwego sposobu, aby sprawdzić, czy to prawda, ale mam dla Ciebie teorię.

Wypróbowałem Twój kod i uzyskałem taki sam wynik, without_else() jest wielokrotnie nieco wolniejszy niż 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]

Biorąc pod uwagę, że bajt jest identyczny, jedyną różnicą jest nazwa funkcji. W szczególności test czasu dokonuje wyszukiwania globalnej nazwy. Spróbuj zmienić nazwę without_else(), a różnica zniknie:

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

Zgaduję, że {[8] } ma kolizję hashową z czymś innym w globals(), więc globalne wyszukiwanie nazw jest nieco wolniejsze.

Edit : słownik z 7 lub 8 kluczami ma prawdopodobnie 32 sloty, więc na tej podstawie {[8] } ma kolizję hashową z __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)]

Aby wyjaśnić, jak działa haszowanie:

__builtins__ skróty do -1196389688, które zmniejszyły modulo rozmiar tabeli (32) oznaczają, że jest ona przechowywana w slocie #8 tabeli.

without_else hashów na 505688136 co zmniejszyło modulo 32 to 8 tak doszło do kolizji. Aby rozwiązać ten Python oblicza:

Zaczynając od:

j = hash % 32
perturb = hash

Powtarzaj to, aż znajdziemy wolne miejsce:

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

Co daje 17 do wykorzystania jako następny indeks. Na szczęście jest to darmowe, więc pętla powtarza się tylko raz. Wielkość tabeli hash jest potęgą 2, więc {[14] } jest wielkością tabeli hash, {[15] } jest liczbą bitów użytych z wartości hash j.

Każda sonda w tabeli może znaleźć jedną z nich:

Gniazdo jest pusty, w takim przypadku sonda zatrzymuje się i wiemy, że wartości nie ma w tabeli.
Slot jest NIEUŻYWANY, ale był używany w przeszłości w takim przypadku idziemy spróbować Następna wartość obliczona jak powyżej.
Szczelina jest pełna, ale pełna wartość hash zapisana w tabeli nie jest taki sam jak hash klucza, którego szukamy (to co dzieje się w przypadku __builtins__ vs without_else).
Szczelina jest pełna i ma dokładnie taką wartość hash, jaką chcemy, a następnie Python sprawdza, czy klucz i obiekt, którego szukamy, są ten sam obiekt (który w tym przypadku będzie ponieważ krótkie łańcuchy które mogą być identyfikatory są internowane więc identycznych identyfikatorów używać dokładnie ten sam ciąg).
Wreszcie, gdy szczelina jest pełna, hash pasuje dokładnie, ale klucze nie są identycznym obiektem, wtedy i tylko wtedy Python spróbuje porównując je dla równości. Jest to stosunkowo powolne, ale w przypadku szukania nazwy nie powinno się zdarza się.