Dlaczego kod Pythona działa szybciej w funkcji?

833
def main():
    for i in xrange(10**8):
        pass
main()

Ten fragment kodu w Pythonie jest uruchamiany (Uwaga: synchronizacja odbywa się za pomocą funkcji czasu w BASH w systemie Linux).

real    0m1.841s
user    0m1.828s
sys     0m0.012s

Jeśli jednak pętla for nie jest umieszczona w funkcji,

for i in xrange(10**8):
    pass

wtedy działa znacznie dłużej:

real    0m4.543s
user    0m4.524s
sys     0m0.012s

Dlaczego to?

thedoctar
źródło
16
Jak właściwie mierzyłeś czas?
Andrew Jaffe
53
Po prostu intuicja, nie jestem pewien, czy to prawda: zgaduję, że dzieje się tak z powodu zakresów. W przypadku funkcji tworzony jest nowy zakres (tj. Rodzaj skrótu z nazwami zmiennych związanymi z ich wartością). Bez funkcji zmienne są w zasięgu globalnym, kiedy można znaleźć wiele rzeczy, a zatem spowalnia pętlę.
Scharron
4
@ Scharron To chyba nie jest to. Zdefiniowano w zakresie 200 000 zmiennych zastępczych bez widocznego wpływu na czas działania.
Deestan
2
Alex Martelli napisał dobrą odpowiedź dotyczącą tego stackoverflow.com/a/1813167/174728
John La Rooy
53
@Scharron, jesteś w połowie poprawny. Chodzi o zakresy, ale powodem, dla którego jest szybszy u lokalnych, jest to, że lokalne zakresy są faktycznie implementowane jako tablice zamiast słowników (ponieważ ich rozmiar jest znany w czasie kompilacji).
Katriel

Odpowiedzi:

532

Możesz zapytać, dlaczego przechowywanie zmiennych lokalnych jest szybsze niż globals. Jest to szczegół implementacji CPython.

Pamiętaj, że CPython jest kompilowany do kodu bajtowego, który działa interpreter. Gdy funkcja jest kompilowana, zmienne lokalne są przechowywane w tablicy o stałym rozmiarze ( nie a dict), a nazwy zmiennych są przypisywane do indeksów. Jest to możliwe, ponieważ nie można dynamicznie dodawać zmiennych lokalnych do funkcji. Następnie pobranie zmiennej lokalnej jest dosłownie wyszukiwaniem wskaźnika na liście i wzrostem liczby rachunków, PyObjectco jest banalne.

Porównaj to z globalnym wyszukiwaniem ( LOAD_GLOBAL), które jest prawdziwym dictwyszukiwaniem obejmującym skrót i tak dalej. Nawiasem mówiąc, dlatego musisz określić, global iczy chcesz, aby była globalna: jeśli kiedykolwiek przypiszesz zmienną wewnątrz zakresu, kompilator wyda STORE_FASTs o dostęp, chyba że powiesz, żeby tego nie robiła.

Nawiasem mówiąc, globalne wyszukiwania są nadal dość zoptymalizowane. Wyszukiwanie atrybutów foo.barjest naprawdę powolne!

Oto mała ilustracja na temat lokalnej zmiennej wydajności.

Katriel
źródło
6
Dotyczy to również PyPy, aż do bieżącej wersji (1.8 w momencie pisania tego tekstu). Kod testowy z OP działa około cztery razy wolniej w zakresie globalnym w porównaniu do funkcji.
GDorn
4
@Walkerneo Nie są, chyba że powiedziałeś to wstecz. Zgodnie z tym, co mówią Katrielalex i ecatmur, wyszukiwanie zmiennych globalnych jest wolniejsze niż wyszukiwanie zmiennych lokalnych ze względu na metodę przechowywania.
Jeremy Pridemore
2
@Walkerneo Podstawową rozmową, która tu się dzieje, jest porównanie między wyszukiwaniem zmiennych lokalnych w ramach funkcji a wyszukiwaniem zmiennych globalnych, które są zdefiniowane na poziomie modułu. Jeśli zauważysz w swoim oryginalnym komentarzu odpowiedź na tę odpowiedź, powiedziałeś: „Nie myślałem, że wyszukiwanie zmiennych globalnych jest szybsze niż wyszukiwanie właściwości zmiennych lokalnych”. i nie są. katrielalex powiedział, że chociaż lokalne wyszukiwania zmiennych są szybsze niż globalne, nawet globalne są dość zoptymalizowane i szybsze niż wyszukiwania atrybutów (które są różne). W tym komentarzu nie mam wystarczająco dużo miejsca na więcej.
Jeremy Pridemore
3
@Walkerneo foo.bar nie jest dostępem lokalnym. Jest to atrybut obiektu. (Wybacz brak formatowania) def foo_func: x = 5, xjest lokalny dla funkcji. Dostęp xjest lokalny. foo = SomeClass(), foo.barto dostęp do atrybutów. val = 5globalny jest globalny. Co do prędkości lokalnej> globalnej> atrybut zgodnie z tym, co tu przeczytałem. Dostęp xdo foo_funcjest więc najszybszy, następnie następuje val, a następnie foo.bar. foo.attrnie jest przeglądem lokalnym, ponieważ w kontekście tego konwój mówimy o przeglądach lokalnych, które są wyszukiwaniem zmiennej należącej do funkcji.
Jeremy Pridemore
3
@thedoctar spójrz na globals()funkcję. Jeśli potrzebujesz więcej informacji, być może będziesz musiał zacząć szukać kodu źródłowego dla Pythona. CPython to tylko nazwa zwykłej implementacji Pythona - więc prawdopodobnie już go używasz!
Katriel
661

Wewnątrz funkcji kod bajtowy to:

  2           0 SETUP_LOOP              20 (to 23)
              3 LOAD_GLOBAL              0 (xrange)
              6 LOAD_CONST               3 (100000000)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                 6 (to 22)
             16 STORE_FAST               0 (i)

  3          19 JUMP_ABSOLUTE           13
        >>   22 POP_BLOCK           
        >>   23 LOAD_CONST               0 (None)
             26 RETURN_VALUE        

Na najwyższym poziomie kod bajtowy to:

  1           0 SETUP_LOOP              20 (to 23)
              3 LOAD_NAME                0 (xrange)
              6 LOAD_CONST               3 (100000000)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                 6 (to 22)
             16 STORE_NAME               1 (i)

  2          19 JUMP_ABSOLUTE           13
        >>   22 POP_BLOCK           
        >>   23 LOAD_CONST               2 (None)
             26 RETURN_VALUE        

Różnica polega na tym, że STORE_FASTjest szybszy (!) Niż STORE_NAME. Jest tak, ponieważ w funkcjii jest lokalny, ale na najwyższym poziomie jest globalny.

Aby sprawdzić kod bajtowy, użyj dismodułu . Byłem w stanie zdemontować funkcję bezpośrednio, ale aby zdemontować kod najwyższego poziomu musiałem użyć compilewbudowanego .

ecatmur
źródło
171
Potwierdzony eksperymentem. Wstawienie global ido mainfunkcji powoduje, że czasy działania są równoważne.
Deestan
44
Odpowiada to na pytanie bez odpowiedzi na pytanie :) W przypadku lokalnych zmiennych funkcyjnych CPython faktycznie przechowuje je w krotce (którą można modyfikować z kodu C), dopóki nie zostanie zażądany słownik (np. Via locals(), inspect.getframe()itp.). Wyszukiwanie elementu tablicy za pomocą stałej liczby całkowitej jest znacznie szybsze niż wyszukiwanie słownika.
dmw
3
Podobnie jest z C / C ++, także użycie zmiennych globalnych powoduje znaczne spowolnienie
kodu
3
To pierwszy kod bajtowy, jaki widziałem. Jak na to spojrzeć i co warto wiedzieć?
Zack
4
@gkimsey Zgadzam się. Chciałem tylko podzielić się dwiema rzeczami i) To zachowanie jest odnotowane w innych językach programowania ii) Czynnik sprawczy jest bardziej stroną architektoniczną, a nie samym językiem w prawdziwym znaczeniu
codejammer
41

Oprócz lokalnych / globalnych czasów przechowywania zmiennych, przewidywanie kodu operacyjnego przyspiesza działanie.

Jak wyjaśniają inne odpowiedzi, funkcja wykorzystuje STORE_FASTw pętli kod operacji. Oto kod bajtowy dla pętli funkcji:

    >>   13 FOR_ITER                 6 (to 22)   # get next value from iterator
         16 STORE_FAST               0 (x)       # set local variable
         19 JUMP_ABSOLUTE           13           # back to FOR_ITER

Zwykle po uruchomieniu programu Python wykonuje kolejno każdy kod operacji, śledząc stos i wykonując inne kontrole w ramce stosu po wykonaniu każdego kodu operacji. Prognozowanie kodu operacyjnego oznacza, że ​​w niektórych przypadkach Python może przejść bezpośrednio do następnego kodu operacyjnego, unikając w ten sposób części tego narzutu.

W takim przypadku za każdym razem, gdy Python widzi FOR_ITER(górna część pętli), „przewiduje”, że STORE_FASTjest to kolejny kod operacji, który musi wykonać. Python następnie zerknie na następny kod operacji, a jeśli prognoza była poprawna, skacze prosto do STORE_FAST. To powoduje ściśnięcie dwóch kodów operacyjnych w jeden kod operacji.

Z drugiej strony STORE_NAMEopcode jest używany w pętli na poziomie globalnym. Python * nie * robi podobnych prognoz, gdy widzi ten kod operacji. Zamiast tego musi wrócić do górnej części pętli oceny, co ma oczywiste implikacje dla prędkości, z jaką pętla jest wykonywana.

Aby podać więcej szczegółów technicznych na temat tej optymalizacji, oto cytat z ceval.cpliku („silnik” maszyny wirtualnej Pythona):

Niektóre kody są zwykle parami, dzięki czemu można przewidzieć drugi kod podczas pierwszego uruchomienia. Na przykład GET_ITERczęsto występuje po nim FOR_ITER. I FOR_ITERczęsto następuje po nimSTORE_FAST lub UNPACK_SEQUENCE.

Weryfikacja prognozy kosztuje pojedynczy szybki test zmiennej rejestru na stałą. Jeśli parowanie było dobre, wówczas predykcja wewnętrznej gałęzi procesora ma duże prawdopodobieństwo powodzenia, co powoduje prawie zerowe przejście do następnego kodu operacji. Udane przewidywanie oszczędza podróż przez pętlę eval, w tym jej dwie nieprzewidywalne gałęzie, HAS_ARGtest i obudowę przełącznika. W połączeniu z przewidywaniem wewnętrznej gałęzi procesora, sukces PREDICTpowoduje, że dwa kody operacyjne działają tak, jakby były pojedynczym nowym kodem operacyjnym z połączonymi ciałami.

Widzimy w kodzie źródłowym FOR_ITERopcode dokładnie, gdzie dokonano prognozy STORE_FAST:

case FOR_ITER:                         // the FOR_ITER opcode case
    v = TOP();
    x = (*v->ob_type->tp_iternext)(v); // x is the next value from iterator
    if (x != NULL) {                     
        PUSH(x);                       // put x on top of the stack
        PREDICT(STORE_FAST);           // predict STORE_FAST will follow - success!
        PREDICT(UNPACK_SEQUENCE);      // this and everything below is skipped
        continue;
    }
    // error-checking and more code for when the iterator ends normally                                     

PREDICTFunkcja rozszerza się if (*next_instr == op) goto PRED_##op, czyli po prostu przeskoczyć do początku przewidywanej opcode. W tym przypadku przeskakujemy tutaj:

PREDICTED_WITH_ARG(STORE_FAST);
case STORE_FAST:
    v = POP();                     // pop x back off the stack
    SETLOCAL(oparg, v);            // set it as the new local variable
    goto fast_next_opcode;

Zmienna lokalna jest teraz ustawiona i następny kod operacji jest gotowy do wykonania. Python kontynuuje iterowalność aż do końca, dzięki czemu za każdym razem dokonuje udanej prognozy.

Strona wiki Python zawiera więcej informacji na temat działania maszyny wirtualnej CPython.

Alex Riley
źródło
Drobna aktualizacja: Od wersji CPython 3.6 oszczędności wynikające z prognoz nieco się zmniejszają; zamiast dwóch nieprzewidywalnych gałęzi jest tylko jedna. Zmiana wynika z przejścia z kodu bajtowego na kod słowny ; teraz wszystkie „kody słowne” mają argument, jest on zerowany, gdy instrukcja nie przyjmuje logicznie argumentu. Dlatego HAS_ARGtest nigdy nie występuje (z wyjątkiem sytuacji, gdy śledzenie niskiego poziomu jest włączone zarówno podczas kompilacji, jak i w środowisku wykonawczym, czego nie robi żadna normalna wersja), pozostawiając tylko jeden nieprzewidywalny skok.
ShadowRanger
Nawet ten nieprzewidywalny skok nie zdarza się w większości wersji CPython, ze względu na nowe ( od Python 3.1 , domyślnie włączone w 3.2 ) obliczone zachowanie gotos; po użyciu PREDICTmakro jest całkowicie wyłączone; zamiast tego większość przypadków kończy się DISPATCHbezpośrednio na gałęzi. Ale w procesorach przewidujących rozgałęzienia efekt jest podobny do tego PREDICT, ponieważ rozgałęzianie (i przewidywanie) odbywa się dla poszczególnych kodów, co zwiększa szanse na pomyślne przewidywanie rozgałęzień.
ShadowRanger