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


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 schneller ist als der Einsatz eines Einstrichs mit temporären Variablen um mehr als 27%?

In den Python-Dokumenten ist die Garbage-Collection während des Tages deaktiviert, so dass dies nicht möglich ist. Ist es eine Art Optimierung?

Die Ergebnisse können in Python 2.x auch in geringerem Maße reproduziert werden.

Running Windows 7, CPython 3.5.1, Intel i7 3.40 GHz, 64-Bit-Betriebssystem und Python. Scheint wie eine andere Maschine, die ich versucht habe, bei Intel i7 3.60 GHz mit Python 3.5.0 läuft nicht reproduziert die Ergebnisse.


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


75
2018-04-11 12:19


Ursprung


Antworten:


Meine Ergebnisse waren ähnlich wie bei Ihnen: Der Code, der Zwischenvariablen verwendete, war in der Python 3.4-Version ziemlich gleichmäßig um mindestens 10-20% schneller. Wenn ich jedoch IPython für denselben 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

Bemerkenswerterweise habe ich es nie geschafft, die 74,2 μs für das erste Mal zu erreichen, als ich es benutzte -mtimeit von der Befehlszeile aus.

Also hat sich dieser Heisenbug als ziemlich interessant herausgestellt. Ich entschied mich, den Befehl mit auszuführen strace und tatsächlich ist etwas Fischiges los:

% 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

Nun, das ist ein guter Grund für den Unterschied. Der Code, der keine Variablen verwendet, verursacht den mmap Systemaufruf wird fast 1000x mehr als der, der Zwischenvariablen verwendet aufgerufen.

Das withoutvars ist voll von mmap/munmap fü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

Das mmap Anruf scheint von der Funktion zu kommen _PyObject_ArenaMmap von Objects/obmalloc.c; das obmalloc.c enthält auch das Makro ARENA_SIZE, welches ist #defined sein (256 << 10) (das ist 262144); ähnlich der munmap passt zu den _PyObject_ArenaMunmap von obmalloc.c.

obmalloc.c sagt, dass

Vor Python 2.5 waren Arenas nie free()"Ed. Beginnend mit Python 2.5,   Wir versuchen es free() Arenen, und verwenden Sie einige milde heuristische Strategien, um zu erhöhen   die Wahrscheinlichkeit, dass Arenen irgendwann frei werden.

Daher führen diese Heuristiken und die Tatsache, dass Python Object Allocator diese freien Arenen freigibt, sobald sie geleert werden, dazu python3 -mtimeit 'tuple(range(2000)) == tuple(range(2000))' Auslösen pathologischen Verhaltens, wobei ein 256 kB-Speicherbereich wiederholt zugewiesen und wieder freigegeben wird; und diese Zuordnung geschieht mit mmap/munmap, die bei Systemaufrufen vergleichsweise teuer sind - mmap mit MAP_ANONYMOUS erfordert, dass die neu gemappten Seiten auf Null gesetzt werden müssen - auch wenn es Python egal ist.

Das Verhalten ist im Code, der Zwischenvariablen verwendet, nicht vorhanden, da es leicht verwendet wird Mehr Speicher und keine Speicherarena können freigegeben werden, da einige Objekte noch darin zugeordnet sind. Das ist, weil timeit wird es zu einer Schleife machen, die nicht unähnlich ist

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

Jetzt ist das Verhalten beides aund b bleibt gebunden, bis sie * neu zugewiesen sind, also in der zweiten Iteration, tuple(range(2000)) wird ein drittes Tupel und die Zuweisung zuweisen a = tuple(...) wird die Referenzzahl des alten Tupels verringern, wodurch es freigegeben wird, und die Referenzzahl des neuen Tupels erhöhen; dann passiert das gleiche b. Daher gibt es nach der ersten Iteration immer mindestens 2 dieser Tupel, wenn nicht 3, so dass das Thrashing nicht auftritt.

Vor allem kann nicht garantiert werden, dass der Code, der Zwischenvariablen verwendet, immer schneller ist - in einigen Setups kann es sogar sein, dass die Verwendung von Zwischenvariablen zu zusätzlichen Ergebnissen führt mmap Aufrufe, während der Code, der Rückgabewerte direkt vergleicht, in Ordnung sein kann.


Jemand fragte, warum das passiert, wann timeit Deaktiviert die Garbage Collection. Es stimmt tatsächlich, dass timeit macht es:

Hinweis

Standardmäßig, timeit() deaktiviert die Garbage Collection während des Timings vorübergehend. Der Vorteil dieses Ansatzes ist, dass unabhängige Zeitabläufe besser vergleichbar sind. Dieser Nachteil besteht darin, dass GC eine wichtige Komponente der Leistung der zu messenden Funktion sein kann. Wenn dies der Fall ist, kann GC als erste Anweisung in der Setup-Zeichenfolge erneut aktiviert werden. Beispielsweise:

Der Garbage Collector von Python ist jedoch nur zum Wiederherstellen da zyklischer MüllSammlungen 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.


101
2018-04-11 13:08



Die erste Frage muss sein, ist es reproduzierbar? Für einige von uns zumindest ist es definitiv, obwohl andere Leute sagen, dass sie die Wirkung nicht sehen. Dies auf Fedora, mit dem Gleichheitstest geändert zu is tatsächlich scheint ein Vergleich für das Ergebnis irrelevant zu sein, und die Reichweite stieg auf 200.000, 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 bemerke, dass Variationen zwischen den Läufen und die Reihenfolge, in der die Ausdrücke ausgeführt werden, sehr wenig Unterschied für das Ergebnis machen.

Hinzufügen von Zuweisen zu aund b in die langsame Version beschleunigt es nicht. In der Tat, wie wir erwarten könnten, hat die Zuweisung zu lokalen Variablen einen vernachlässigbaren Effekt. Die einzige Sache, die es beschleunigt, teilt den Ausdruck vollständig in zwei. Der einzige Unterschied, den dies machen sollte, ist, dass es die maximale Stapeltiefe reduziert, die von Python verwendet wird, während der Ausdruck ausgewertet wird (von 4 auf 3).

Das gibt uns den Hinweis, dass der Effekt mit der Stack-Tiefe zusammenhängt, vielleicht schiebt der Extra-Level den Stack auf eine andere Speicherseite. Wenn das der Fall ist, sollten wir sehen, dass sich andere Änderungen, die sich auf den Stack 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

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


7
2018-04-11 13:04