Ist "x <y <z" schneller als "x <y und y <z"?

129

Von dieser Seite wissen wir, dass:

Verkettete Vergleiche sind schneller als mit dem andOperator. Schreiben x < y < zstatt x < y and y < z.

Ich habe jedoch ein anderes Ergebnis beim Testen der folgenden Codefragmente erhalten:

$ python -m timeit "x = 1.2" "y = 1.3" "z = 1.8" "x < y < z"
1000000 loops, best of 3: 0.322 usec per loop
$ python -m timeit "x = 1.2" "y = 1.3" "z = 1.8" "x < y and y < z"
1000000 loops, best of 3: 0.22 usec per loop
$ python -m timeit "x = 1.2" "y = 1.3" "z = 1.1" "x < y < z"
1000000 loops, best of 3: 0.279 usec per loop
$ python -m timeit "x = 1.2" "y = 1.3" "z = 1.1" "x < y and y < z"
1000000 loops, best of 3: 0.215 usec per loop

Es scheint, dass x < y and y < zdas schneller ist als x < y < z. Warum?

Nachdem ich einige Beiträge auf dieser Site durchsucht habe (wie diese hier ), weiß ich, dass "nur einmal bewertet" der Schlüssel ist x < y < z, aber ich bin immer noch verwirrt. Um weitere Studien durchzuführen, habe ich diese beiden Funktionen mit dis.disfolgenden Komponenten zerlegt :

import dis

def chained_compare():
        x = 1.2
        y = 1.3
        z = 1.1
        x < y < z

def and_compare():
        x = 1.2
        y = 1.3
        z = 1.1
        x < y and y < z

dis.dis(chained_compare)
dis.dis(and_compare)

Und die Ausgabe ist:

## chained_compare ##

  4           0 LOAD_CONST               1 (1.2)
              3 STORE_FAST               0 (x)

  5           6 LOAD_CONST               2 (1.3)
              9 STORE_FAST               1 (y)

  6          12 LOAD_CONST               3 (1.1)
             15 STORE_FAST               2 (z)

  7          18 LOAD_FAST                0 (x)
             21 LOAD_FAST                1 (y)
             24 DUP_TOP
             25 ROT_THREE
             26 COMPARE_OP               0 (<)
             29 JUMP_IF_FALSE_OR_POP    41
             32 LOAD_FAST                2 (z)
             35 COMPARE_OP               0 (<)
             38 JUMP_FORWARD             2 (to 43)
        >>   41 ROT_TWO
             42 POP_TOP
        >>   43 POP_TOP
             44 LOAD_CONST               0 (None)
             47 RETURN_VALUE

## and_compare ##

 10           0 LOAD_CONST               1 (1.2)
              3 STORE_FAST               0 (x)

 11           6 LOAD_CONST               2 (1.3)
              9 STORE_FAST               1 (y)

 12          12 LOAD_CONST               3 (1.1)
             15 STORE_FAST               2 (z)

 13          18 LOAD_FAST                0 (x)
             21 LOAD_FAST                1 (y)
             24 COMPARE_OP               0 (<)
             27 JUMP_IF_FALSE_OR_POP    39
             30 LOAD_FAST                1 (y)
             33 LOAD_FAST                2 (z)
             36 COMPARE_OP               0 (<)
        >>   39 POP_TOP
             40 LOAD_CONST               0 (None)

Es scheint, dass der x < y and y < zBefehl weniger uneinheitlich ist als x < y < z. Sollte ich x < y and y < zschneller überlegen als x < y < z?

Getestet mit Python 2.7.6 auf einer Intel (R) Xeon (R) CPU E5640 bei 2,67 GHz.

zangw
quelle
8
Mehr zerlegte Befehle bedeuten weder mehr Komplexität noch langsameren Code. Als ich jedoch Ihre timeitTests sah, interessierte ich mich dafür.
Marco Bonelli
6
Ich nahm an, dass der Geschwindigkeitsunterschied zu "einmal ausgewertet" auftritt, wenn yes sich nicht nur um eine variable Suche handelt, sondern um einen teureren Prozess wie einen Funktionsaufruf. Dh 10 < max(range(100)) < 15ist schneller als 10 < max(range(100)) and max(range(100)) < 15weil max(range(100))für beide Vergleiche einmal aufgerufen wird.
zehnpaard
2
@MarcoBonelli Dies ist der Fall, wenn der zerlegte Code 1) keine Schleifen enthält und 2) jeder einzelne Bytecode sehr, sehr schnell ist, da an diesem Punkt der Overhead der Hauptschleife erheblich wird.
Bakuriu
2
Die Verzweigungsvorhersage kann Ihre Tests durcheinander bringen.
Corey Ogburn
2
@zehnpaard Ich stimme dir zu. Wenn "y" mehr als ein einfacher Wert ist (z. B. ein Funktionsaufruf oder eine Berechnung), würde ich erwarten, dass die Tatsache, dass "y" einmal in x <y <z ausgewertet wird, einen viel deutlicheren Einfluss hat. In dem dargestellten Fall befinden wir uns innerhalb der Fehlerbalken: Die Auswirkungen der (fehlgeschlagenen) Verzweigungsvorhersage, des nicht optimalen Bytecodes und anderer plattform- / CPU-spezifischer Effekte dominieren. Dies macht die allgemeine Regel, dass eine einmalige Bewertung besser ist (und auch besser lesbar ist), nicht ungültig, zeigt jedoch, dass dies im Extremfall möglicherweise nicht so viel Wert bringt.
MartyMacGyver

Antworten:

111

Der Unterschied besteht darin, dass in x < y < z ynur einmal ausgewertet wird. Dies macht keinen großen Unterschied, wenn y eine Variable ist, aber es ist, wenn es sich um einen Funktionsaufruf handelt, dessen Berechnung einige Zeit in Anspruch nimmt.

from time import sleep
def y():
    sleep(.2)
    return 1.3
%timeit 1.2 < y() < 1.8
10 loops, best of 3: 203 ms per loop
%timeit 1.2 < y() and y() < 1.8
1 loops, best of 3: 405 ms per loop
rauben
quelle
18
Natürlich könnte es auch einen semantischen Unterschied geben. Y () könnte nicht nur zwei verschiedene Werte zurückgeben, sondern mit einer Variablen könnte die Auswertung des Operators kleiner als in x <y den Wert von y ändern. Aus diesem Grund wird es im Bytecode häufig nicht optimiert (wenn y beispielsweise eine nicht lokale Variable ist oder an einem Abschluss
teilnimmt
Nur neugierig, warum brauchten Sie eine sleep()Insider-Funktion?
Prof
@Prof Das heißt, eine Funktion zu simulieren, deren Berechnung einige Zeit in Anspruch nimmt. Wenn die Funktionen sofort zurückkehren, gibt es keinen großen Unterschied zwischen den beiden Zeitergebnissen.
Rob
@Rob Warum sollte es keinen großen Unterschied geben? Es wären 3 ms gegen 205 ms, das zeigt es gut genug, nicht wahr?
Prof
@Prof Sie vermissen den Punkt, dass y () zweimal berechnet wird, also 2x200ms statt 1x200ms. Der Rest (3/5 ms) ist irrelevantes Rauschen bei der Zeitmessung.
Rob
22

Optimaler Bytecode für beide von Ihnen definierten Funktionen wäre

          0 LOAD_CONST               0 (None)
          3 RETURN_VALUE

weil das Ergebnis des Vergleichs nicht verwendet wird. Machen wir die Situation interessanter, indem wir das Ergebnis des Vergleichs zurückgeben. Lassen Sie uns auch das Ergebnis zur Kompilierungszeit nicht erkennbar machen.

def interesting_compare(y):
    x = 1.1
    z = 1.3
    return x < y < z  # or: x < y and y < z

Auch hier sind die beiden Versionen des Vergleichs semantisch identisch, sodass der optimale Bytecode für beide Konstrukte gleich ist. So gut ich es herausfinden kann, würde es so aussehen. Ich habe jede Zeile vor und nach jedem Opcode in der Forth-Notation mit dem Stapelinhalt versehen (oben auf dem Stapel rechts, --vor und nach geteilt, nachfolgend ?zeigt etwas an, das möglicherweise vorhanden ist oder nicht). Beachten Sie, dass RETURN_VALUEalles, was sich auf dem Stapel befindet, unter dem zurückgegebenen Wert verworfen wird.

          0 LOAD_FAST                0 (y)    ;          -- y
          3 DUP_TOP                           ; y        -- y y
          4 LOAD_CONST               0 (1.1)  ; y y      -- y y 1.1
          7 COMPARE_OP               4 (>)    ; y y 1.1  -- y pred
         10 JUMP_IF_FALSE_OR_POP     19       ; y pred   -- y
         13 LOAD_CONST               1 (1.3)  ; y        -- y 1.3
         16 COMPARE_OP               0 (<)    ; y 1.3    -- pred
     >>  19 RETURN_VALUE                      ; y? pred  --

Wenn eine Implementierung der Sprache CPython, PyPy, was auch immer, diesen Bytecode (oder seine eigene äquivalente Abfolge von Operationen) nicht für beide Variationen generiert , zeigt dies die schlechte Qualität dieses Bytecode-Compilers . Das Abrufen der Bytecode-Sequenzen, die Sie oben gepostet haben, ist ein gelöstes Problem (ich denke, alles, was Sie für diesen Fall benötigen, ist ständiges Falten , Eliminierung von totem Code und bessere Modellierung des Inhalts des Stapels; die Eliminierung von allgemeinen Unterausdrücken wäre ebenfalls billig und wertvoll ), und es gibt wirklich keine Entschuldigung dafür, dies in einer modernen Sprachimplementierung nicht zu tun.

Nun kommt es vor, dass alle aktuellen Implementierungen der Sprache Bytecode-Compiler von schlechter Qualität haben. Aber das sollten Sie beim Codieren ignorieren ! Stellen Sie sich vor, der Bytecode-Compiler sei gut und schreiben Sie den am besten lesbaren Code. Es wird wahrscheinlich sowieso schnell genug sein. Wenn dies nicht der Fall ist, suchen Sie zuerst nach algorithmischen Verbesserungen und versuchen Sie es dann mit Cython. Dies bietet bei gleichem Aufwand weitaus mehr Verbesserungen als alle Optimierungen auf Ausdrucksebene, die Sie möglicherweise anwenden.

zwol
quelle
Nun, die wichtigste aller Optimierungen müsste überhaupt möglich sein: Inlining. Und das ist alles andere als ein "gelöstes Problem" für dynamische Sprachen, die es ermöglichen, die Implementierung einer Funktion dynamisch zu ändern (machbar - HotSpot kann ähnliche Dinge tun, und Graal arbeitet daran, diese Art von Optimierungen für Python und andere dynamische Sprachen verfügbar zu machen ). Und da die Funktion selbst möglicherweise von verschiedenen Modulen aufgerufen wird (oder ein Aufruf dynamisch generiert wird!), Können Sie diese Optimierungen dort wirklich nicht durchführen.
Voo
1
@Voo Mein handoptimierter Bytecode hat auch bei beliebiger Dynamik genau die gleiche Semantik wie das Original (eine Ausnahme: a <b ≡ b> a wird angenommen). Auch Inlining wird überbewertet. Wenn Sie zu viel davon tun - und es ist viel zu einfach, zu viel davon zu tun -, sprengen Sie den I-Cache und verlieren alles, was Sie gewonnen haben, und noch mehr.
zwol
Sie haben Recht, ich dachte, Sie wollten Ihren interesting_compareeinfachen Bytecode oben optimieren (der nur mit Inlining funktionieren würde). Völlig offtopic aber: Inlining ist eine der wichtigsten Optimierungen für jeden Compiler. Sie können versuchen, einige Benchmarks mit beispielsweise HotSpot für echte Programme auszuführen (nicht einige Mathe-Tests, die 99% ihrer Zeit in einer von Hand optimierten Hot-Schleife verbringen [und daher sowieso keine Funktionsaufrufe mehr haben]), wenn Sie diese deaktivieren Fähigkeit, alles zu inline - Sie werden große Regressionen sehen.
Voo
@Voo Ja, der einfache Bytecode oben sollte die "optimale Version" des ursprünglichen Codes des OP sein, nicht interesting_compare.
zwol
"eine Ausnahme: a <b ≡ b> a wird angenommen" → was in Python einfach nicht wahr ist. Außerdem kann CPython nicht einmal wirklich davon ausgehen, dass Operationen yden Stack nicht ändern, da es viele Debug-Tools enthält.
Veedrac
8

Da der Unterschied in der Ausgabe auf mangelnde Optimierung zurückzuführen zu sein scheint, sollten Sie diesen Unterschied in den meisten Fällen ignorieren - es könnte sein, dass der Unterschied verschwindet. Der Unterschied besteht darin, dass ynur einmal ausgewertet werden sollte und dies durch Duplizieren auf dem Stapel gelöst wird, was eine zusätzliche POP_TOPLösung erfordertLOAD_FAST könnte jedoch möglich sein.

Der wichtige Unterschied ist jedoch, dass in x<y and y<zder zweiten yzweimal x<ybewertet werden sollte, wenn als wahr bewertet wird, dies hat Auswirkungen, wenn die Bewertung vony viel Zeit nimmt oder Nebenwirkungen hat.

In den meisten Szenarien sollten Sie verwenden, x<y<zobwohl es etwas langsamer ist.

Himmel König
quelle
6

Erstens ist Ihr Vergleich so gut wie bedeutungslos, da die beiden verschiedenen Konstrukte nicht eingeführt wurden, um eine Leistungsverbesserung zu erzielen. Sie sollten sich daher nicht entscheiden, ob Sie eines anstelle des anderen verwenden möchten.

Das x < y < zKonstrukt:

  1. Ist klarer und direkter in seiner Bedeutung.
  2. Seine Semantik ist das, was man von dem „mathematischen Sinne“ des Vergleichs erwarten würde: evalute x, yund z einmal und prüfen , ob der gesamte Zustand hält. Durch anddie Verwendung wird die Semantik durch ymehrmaliges Auswerten geändert , wodurch sich das Ergebnis ändern kann .

Wählen Sie also eine anstelle der anderen, abhängig von der gewünschten Semantik und, wenn sie gleichwertig sind, ob eine besser lesbar ist als die andere.

Dies bedeutet: Mehr zerlegter Code bedeutet nicht langsameren Code. Das Ausführen von mehr Bytecode-Operationen bedeutet jedoch, dass jede Operation einfacher ist und dennoch eine Iteration der Hauptschleife erfordert. Dies bedeutet, dass der Aufwand für die Ausführung weiterer Bytecode-Operationen von Bedeutung sein kann , wenn die von Ihnen ausgeführten Vorgänge extrem schnell sind (z. B. die Suche nach lokalen Variablen, wie Sie sie dort ausführen).

Beachten Sie jedoch, dass dieses Ergebnis nicht für die allgemeinere Situation gilt, sondern nur für den "schlimmsten Fall", den Sie zufällig profilieren. Wie andere angemerkt haben, wenn Sie sich änderny die Ergebnisse ändern zu etwas , das noch etwas länger dauert, da die verkettete Notation sie nur einmal auswertet.

Zusammenfassend:

  • Berücksichtigen Sie die Semantik vor der Ausführung.
  • Lesbarkeit berücksichtigen.
  • Vertraue keinen Mikro-Benchmarks. Profilieren Sie immer mit verschiedenen Parametern, um zu sehen, wie sich ein Funktions- / Ausdrucks-Timing in Bezug auf diese Parameter verhält, und überlegen Sie, wie Sie es verwenden möchten.
Bakuriu
quelle
5
Ich denke, Ihre Antwort enthält nicht die einfache und relevante Tatsache, dass die zitierte Seite im speziellen Fall der Frage - Floats vergleichen - einfach falsch ist. Der verkettete Vergleich ist nicht schneller, wie bei beiden Messungen und im generierten Bytecode zu sehen ist.
pvg
30
Die Beantwortung einer Frage mit der Aufschrift "Vielleicht sollten Sie nicht so viel über Leistung nachdenken" scheint mir nicht nützlich zu sein. Sie machen potenziell bevormundende Annahmen über das Verständnis des Fragestellers für allgemeine Programmierprinzipien und sprechen dann hauptsächlich über diese anstatt über das vorliegende Problem.
Ben Millwood
@Veerdac du liest den Kommentar falsch. Die vorgeschlagene Optimierung in dem Originaldokument, auf das sich das OP stützte, ist falsch, zumindest bei Floats. Es ist nicht schneller.
pvg