Dlaczego wczesny powrót jest wolniejszy niż w innym przypadku?


179

To pytanie uzupełniające do odpowiedzi, której udzieliłem kilka dni temu . Edycja: 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. Przeprosiny. Podane 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]

... lub innymi słowy: posiadanie elseklauzuli jest szybsze, niezależnie od tego, czy ifwarunek zostanie wyzwolony, czy nie.

Zakładam, że ma to związek z innym generowanym przez nich kodem bajtowym, ale czy ktoś jest w stanie potwierdzić / wyjaśnić szczegółowo?

EDYCJA: Wydaje się, że nie wszyscy są w stanie odtworzyć moje czasy, więc pomyślałem, że przydatne może być podanie pewnych informacji w moim systemie. Używam 64-bitowego systemu Ubuntu 11.10 z zainstalowanym domyślnym pythonem. pythongeneruje 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 dezasemblacji 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        

1
istniało identyczne pytanie dotyczące SO, którego nie mogę teraz znaleźć. Sprawdzili wygenerowany kod bajtowy i był jeszcze jeden krok. Obserwowane różnice były bardzo zależne od testera (maszyna, SO ..), czasami znajdując tylko bardzo małe różnice.
joaquin

3
W wersji 3.x oba generują identyczny zapis kodu bajtowego dla jakiegoś nieosiągalnego kodu ( LOAD_CONST(None); RETURN_VALUE- jak już wspomniano, nigdy nie został osiągnięty) na końcu with_else. Wątpię, czy martwy kod przyspiesza działanie funkcji. Czy ktoś może podać dis2,7?

4
Nie byłem w stanie tego odtworzyć. Funkcja z elsei Falsebyła najwolniejsza ze wszystkich (152ns). Drugi najszybszy był Truebez else(143ns), a dwa pozostałe były w zasadzie takie same (137ns i 138ns). Nie użyłem parametru domyślnego i zmierzyłem go %timeitw iPython.
rplnt

Nie mogę odtworzyć tych czasów, czasami with_else jest szybsze, czasami jest to wersja without_else, wygląda na to, że są dla mnie bardzo podobne ...
Cédric Julien

1
Dodano wyniki demontażu. Używam Ubuntu 11.10, 64-bitowy, podstawowy Python 2.7 - taka sama konfiguracja jak @mac. Zgadzam się również, że with_elsejest zauważalnie szybszy.
Chris Morgan

Odpowiedzi:


387

To tylko domysł, i nie wymyśliłem łatwego sposobu, aby sprawdzić, czy jest to właściwe, ale mam dla ciebie teorię.

Wypróbowałem Twój kod i otrzymałem to samo z wyników, 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 kod bajtowy jest identyczny, jedyną różnicą jest nazwa funkcji. W szczególności test synchronizacji sprawdza globalną nazwę. 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]

Domyślam się, że without_elsema on konflikt mieszający z czymś innym, globals()więc globalne wyszukiwanie nazw jest nieco wolniejsze.

Edycja : słownik z 7 lub 8 klawiszami ma prawdopodobnie 32 miejsca, więc na tej podstawie without_elsewystępuje kolizja skrótu 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, co zmniejszyło moduł wielkości stołu (32), co oznacza, że ​​jest on przechowywany w szczelinie nr 8 stołu.

without_elsehashes do 505688136, który zredukował modulo 32 do 8, więc jest kolizja. Aby rozwiązać ten problem, Python oblicza:

Począwszy 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ępnego indeksu. Na szczęście jest to darmowe, więc pętla powtarza się tylko raz. Rozmiar tablicy skrótów to potęga 2, podobnie 2**ijak rozmiar tablicy skrótów, ito liczba bitów użytych na podstawie wartości skrótu j.

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

  • Szczelina jest pusta, w takim przypadku sondowanie zatrzymuje się i wiemy, że wartości nie ma w tabeli.

  • Szczelina nie jest używana, ale była używana w przeszłości, w takim przypadku przechodzimy do następnej wartości obliczonej jak wyżej.

  • Slot jest pełny, ale pełna wartość skrótu przechowywana w tabeli nie jest taka sama jak skrót klucza, którego szukamy (tak dzieje się w przypadku __builtins__vs without_else).

  • Boks jest pełny i ma dokładnie taką wartość skrótu, jaką chcemy, a następnie Python sprawdza, czy klucz i obiekt, którego szukamy, są tym samym obiektem (co w tym przypadku będzie, ponieważ krótkie łańcuchy, które mogą być identyfikatorami, są internalizowane, więc identyczne identyfikatory używają dokładnie tego samego ciągu).

  • Wreszcie, gdy boks jest pełny, skrót jest dokładnie zgodny, ale klucze nie są identycznymi obiektami, wtedy i tylko wtedy Python spróbuje porównać je dla równości. Jest to stosunkowo powolne, ale w przypadku wyszukiwania nazw tak naprawdę nie powinno się zdarzyć.


9
@Chris, nie, długość łańcucha nie powinna być znacząca. Za pierwszym razem, gdy haszujesz łańcuch, zajmie to czas proporcjonalny do długości łańcucha, ale następnie obliczony skrót jest buforowany w obiekcie łańcucha, więc kolejne skróty to O (1).
Duncan

1
Ach, ok, nie byłem świadomy buforowania, ale to ma sens
Chris Eberle,

9
Fascynujący! Czy mogę nazywać cię Sherlock? ;) W każdym razie mam nadzieję, że nie zapomnę dać ci dodatkowych punktów z nagrodą, gdy tylko pytanie będzie kwalifikowalne.
Voo,

4
@mac, niezupełnie. Dodam trochę o rozdzielczości skrótu (zamierzałem to wycisnąć w komentarzu, ale jest to bardziej interesujące niż myślałem).
Duncan

6
@ Duncan - Dziękuję bardzo za poświęcenie czasu na zilustrowanie procesu mieszania. Najlepsza odpowiedź! :)
Mac
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.