Warum ist Code, der Zwischenvariablen verwendet, schneller als Code ohne?

76

Ich bin auf dieses seltsame Verhalten gestoßen und habe es nicht erklärt. Dies sind die Benchmarks:

py -3 -m timeit "tuple(range(2000)) == tuple(range(2000))"
10000 loops, best of 3: 97.7 usec per loop
py -3 -m timeit "a = tuple(range(2000));  b = tuple(range(2000)); a==b"
10000 loops, best of 3: 70.7 usec per loop

Wie kommt es, dass der Vergleich mit der Variablenzuweisung um mehr als 27% schneller ist als die Verwendung eines Einzeilers mit temporären Variablen?

In den Python-Dokumenten ist die Speicherbereinigung während der Zeit deaktiviert, daher kann dies nicht der Fall sein. Ist es eine Art Optimierung?

Die Ergebnisse können in geringerem Umfang auch in Python 2.x reproduziert werden.

Unter Windows 7, CPython 3.5.1, Intel i7 3.40 GHz, 64-Bit-Betriebssystem und Python. Scheint, als würde ein anderer Computer, den ich mit Intel 3.7 3.60 GHz mit Python 3.5.0 ausgeführt habe, die Ergebnisse nicht reproduzieren.


Das Ausführen mit demselben Python-Prozess mit timeit.timeit()@ 10000-Schleifen ergab 0,703 bzw. 0,804. Zeigt immer noch, wenn auch in geringerem Maße. (~ 12,5%)

Bharel
quelle
6
Vergleiche dis.dis("tuple(range(2000)) == tuple(range(2000))")mit dis.dis("a = tuple(range(2000)); b = tuple(range(2000)); a==b"). In meiner Konfiguration enthält das zweite Snippet tatsächlich den gesamten Bytecode des ersten und einige zusätzliche Anweisungen. Es ist kaum zu glauben, dass mehr Bytecode-Anweisungen zu einer schnelleren Ausführung führen. Vielleicht ist es ein Fehler in einer bestimmten Python-Version?
Łukasz Rogalski
1
Wenn Sie versuchen, dies zu reproduzieren, führen Sie den Test bitte mehrmals in verschiedenen Ausführungsreihenfolgen aus. - Ungeachtet des Ergebnisses und der Seltsamkeit davon denke ich, dass die Frage für SO nicht besonders wertvoll ist.
stupsen
3
Ich finde das ziemlich interessant. @poke Sie müssen sich daran erinnern, dass eine Antwort auf ein ähnliches Phänomen jetzt die am besten bewertete Antwort im Stackoverflow ist.
Antti Haapala
3
Versuchen Sie außerdem, den Test in einem einzelnen Python-Prozess timeitdirekt mit dem Modul auszuführen . Vergleiche zwischen zwei separaten Python-Prozessen können durch den Taskplaner des Betriebssystems oder andere Effekte beeinflusst werden.
stupsen
1
@aluriak "best of 3" bedeutet best of drei Durchschnittswerte . Dies geschieht, weil ein Durchschnitt beispielsweise einen unerwarteten Prozessstillstand beinhalten kann. Das Beste aus den Durchschnittswerten zu nehmen, vermeidet dies.
Veedrac

Antworten:

107

Meine Ergebnisse waren ähnlich wie Ihre: Der Code mit Zwischenvariablen war in Python 3.4 ziemlich konsistent mindestens 10-20% schneller. Wenn ich jedoch IPython auf demselben Python 3.4-Interpreter verwendet habe, habe ich folgende Ergebnisse erhalten:

In [1]: %timeit -n10000 -r20 tuple(range(2000)) == tuple(range(2000))
10000 loops, best of 20: 74.2 µs per loop

In [2]: %timeit -n10000 -r20 a = tuple(range(2000));  b = tuple(range(2000)); a==b
10000 loops, best of 20: 75.7 µs per loop

Insbesondere habe ich es nie geschafft, die 74,2 µs für die ersteren zu erreichen, als ich sie -mtimeitüber die Befehlszeile verwendet habe.

Dieser Heisenbug erwies sich also als etwas ziemlich Interessantes. Ich habe beschlossen, den Befehl mit auszuführen, straceund tatsächlich ist etwas faul:

% strace -o withoutvars python3 -m timeit "tuple(range(2000)) == tuple(range(2000))"
10000 loops, best of 3: 134 usec per loop
% strace -o withvars python3 -mtimeit "a = tuple(range(2000));  b = tuple(range(2000)); a==b"
10000 loops, best of 3: 75.8 usec per loop
% grep mmap withvars|wc -l
46
% grep mmap withoutvars|wc -l
41149

Das ist ein guter Grund für den Unterschied. Der Code, der keine Variablen verwendet, bewirkt, dass der mmapSystemaufruf fast 1000x häufiger aufgerufen wird als der Code, der Zwischenvariablen verwendet.

Das withoutvarsist voll von mmap/ munmapfür eine 256k Region; Dieselben Zeilen werden immer wieder wiederholt:

mmap(NULL, 262144, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f32e56de000
munmap(0x7f32e56de000, 262144)          = 0
mmap(NULL, 262144, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f32e56de000
munmap(0x7f32e56de000, 262144)          = 0
mmap(NULL, 262144, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f32e56de000
munmap(0x7f32e56de000, 262144)          = 0

Der mmapAufruf scheint von der Funktion _PyObject_ArenaMmapvon zu kommen Objects/obmalloc.c; das obmalloc.centhält auch das Makro ARENA_SIZE, das #defined sein soll (256 << 10)(das heißt 262144); ähnlich munmappasst das _PyObject_ArenaMunmapvon obmalloc.c.

obmalloc.c sagt, dass

Vor Python 2.5 wurden Arenen nie free()bearbeitet. Ab Python 2.5 versuchen wir, free()Arenen zu erstellen, und verwenden einige milde heuristische Strategien, um die Wahrscheinlichkeit zu erhöhen, dass Arenen schließlich freigegeben werden können.

Daher führen diese Heuristiken und die Tatsache, dass der Python-Objektzuweiser diese freien Arenen freigibt, sobald sie geleert sind, zu einem python3 -mtimeit 'tuple(range(2000)) == tuple(range(2000))'pathologischen Verhalten, bei dem ein Speicherbereich von 256 kiB wiederholt neu zugewiesen und freigegeben wird. und diese Zuordnung geschieht mit mmap/ munmap, die vergleichsweise teuer , wie sie sind Systemaufrufe ist - weiterhin mmapmit MAP_ANONYMOUSerfordert , dass die neu kartiert Seiten müssen auf Null gesetzt werden - auch wenn Python würde sich nicht darum.

Das Verhalten ist in dem Code, der Zwischenvariablen verwendet, nicht vorhanden, da etwas mehr Speicher verwendet wird und kein Speicherbereich freigegeben werden kann, da einige Objekte noch darin zugeordnet sind. Das liegt daran timeit, dass es nicht anders als eine Schleife wird

for n in range(10000)
    a = tuple(range(2000))
    b = tuple(range(2000))
    a == b

Das Verhalten ist nun, dass beide aund bbleiben gebunden, bis sie * neu zugewiesen werden. In der zweiten Iteration tuple(range(2000))wird also ein drittes Tupel zugewiesen, und die Zuweisung a = tuple(...)verringert die Referenzanzahl des alten Tupels, wodurch es freigegeben wird, und erhöht sich der Referenzzähler des neuen Tupels; dann passiert das gleiche mit b. Daher gibt es nach der ersten Iteration immer mindestens 2 dieser Tupel, wenn nicht 3, so dass das Thrashing nicht auftritt.

Insbesondere kann nicht garantiert werden, dass der Code mit Zwischenvariablen immer schneller ist. In einigen Setups kann die Verwendung von Zwischenvariablen zu zusätzlichen mmapAufrufen führen, während der Code, der die Rückgabewerte direkt vergleicht, möglicherweise in Ordnung ist.


Jemand fragte, warum dies passiert, wenn die timeitSpeicherbereinigung deaktiviert wird. Es ist in der Tat wahr, dass es timeittut :

Hinweis

Standardmäßig wird timeit()die Speicherbereinigung während des Timings vorübergehend deaktiviert. Der Vorteil dieses Ansatzes besteht darin, dass unabhängige Timings vergleichbarer werden. Dieser Nachteil besteht darin, dass GC ein wichtiger Bestandteil der Leistung der gemessenen Funktion sein kann. In diesem Fall kann GC als erste Anweisung in der Setup-Zeichenfolge wieder aktiviert werden. Zum Beispiel:

Der Garbage Collector von Python ist jedoch nur dazu da, zyklischen Müll zurückzugewinnen , dh Sammlungen von Objekten, deren Referenzen Zyklen bilden. Dies ist hier nicht der Fall; Stattdessen werden diese Objekte sofort freigegeben, wenn der Referenzzähler auf Null fällt.

Antti Haapala
quelle
1
Woha, das ist interessant. Sollte sich der Müllsammler (der zeitlich deaktiviert ist) nicht um die Befreiung kümmern oder sollte er sich zumindest darum kümmern? Und es wirft eine andere Frage auf: Sind diese wiederholten Anrufe nicht ein Fehler?
Bharel
6
@Bharel eher wie "gebrochen wie geplant"
Antti Haapala
1
@Bharel Es hängt davon ab, ob eine neue Speicherarena zugewiesen wird oder nicht . Es ist durchaus möglich, dass andere Systeme teilweise freie Arenen haben, die über genügend freien Speicher in den Pools verfügen, sodass nicht mehr erforderlich ist. Sogar dieselbe Python-Version auf oberflächlich ähnlichen Systemen kann ein unterschiedliches Verhalten aufweisen - z. B. Python-Installationspfad, Anzahl der Pakete site-packages, Umgebungsvariablen, aktuelles Arbeitsverzeichnis -, die sich alle auf das Speicherlayout des Prozesses auswirken.
Antti Haapala
7
@Bharel: Der Garbage Collector in CPython wird besser als "zyklischer Garbage Collector" bezeichnet. Es geht ausschließlich darum, isolierte Referenzzyklen freizugeben, nicht um die allgemeine Speicherbereinigung. Alle anderen Bereinigungen sind synchron und in Ordnung. Wenn der letzte Verweis auf das letzte Objekt in einer Arena freigegeben wird, wird das Objekt sofort gelöscht und die Arena sofort freigegeben, ohne dass ein zyklischer Garbage Collector beteiligt sein muss. Aus diesem Grund ist das Deaktivieren legal gc. Wenn die allgemeine Bereinigung deaktiviert wäre, würde Ihnen verdammt schnell der Speicher ausgehen.
ShadowRanger
1
Zusammenfassend: Der Effekt in der Antwort ist nicht reproduzierbar (kein signifikanter Unterschied in der Anzahl der mmap-Aufrufe) auf die /usr/bin/python3mit Ubuntu 16.04 ( python3-minimalPaket) verteilte Standardeinstellung . Ich habe auch verschiedene Docker-Bilder ausprobiert, zB docker run --rm python:3.6.4 python -m timeit ...- kein Effekt (einschließlich 3.4). Das Verhalten in Ihrer Antwort ist reproduzierbar, wenn Python aus dem Quellcode kompiliert wird (z. B. 3.6.4-d48eceb, aber keine Auswirkung auf 3.7-e3256087)
jfs
7

Die erste Frage hier muss sein, ist es reproduzierbar? Zumindest für einige von uns ist es definitiv so, obwohl andere Leute sagen, dass sie den Effekt nicht sehen. Dies bei Fedora, bei dem der Gleichheitstest dahingehend geändert wurde, dass istatsächlich ein Vergleich durchgeführt wird, scheint für das Ergebnis irrelevant zu sein, und der Bereich wurde auf 200.000 erhöht, da dies den Effekt zu maximieren scheint:

$ python3 -m timeit "a = tuple(range(200000));  b = tuple(range(200000)); a is b"
100 loops, best of 3: 7.03 msec per loop
$ python3 -m timeit "a = tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.2 msec per loop
$ python3 -m timeit "tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.2 msec per loop
$ python3 -m timeit "a = b = tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 9.99 msec per loop
$ python3 -m timeit "a = b = tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.2 msec per loop
$ python3 -m timeit "tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.1 msec per loop
$ python3 -m timeit "a = tuple(range(200000));  b = tuple(range(200000)); a is b"
100 loops, best of 3: 7 msec per loop
$ python3 -m timeit "a = tuple(range(200000));  b = tuple(range(200000)); a is b"
100 loops, best of 3: 7.02 msec per loop

Ich stelle fest, dass Variationen zwischen den Läufen und der Reihenfolge, in der die Ausdrücke ausgeführt werden, für das Ergebnis kaum einen Unterschied machen.

Das Hinzufügen von Zuweisungen zu aund bin die langsame Version beschleunigt dies nicht. Wie zu erwarten ist, hat die Zuweisung zu lokalen Variablen vernachlässigbare Auswirkungen. Das einzige, was es beschleunigt, ist, den Ausdruck vollständig in zwei Teile zu teilen. Der einzige Unterschied, den dies machen sollte, besteht darin, dass die maximale Stapeltiefe, die Python bei der Auswertung des Ausdrucks verwendet, verringert wird (von 4 auf 3).

Das gibt uns den Hinweis, dass der Effekt mit der Stapeltiefe zusammenhängt. Vielleicht schiebt die zusätzliche Ebene den Stapel auf eine andere Speicherseite. Wenn ja, sollten wir sehen, dass sich andere Änderungen, die sich auf den Stapel auswirken, ändern (höchstwahrscheinlich den Effekt beenden), und tatsächlich sehen wir Folgendes:

$ python3 -m timeit -s "def foo():
   tuple(range(200000)) is tuple(range(200000))" "foo()"
100 loops, best of 3: 10 msec per loop
$ python3 -m timeit -s "def foo():
   tuple(range(200000)) is tuple(range(200000))" "foo()"
100 loops, best of 3: 10 msec per loop
$ python3 -m timeit -s "def foo():
   a = tuple(range(200000));  b = tuple(range(200000)); a is b" "foo()"
100 loops, best of 3: 9.97 msec per loop
$ python3 -m timeit -s "def foo():
   a = tuple(range(200000));  b = tuple(range(200000)); a is b" "foo()"
100 loops, best of 3: 10 msec per loop

Ich denke also, dass der Effekt ausschließlich darauf zurückzuführen ist, wie viel Python-Stack während des Timing-Prozesses verbraucht wird. Es ist immer noch komisch.

Duncan
quelle
2 Computer mit denselben Memory Sticks und demselben Betriebssystem führen jedoch zu unterschiedlichen Ergebnissen. Die Stapeltiefe klingt nach einer guten Theorie, erklärt aber nicht den Unterschied zwischen Maschinen.
Bharel