Frage Ist

Ich lese ein Buch, wo der Autor das sagt if( a < 901 ) ist schneller als if( a <= 900 ).

Nicht genau wie in diesem einfachen Beispiel, aber es gibt geringfügige Leistungsänderungen im komplexen Loop-Code. Ich nehme an, dass dies etwas mit dem generierten Maschinencode zu tun hat, falls es überhaupt wahr ist.


1372
2017-08-27 02:10


Ursprung


Antworten:


Nein, auf den meisten Architekturen wird es nicht schneller sein. Sie haben nicht angegeben, aber auf x86 werden alle Integralvergleiche normalerweise in zwei Maschinenbefehlen implementiert:

  • EIN test oder cmp Anweisung, die setzt EFLAGS
  • Und ein Jcc (Sprung) Anweisung, abhängig vom Vergleichstyp (und Code-Layout):
    • jne - Springe, wenn nicht gleich -> ZF = 0
    • jz - Springe wenn Null (gleich) -> ZF = 1
    • jg - Springe wenn größer -> ZF = 0 and SF = OF
    • (etc...)

Beispiel (Bearbeitet für die Kürze) Kompiliert mit $ gcc -m32 -S -masm=intel test.c

    if (a < b) {
        // Do something 1
    }

Kompiliert zu:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jge     .L2                          ; jump if a is >= b
    ; Do something 1
.L2:

Und

    if (a <= b) {
        // Do something 2
    }

Kompiliert zu:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jg      .L5                          ; jump if a is > b
    ; Do something 2
.L5:

Der einzige Unterschied zwischen den beiden ist a jg gegen a jge Anweisung. Die beiden brauchen die gleiche Zeit.


Ich möchte den Kommentar ansprechen, dass nichts darauf hinweist, dass die verschiedenen Sprunganweisungen die gleiche Zeit benötigen. Dieser ist ein wenig schwierig zu beantworten, aber hier ist, was ich geben kann: In der Intel Befehlssatz Referenzsind sie alle unter einer gemeinsamen Anweisung zusammengefasst, Jcc (Springe, wenn die Bedingung erfüllt ist). Die gleiche Gruppierung wird zusammen unter der Referenzhandbuch zur Optimierung, in Anhang C. Latenz und Durchsatz.

Latenz - Die Anzahl der Taktzyklen, die für die   Ausführungskern, um die Ausführung aller μops, die gebildet werden, zu vervollständigen   eine Anweisung.

Durchsatz - Die Anzahl der erforderlichen Taktzyklen   Warten Sie, bis die Ausgabeports frei sind, die gleiche Anweisung zu akzeptieren   nochmal. Für viele Anweisungen kann der Durchsatz eines Befehls sein   deutlich weniger als seine Latenz

Die Werte für Jcc sind:

      Latency   Throughput
Jcc     N/A        0.5

mit der folgenden Fußnote auf Jcc:

7) Die Auswahl von bedingten Sprungbefehlen sollte auf der Empfehlung von Abschnitt 3.4.1, "Verzweigungsvorhersage-Optimierung" basieren, um die Vorhersagbarkeit von Verzweigungen zu verbessern. Wenn Verzweigungen erfolgreich vorhergesagt werden, wird die Latenz von jcc ist effektiv Null.

Also, nichts in den Intel Docs behandelt jemals einen Jcc Belehrung anders als die anderen.

Wenn man über die tatsächliche Schaltung nachdenkt, die zum Implementieren der Befehle verwendet wird, kann man annehmen, dass es einfache AND / OR-Gatter auf den verschiedenen Bits geben würde EFLAGS, um festzustellen, ob die Bedingungen erfüllt sind. Es gibt dann keinen Grund, dass ein Befehl, der zwei Bits testet, mehr oder weniger Zeit benötigt als einer, der nur einen prüft (Ignorieren der Gatterausbreitungsverzögerung, die viel kürzer ist als die Taktperiode).


Bearbeiten: Gleitpunkt

Dies gilt auch für den Gleitpunkt von x87: (So ziemlich der gleiche Code wie oben, aber mit double Anstatt von int.)

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; Compare ST(0) and ST(1), and set CF, PF, ZF in EFLAGS
        fstp    st(0)
        seta    al                     ; Set al if above (CF=0 and ZF=0).
        test    al, al
        je      .L2
        ; Do something 1
.L2:

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; (same thing as above)
        fstp    st(0)
        setae   al                     ; Set al if above or equal (CF=0).
        test    al, al
        je      .L5
        ; Do something 2
.L5:
        leave
        ret

1570
2017-08-27 02:13



Historisch gesehen (wir reden über die 1980er und die frühen 1990er Jahre) gab es etwas Architekturen, in denen das stimmte. Das Grundproblem besteht darin, dass der Ganzzahlvergleich inhärent über ganzzahlige Subtraktionen implementiert wird. Dies führt zu folgenden Fällen.

Comparison     Subtraction
----------     -----------
A < B      --> A - B < 0
A = B      --> A - B = 0
A > B      --> A - B > 0

Jetzt, wenn A < B die Subtraktion muss ein High-Bit für die Subtraktion ausleihen, um korrekt zu sein, genau wie Sie tragen und borgen, wenn Sie von Hand addieren und subtrahieren. Dieses "geliehene" Bit wurde normalerweise als das Bit tragen und wäre durch einen Verzweigungsbefehl testbar. Ein zweites Bit namens Nullbit würde gesetzt werden, wenn die Subtraktion identisch Null wäre, was Gleichheit implizierte.

Gewöhnlich gab es mindestens zwei bedingte Verzweigungsbefehle, einen zum Verzweigen auf das Übertragsbit und einen zum Null-Bit.

Um nun den Kern der Sache zu verstehen, erweitern wir die vorhergehende Tabelle, um die Übertrags- und Null-Bit-Ergebnisse einzubeziehen.

Comparison     Subtraction  Carry Bit  Zero Bit
----------     -----------  ---------  --------
A < B      --> A - B < 0    0          0
A = B      --> A - B = 0    1          1
A > B      --> A - B > 0    1          0

Also, eine Verzweigung für implementieren A < B kann in einer Anweisung erfolgen, weil das Übertragsbit gelöscht ist nur in diesem Fall, das heißt,

;; Implementation of "if (A < B) goto address;"
cmp  A, B          ;; compare A to B
bcz  address       ;; Branch if Carry is Zero to the new address

Wenn wir jedoch einen Vergleich, der weniger als gleich ist, durchführen wollen, müssen wir eine zusätzliche Überprüfung des Null-Flags durchführen, um den Fall der Gleichheit zu erfassen.

;; Implementation of "if (A <= B) goto address;"
cmp A, B           ;; compare A to B
bcz address        ;; branch if A < B
bzs address        ;; also, Branch if the Zero bit is Set

Also, auf einigen Maschinen, mit einem "weniger als" Vergleich Macht sparen eine Maschinenanweisung. Dies war in der Ära der Sub-Megahertz-Prozessorgeschwindigkeit und der 1: 1-CPU-zu-Speicher-Geschwindigkeitsverhältnisse relevant, aber heutzutage ist es fast völlig irrelevant.


555
2017-08-27 17:53



Wenn wir von internen Integer-Typen sprechen, gibt es keinen möglichen Weg, schneller als der andere zu sein. Sie sind offensichtlich semantisch identisch. Beide bitten den Compiler genau dasselbe zu tun. Nur ein fürchterlich zerbrochener Compiler würde einen minderwertigen Code für einen von diesen erzeugen.

Wenn es eine Plattform gab wo < war schneller als <= für einfache Integer-Typen sollte der Compiler immer Konvertieren <= zu < für Konstanten. Jeder Compiler, der das nicht getan hat, wäre nur ein schlechter Compiler (für diese Plattform).


85
2017-08-27 02:31



Ich sehe, dass keiner schneller ist. Der Compiler generiert den gleichen Maschinencode in jeder Bedingung mit einem anderen Wert.

if(a < 901)
cmpl  $900, -4(%rbp)
jg .L2

if(a <=901)
cmpl  $901, -4(%rbp)
jg .L3

Mein Beispiel if ist von GCC auf x86_64-Plattform unter Linux.

Compiler-Autoren sind ziemlich schlaue Leute, und sie denken an diese Dinge und viele andere, die die meisten von uns für selbstverständlich halten.

Ich habe festgestellt, dass, wenn es keine Konstante ist, in beiden Fällen derselbe Maschinencode generiert wird.

int b;
if(a < b)
cmpl  -4(%rbp), %eax
jge   .L2

if(a <=b)
cmpl  -4(%rbp), %eax
jg .L3

67
2017-08-27 02:16



Für Fließkomma-Code kann der <= Vergleich tatsächlich sogar auf modernen Architekturen langsamer sein (durch einen Befehl). Hier ist die erste Funktion:

int compare_strict(double a, double b) { return a < b; }

Auf PowerPC führt dies zuerst einen Gleitkommavergleich durch (der aktualisiert wird) cr, das Bedingungsregister), verschiebt dann das Bedingungsregister zu einem GPR, verschiebt das Bit "verglichen mit weniger als" an Stelle und kehrt dann zurück. Es dauert vier Anweisungen.

Betrachten Sie stattdessen diese Funktion:

int compare_loose(double a, double b) { return a <= b; }

Dies erfordert die gleiche Arbeit wie compare_strict oben, aber jetzt gibt es zwei Bits von Interesse: "war weniger als" und "war gleich". Dies erfordert eine zusätzliche Anweisung (cror- Bedingungsregister bitweise ODER), um diese beiden Bits zu einem zu kombinieren. Damit compare_loose benötigt fünf Anweisungen, während compare_strict benötigt vier.

Sie könnten denken, dass der Compiler die zweite Funktion wie folgt optimieren könnte:

int compare_loose(double a, double b) { return ! (a > b); }

Dies wird jedoch nicht korrekt mit NaNs umgehen. NaN1 <= NaN2 und NaN1 > NaN2 müssen beide zu falsch auswerten.


48
2017-08-27 18:32



Vielleicht hat der Autor dieses unbenannten Buches das gelesen a > 0 läuft schneller als a >= 1 und denkt, dass das universal wahr ist.

Aber es ist weil a 0 ist beteiligt (weil CMP kann, abhängig von der Architektur, z.B. mit OR) und nicht wegen der <.


34
2017-08-27 13:05



Zumindest könnte, wenn das der Fall wäre, ein Compiler trivialerweise ein <= b zu! (A> b) optimieren, und selbst wenn der Vergleich selbst tatsächlich langsamer wäre, würden Sie mit Ausnahme des naivsten Compilers keinen Unterschied bemerken .


29
2017-08-27 09:23



Sie haben die gleiche Geschwindigkeit. Vielleicht in einer speziellen Architektur, was er / sie gesagt hat, ist richtig, aber in der x86-Familie weiß ich zumindest, dass sie gleich sind. Weil die CPU dafür eine Subtraktion (a - b) durchführt und dann die Flags des Flag-Registers überprüft. Zwei Bits dieses Registers werden ZF (Null-Flag) und SF (Vorzeichen-Flag) genannt, und dies geschieht in einem Zyklus, da dies mit einer Maskenoperation geschieht.


15
2017-08-27 08:25



Dies hängt stark von der zugrunde liegenden Architektur ab, zu der das C kompiliert wird. Einige Prozessoren und Architekturen können explizite Anweisungen für gleich oder weniger als und gleich haben, die in unterschiedlichen Zyklenzahlen ausgeführt werden.

Das wäre jedoch ziemlich ungewöhnlich, da der Compiler es umgehen könnte, was es irrelevant macht.


13
2017-08-27 02:15



Andere Antworten haben sich darauf konzentriert x86 Architektur, und ich weiß nicht ARM Architektur (die Ihr Beispiel-Assembler zu sein scheint) gut genug, um speziell auf den erzeugten Code zu kommentieren, aber dies ist ein Beispiel für eine Mikro-Optimierung welche ist sehr architekturspezifisch und ist es als wahrscheinlich eine Anti-Optimierung, wie es eine Optimierung sein soll.

Als solche würde ich vorschlagen, dass diese Art von Mikro-Optimierung ist ein Beispiel für Frachtkult Programmierung statt beste Software-Engineering-Praxis.

Es gibt wahrscheinlich etwas Architekturen, wo dies eine Optimierung ist, aber ich kenne mindestens eine Architektur, wo das Gegenteil wahr sein kann. Der ehrwürdige Transputer Architektur hatte nur Maschinencode Anweisungen für gleich und größer als oder gleich wie, so mussten alle Vergleiche aus diesen Primitiven aufgebaut werden.

Auch dann konnte der Compiler in fast allen Fällen die Auswertungsanweisungen so ordnen, dass in der Praxis kein Vergleich einen Vorteil gegenüber einem anderen hatte. Im schlimmsten Fall muss jedoch möglicherweise eine umgekehrte Anweisung (REV) hinzugefügt werden, um die beiden obersten Elemente der Operandenstapel. Dies war ein Ein-Byte-Befehl, der einen einzigen Zyklus brauchte, um laufen zu können, und somit den geringsten Overhead, der möglich war.

Ob eine Micro-Optimierung wie diese ist oder nicht Optimierung oder Anti-Optimierung hängt von der spezifischen Architektur ab, die Sie verwenden, daher ist es normalerweise eine schlechte Idee, sich an Architektur-spezifische Mikrooptimierungen zu gewöhnen, andernfalls könnten Sie instinktiv eine verwenden, wenn dies nicht angemessen ist, und es sieht so aus Was das Buch, das Sie lesen, befürwortet.


10
2017-08-31 18:33