Warum läuft Python-Code in einer Funktion schneller?

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

Dieser Code in Python läuft in (Hinweis: Das Timing erfolgt mit der Zeitfunktion in BASH unter Linux.)

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

Wenn die for-Schleife jedoch nicht in einer Funktion platziert ist,

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

dann läuft es viel länger:

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

Warum ist das?

Thedoctar
quelle
16
Wie hast du eigentlich das Timing gemacht?
Andrew Jaffe
53
Nur eine Intuition, nicht sicher, ob es wahr ist: Ich würde vermuten, dass es am Umfang liegt. Im Funktionsfall wird ein neuer Bereich erstellt (dh eine Art Hash mit Variablennamen, die an ihren Wert gebunden sind). Ohne eine Funktion befinden sich Variablen im globalen Bereich, wenn Sie viele Dinge finden können, wodurch die Schleife verlangsamt wird.
Scharron
4
@Scharron Das scheint es nicht zu sein. Definierte 200k Dummy-Variablen im Bereich, ohne dass dies die Laufzeit sichtbar beeinflusst.
Deestan
2
Alex Martelli schrieb eine gute Antwort bezüglich dieses stackoverflow.com/a/1813167/174728
John La Rooy
53
@Scharron du bist halb richtig. Es geht um Bereiche, aber der Grund, warum es bei Einheimischen schneller ist, ist, dass lokale Bereiche tatsächlich als Arrays anstelle von Wörterbüchern implementiert werden (da ihre Größe zur Kompilierungszeit bekannt ist).
Katriel

Antworten:

532

Sie könnten sich fragen, warum es schneller ist, lokale Variablen als globale zu speichern. Dies ist ein CPython-Implementierungsdetail.

Denken Sie daran, dass CPython zu Bytecode kompiliert wird, den der Interpreter ausführt. Wenn eine Funktion kompiliert wird, werden die lokalen Variablen in einem Array fester Größe ( nicht a dict) gespeichert und den Indizes Variablennamen zugewiesen. Dies ist möglich, weil Sie einer Funktion keine dynamischen Variablen dynamisch hinzufügen können. Das Abrufen einer lokalen Variablen ist dann buchstäblich eine Zeigersuche in der Liste und eine Erhöhung der Anzahl der Nachzähler, PyObjectwas trivial ist.

Vergleichen Sie dies mit einem globalen Lookup ( LOAD_GLOBAL), bei dem es sich um eine echte dictSuche mit einem Hash usw. handelt. Aus diesem Grund müssen Sie im Übrigen angeben, global iob es global sein soll: Wenn Sie jemals eine Variable innerhalb eines Bereichs zuweisen, gibt der Compiler STORE_FASTs für den Zugriff aus, es sei denn, Sie weisen ihn an , dies nicht zu tun.

Übrigens sind globale Suchvorgänge immer noch ziemlich optimiert. Attributsuchen foo.barsind die wirklich langsamen!

Hier ist eine kleine Illustration zur lokalen variablen Effizienz.

Katriel
quelle
6
Dies gilt auch für PyPy bis zur aktuellen Version (1.8 zum Zeitpunkt dieses Schreibens). Der Testcode aus dem OP wird im globalen Bereich etwa viermal langsamer ausgeführt als innerhalb einer Funktion.
GDorn
4
@ Walkerneo Sie sind es nicht, es sei denn, Sie sagten es rückwärts. Nach den Aussagen von katrielalex und ecatmur sind globale Variablensuchen aufgrund der Speichermethode langsamer als lokale Variablensuchen.
Jeremy Pridemore
2
@Walkerneo Die primäre Konversation, die hier stattfindet, ist der Vergleich zwischen lokalen Variablensuchen innerhalb einer Funktion und globalen Variablensuchen, die auf Modulebene definiert sind. Wenn Sie in Ihrer ursprünglichen Kommentarantwort auf diese Antwort feststellen, dass Sie gesagt haben: "Ich hätte nicht gedacht, dass die Suche nach globalen Variablen schneller ist als die Suche nach lokalen Variableneigenschaften." und sie sind nicht. katrielalex sagte, dass, obwohl lokale Variablensuchen schneller sind als globale, sogar globale ziemlich optimiert und schneller sind als Attributsuchen (die unterschiedlich sind). Ich habe in diesem Kommentar nicht genug Platz für mehr.
Jeremy Pridemore
3
@Walkerneo foo.bar ist kein lokaler Zugriff. Es ist ein Attribut eines Objekts. (Verzeihen Sie die fehlende Formatierung) def foo_func: x = 5, xist lokal für eine Funktion. Der Zugriff xerfolgt lokal. foo = SomeClass(), foo.barIst Attribut Zugriff. val = 5global ist global. Bezüglich des Attributs speed local> global> gemäß dem, was ich hier gelesen habe. So Zugriff xin foo_funcist am schnellsten, gefolgt von val, gefolgt von foo.bar. foo.attrist keine lokale Suche, da es sich im Kontext dieser Convo um eine lokale Suche handelt, bei der es sich um eine Suche nach einer Variablen handelt, die zu einer Funktion gehört.
Jeremy Pridemore
3
@thedoctar werfen Sie einen Blick auf die globals()Funktion. Wenn Sie mehr Informationen wünschen, müssen Sie möglicherweise den Quellcode für Python suchen. Und CPython ist nur der Name für die übliche Implementierung von Python - Sie verwenden es also wahrscheinlich bereits!
Katriel
661

Innerhalb einer Funktion lautet der Bytecode:

  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        

Auf der obersten Ebene lautet der Bytecode:

  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        

Der Unterschied ist, dass STORE_FASTes schneller (!) Ist als STORE_NAME. Dies liegt daran, dass eine Funktion ilokal ist, auf oberster Ebene jedoch global.

Verwenden Sie das disModul , um den Bytecode zu überprüfen . Ich konnte die Funktion direkt zerlegen, aber um den obersten Code zu zerlegen, musste ich den compileeingebauten verwenden .

ecatmur
quelle
171
Durch Experiment bestätigt. Durch das Einfügen global iin die mainFunktion werden die Laufzeiten gleichwertig.
Deestan
44
Dies beantwortet die Frage, ohne die Frage zu beantworten :) Bei lokalen Funktionsvariablen speichert CPython diese tatsächlich in einem Tupel (das vom C-Code veränderbar ist), bis ein Wörterbuch angefordert wird (z. B. via locals()oder inspect.getframe()usw.). Das Nachschlagen eines Array-Elements mit einer konstanten Ganzzahl ist viel schneller als das Durchsuchen eines Diktats.
dmw
3
Es ist das gleiche mit C / C ++ auch verursacht globale Variablen deutliche Verlangsamung
Dies gilt Codejammer
3
Dies ist das erste Mal, dass ich Bytecode gesehen habe. Wie sieht man das aus und es ist wichtig zu wissen?
Zack
4
@gkimsey Ich stimme zu. Ich wollte nur zwei Dinge teilen: i) Dieses Verhalten wird in anderen Programmiersprachen festgestellt. Ii) Der Erreger ist eher die architektonische Seite und nicht die Sprache selbst im eigentlichen Sinne
Codejammer
41

Abgesehen von lokalen / globalen variablen Speicherzeiten beschleunigt die Opcode-Vorhersage die Funktion.

Wie die anderen Antworten erklären, verwendet die Funktion den STORE_FASTOpcode in der Schleife. Hier ist der Bytecode für die Funktionsschleife:

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

Normalerweise führt Python beim Ausführen eines Programms jeden Opcode nacheinander aus, verfolgt den Stapel und führt nach Ausführung jedes Opcodes weitere Überprüfungen des Stapelrahmens durch. Opcode-Vorhersage bedeutet, dass Python in bestimmten Fällen direkt zum nächsten Opcode springen kann, wodurch ein Teil dieses Overheads vermieden wird.

In diesem Fall FOR_ITER"sagt" Python jedes Mal, wenn es den oberen Rand der Schleife sieht , voraus, dass dies STORE_FASTder nächste Opcode ist, den es ausführen muss. Python schaut dann auf den nächsten Opcode und springt, wenn die Vorhersage korrekt war, direkt zu STORE_FAST. Dies hat den Effekt, dass die beiden Opcodes zu einem einzigen Opcode zusammengefasst werden.

Auf der anderen Seite die STORE_NAME Opcode in der Schleife auf globaler Ebene verwendet. Python macht * keine * ähnlichen Vorhersagen, wenn es diesen Opcode sieht. Stattdessen muss es zum Anfang der Auswertungsschleife zurückkehren, was offensichtliche Auswirkungen auf die Geschwindigkeit hat, mit der die Schleife ausgeführt wird.

Um weitere technische Details zu dieser Optimierung zu erhalten, finden Sie hier ein Zitat aus dem ceval.c Datei (der "Engine" der virtuellen Maschine von Python):

Einige Opcodes kommen in der Regel paarweise vor, sodass der zweite Code vorhergesagt werden kann, wenn der erste ausgeführt wird. Zum Beispiel GET_ITERwird oft gefolgt von FOR_ITER. Und FOR_ITERwird oft gefolgt vonSTORE_FAST oderUNPACK_SEQUENCE .

Das Überprüfen der Vorhersage kostet einen einzelnen Hochgeschwindigkeitstest einer Registervariablen gegen eine Konstante. Wenn die Paarung gut war, hat die interne Verzweigungsprädikation des Prozessors eine hohe Erfolgswahrscheinlichkeit, was zu einem Übergang von nahezu null Overhead zum nächsten Opcode führt. Eine erfolgreiche Vorhersage erspart eine Reise durch die Bewertungsschleife einschließlich ihrer zwei unvorhersehbaren Zweige, derHAS_ARG Tests und des Schaltfalls. In Kombination mit der internen Verzweigungsvorhersage des Prozessors führt ein Erfolg PREDICTdazu, dass die beiden Opcodes so ausgeführt werden, als wären sie ein einziger neuer Opcode mit den kombinierten Körpern.

Wir können im Quellcode für den FOR_ITEROpcode genau sehen, wo die Vorhersage fürSTORE_FAST gemacht wird:

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                                     

Die PREDICTFunktion wird erweitert aufif (*next_instr == op) goto PRED_##op dh wir springen einfach zum Anfang des vorhergesagten Opcodes. In diesem Fall springen wir hier:

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;

Die lokale Variable ist jetzt gesetzt und der nächste Opcode steht zur Ausführung bereit. Python fährt mit dem Iterable fort, bis es das Ende erreicht, und macht jedes Mal die erfolgreiche Vorhersage.

Auf der Python-Wiki-Seite finden Sie weitere Informationen zur Funktionsweise der virtuellen Maschine von CPython.

Alex Riley
quelle
Kleinere Aktualisierung: Ab CPython 3.6 gehen die Einsparungen durch die Vorhersage etwas zurück. Anstelle von zwei unvorhersehbaren Zweigen gibt es nur einen. Die Änderung ist auf den Wechsel von Bytecode zu Wordcode zurückzuführen . Jetzt haben alle "Wortcodes" ein Argument. Es wird nur auf Null gesetzt, wenn die Anweisung kein Argument logisch akzeptiert. Daher wird der HAS_ARGTest nie durchgeführt (außer wenn die Ablaufverfolgung auf niedriger Ebene sowohl zur Kompilierung als auch zur Laufzeit aktiviert ist, was bei keinem normalen Build der Fall ist), sodass nur ein unvorhersehbarer Sprung verbleibt.
ShadowRanger
Selbst dieser unvorhersehbare Sprung tritt in den meisten CPython-Builds aufgrund des neuen ( ab Python 3.1 , standardmäßig in 3.2 standardmäßig aktiviert ) gotos-Verhaltens nicht auf. Bei Verwendung ist das PREDICTMakro vollständig deaktiviert. Stattdessen enden die meisten Fälle in einem DISPATCH, der direkt verzweigt. Bei Verzweigungsvorhersage-CPUs ist der Effekt ähnlich dem von PREDICT, da die Verzweigung (und Vorhersage) pro Opcode erfolgt, was die Wahrscheinlichkeit einer erfolgreichen Verzweigungsvorhersage erhöht.
ShadowRanger