Ist if( a < 901 )schneller als if( a <= 900 ).

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

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

• A testoder cmpAnweisung, die setztEFLAGS
• Und eine 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
  • (usw...)

Beispiel (der Kürze halber bearbeitet) 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 also jgeine jgeAnweisung. Die beiden werden die gleiche Zeit in Anspruch nehmen.

Ich möchte auf den Kommentar eingehen, dass nichts darauf hinweist, dass die verschiedenen Sprunganweisungen dieselbe Zeit in Anspruch nehmen. Diese Frage ist etwas schwierig zu beantworten, aber ich kann Folgendes geben: In der Intel-Befehlssatzreferenz sind sie alle unter einer gemeinsamen Anweisung zusammengefasst Jcc(Springen, wenn die Bedingung erfüllt ist). Dieselbe Gruppierung wird im Optimierungsreferenzhandbuch in Anhang C zusammengefasst. Latenz und Durchsatz.

Latenz - Die Anzahl der Taktzyklen, die der Ausführungskern benötigt, um die Ausführung aller μops abzuschließen, die einen Befehl bilden.

Durchsatz - Die Anzahl der Taktzyklen, die erforderlich sind, um zu warten, bis die Issue-Ports frei sind, um denselben Befehl erneut zu akzeptieren. Bei vielen Befehlen kann der Durchsatz eines Befehls erheblich geringer sein als seine Latenz

Die Werte für Jccsind:

      Latency   Throughput
Jcc     N/A        0.5

mit folgender Fußnote zu Jcc:

7) Die Auswahl von Anweisungen für bedingte Sprünge sollte auf der Empfehlung von Abschnitt 3.4.1, „Optimierung der Verzweigungsvorhersage“ basieren, um die Vorhersagbarkeit von Verzweigungen zu verbessern. Wenn Verzweigungen erfolgreich vorhergesagt werden, ist die Latenz von jcceffektiv Null.

Nichts in den Intel-Dokumenten behandelt eine JccAnweisung jemals anders als die anderen.

Wenn man über die tatsächliche Schaltung nachdenkt, die zum Implementieren der Anweisungen verwendet wird, kann man annehmen, dass es einfache UND / ODER-Gatter auf den verschiedenen Bits in gibt EFLAGS, um zu bestimmen, ob die Bedingungen erfüllt sind. Es gibt dann keinen Grund, warum ein Befehl, der zwei Bits testet, mehr oder weniger Zeit in Anspruch nehmen sollte als ein Befehl, der nur eines testet (Ignorieren der Gate-Ausbreitungsverzögerung, die viel kürzer als die Taktperiode ist).

Bearbeiten: Gleitkomma

Dies gilt auch für x87-Gleitkommazahlen: (Ziemlich derselbe Code wie oben, jedoch mit doublestatt 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

Historisch gesehen (wir sprechen von den 1980er und frühen 1990er Jahren) gab es einige Architekturen, in denen dies zutraf. Das Hauptproblem besteht darin, dass der Ganzzahlvergleich von Natur aus über Ganzzahlsubtraktionen 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

Nun, wenn A < Bdie Subtraktion ein High-Bit ausleihen muss, damit die Subtraktion korrekt ist, so wie Sie es beim Addieren und Subtrahieren von Hand tragen und ausleihen. Dieses "geliehene" Bit wurde üblicherweise als Übertragsbit bezeichnet und kann durch einen Verzweigungsbefehl getestet werden. Ein zweites Bit, das als Nullbit bezeichnet wird, würde gesetzt, wenn die Subtraktion identisch Null wäre, was Gleichheit impliziert.

Es gab normalerweise mindestens zwei bedingte Verzweigungsbefehle, einen zum Verzweigen auf dem Übertragsbit und einen zum Nullbit.

Um auf den Punkt zu kommen, erweitern wir die vorherige Tabelle um die Übertragungs- und Null-Bit-Ergebnisse.

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

Das Implementieren einer Verzweigung für A < Bkann also in einem Befehl erfolgen, da das Übertragsbit nur in diesem Fall klar ist, d. H.

;; 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 durchführen möchten, der kleiner oder gleich ist, müssen wir das Null-Flag zusätzlich überprüfen, 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 „kleiner als“ Vergleich könnte speichert einen Maschinenbefehl . Dies war im Zeitalter der Sub-Megahertz-Prozessorgeschwindigkeit und des Verhältnisses von CPU zu Speicher von 1: 1 relevant, ist aber heute fast völlig irrelevant.

Angenommen, es handelt sich um interne Ganzzahltypen, gibt es keine Möglichkeit, dass einer schneller als der andere sein könnte. Sie sind offensichtlich semantisch identisch. Beide fordern den Compiler auf, genau dasselbe zu tun. Nur ein schrecklich kaputter Compiler würde für einen davon minderwertigen Code generieren.

Wenn es eine Plattform war , wo <war schneller als <=für einfachen Integer - Typen, sollte der Compiler immer konvertieren , <=um <für Konstanten. Jeder Compiler, der dies nicht tat, wäre nur ein schlechter Compiler (für diese Plattform).

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

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

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

Mein Beispiel ifstammt von GCC auf der x86_64-Plattform unter Linux.

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

Ich habe festgestellt, dass in beiden Fällen der gleiche Maschinencode generiert wird, wenn es sich nicht um eine Konstante handelt.

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

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

Für Gleitkomma-Code kann der Vergleich <= sogar auf modernen Architekturen langsamer sein (um einen Befehl). Hier ist die erste Funktion:

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

Auf PowerPC führt dies zuerst einen Gleitkomma-Vergleich durch (der crdas Bedingungsregister aktualisiert ), verschiebt dann das Bedingungsregister in einen GPR, verschiebt das Bit "verglichen weniger als" an seinen Platz und kehrt dann zurück. Es dauert vier Anweisungen.

Betrachten Sie nun stattdessen diese Funktion:

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

Dies erfordert die gleiche Arbeit wie compare_strictoben, aber jetzt gibt es zwei interessante Punkte: "war kleiner als" und "war gleich". Dies erfordert einen zusätzlichen Befehl ( cror- Bedingungsregister bitweise ODER), um diese beiden Bits zu einem zu kombinieren. So compare_looseerfordert fünf Anweisungen, während compare_strictvier erfordert.

Sie könnten denken, dass der Compiler die zweite Funktion folgendermaßen optimieren könnte:

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

Dies behandelt jedoch NaNs falsch. NaN1 <= NaN2und NaN1 > NaN2müssen beide zu falsch bewerten.

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

Aber es liegt daran, dass a 0beteiligt ist (weil CMPje nach Architektur zB durch ersetzt werden kann OR) und nicht an der <.

Wenn dies wahr wäre, könnte ein Compiler zumindest a <= b bis! (A> b) trivial optimieren, und selbst wenn der Vergleich selbst tatsächlich langsamer wäre, würden Sie mit allen außer dem naivsten Compiler keinen Unterschied bemerken .

Sie haben die gleiche Geschwindigkeit. Vielleicht ist in einer speziellen Architektur das, was er / sie gesagt hat, richtig, aber zumindest in der x86-Familie weiß ich, dass sie gleich sind. Zu diesem Zweck führt die CPU eine Subtraktion (a - b) durch und überprüft dann die Flags des Flagregisters. Zwei Bits dieses Registers heißen ZF (Null-Flag) und SF (Vorzeichen-Flag) und werden in einem Zyklus ausgeführt, da dies mit einer Maskenoperation erfolgt.

Dies hängt stark von der zugrunde liegenden Architektur ab, zu der das C kompiliert wird. Einige Prozessoren und Architekturen verfügen möglicherweise über explizite Anweisungen für gleich oder kleiner als und gleich, die in unterschiedlicher Anzahl von Zyklen ausgeführt werden.

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

TL; DR Antwort

Bei den meisten Kombinationen aus Architektur, Compiler und Sprache ist dies nicht schneller.

Vollständige Antwort

Andere Antworten werden auf konzentriert x86 - Architektur, und ich weiß nicht , die ARM - Architektur gut genug , um einen Kommentar speziell auf dem Code erzeugt, aber dies ist ein Beispiel für eine (die Ihr Beispiel Assembler zu sein scheint) Mikro-Optimierung , die ist sehr Architektur spezifisch und ist ebenso wahrscheinlich eine Anti-Optimierung wie eine Optimierung .

Daher würde ich vorschlagen, dass diese Art der Mikrooptimierung eher ein Beispiel für die Frachtkultprogrammierung als für die beste Softwareentwicklungspraxis ist.

Es gibt wahrscheinlich einige Architekturen, bei denen dies eine Optimierung ist, aber ich kenne mindestens eine Architektur, bei der das Gegenteil der Fall sein kann. Die ehrwürdige Transputer- Architektur hatte nur Maschinencode-Anweisungen für gleich und größer als oder gleich , so dass alle Vergleiche aus diesen Grundelementen erstellt werden mussten.

Selbst dann konnte der Compiler in fast allen Fällen die Auswertungsanweisungen so anordnen, dass in der Praxis kein Vergleich einen Vorteil gegenüber einem anderen hatte. Im schlimmsten Fall muss möglicherweise eine umgekehrte Anweisung (REV) hinzugefügt werden, um die beiden obersten Elemente auf dem Operandenstapel auszutauschen . Dies war ein Einzelbyte-Befehl, dessen Ausführung einen einzelnen Zyklus dauerte und daher den geringstmöglichen Overhead aufwies.

Unabhängig davon , ob eine Mikro-Optimierung wie dies ist eine Optimierung oder eine anti-Optimierung auf der spezifische Architektur ab , die Sie verwenden, so ist es in der Regel eine schlechte Idee ist , in die Gewohnheit, von Architektur spezifische Mikro-Optimierungen verwenden, sonst könnte man instinktiv Verwenden Sie eine, wenn dies unangemessen ist, und es sieht so aus, als würde das Buch, das Sie lesen, genau dies befürworten.

Sie sollten den Unterschied nicht bemerken können, selbst wenn es einen gibt. Außerdem müssen Sie in der Praxis eine zusätzliche a + 1oder a - 1eine Bedingung ausführen, es sei denn, Sie verwenden einige magische Konstanten, was auf jeden Fall eine sehr schlechte Praxis ist.

Man könnte sagen, dass die Zeile in den meisten Skriptsprachen korrekt ist, da das zusätzliche Zeichen zu einer etwas langsameren Codeverarbeitung führt. Wie in der Top-Antwort bereits erwähnt, sollte dies in C ++ keine Auswirkungen haben, und alles, was mit einer Skriptsprache ausgeführt wird, ist wahrscheinlich nicht so wichtig für die Optimierung.

Als ich diese Antwort schrieb, war ich auf der Suche nur auf der Titel - Frage zu <vs. <= in der Regel nicht das spezifische Beispiel eines konstanten a < 901vs. a <= 900. Viele Compiler verkleinern die Größe von Konstanten immer durch Konvertieren zwischen <und <=, z. B. weil der x86-Sofortoperand eine kürzere 1-Byte-Codierung für -128..127 hat.

Für ARM und insbesondere AArch64 hängt die Fähigkeit, sofort zu codieren, davon ab, dass ein schmales Feld in eine beliebige Position in einem Wort gedreht werden kann. Also cmp w0, #0x00f000wäre kodierbar, cmp w0, #0x00effffkönnte aber nicht sein. Daher gilt die AA-Regel zum Vergleich mit einer Konstante zur Kompilierungszeit nicht immer für AArch64.

<vs. <= im Allgemeinen, auch für Bedingungen mit Laufzeitvariablen

In der Assemblersprache der meisten Maschinen hat ein Vergleich für <=die gleichen Kosten wie ein Vergleich für <. Dies gilt unabhängig davon, ob Sie darauf verzweigen, es boolesch machen, um eine 0/1-Ganzzahl zu erstellen, oder es als Prädikat für eine verzweigungslose Auswahloperation (wie x86 CMOV) verwenden. Die anderen Antworten haben nur diesen Teil der Frage angesprochen.

Bei dieser Frage geht es jedoch um die C ++ - Operatoren, die Eingabe in den Optimierer. Normalerweise sind beide gleich effizient. Der Rat aus dem Buch klingt völlig falsch, da Compiler den Vergleich, den sie in asm implementieren, immer transformieren können. Es gibt jedoch mindestens eine Ausnahme, bei der die Verwendung <=versehentlich etwas erzeugen kann, das der Compiler nicht optimieren kann.

Als Schleifenbedingung gibt es Fälle, in denen <=sich der Compiler qualitativ davon unterscheidet <, zu beweisen, dass eine Schleife nicht unendlich ist. Dies kann einen großen Unterschied machen und die automatische Vektorisierung deaktivieren.

Der vorzeichenlose Überlauf ist im Gegensatz zum vorzeichenbehafteten Überlauf (UB) als Base-2-Wrap-Around gut definiert. Vorzeichenbehaftete Schleifenzähler sind im Allgemeinen davor sicher, da Compiler, die basierend auf dem nicht auftretenden UB mit vorzeichenbehaftetem Überlauf optimieren, nicht ++i <= sizeirgendwann falsch werden. ( Was jeder C-Programmierer über undefiniertes Verhalten wissen sollte )

void foo(unsigned size) {
    unsigned upper_bound = size - 1;  // or any calculation that could produce UINT_MAX
    for(unsigned i=0 ; i <= upper_bound ; i++)
        ...

Compiler können nur so optimieren, dass das (definierte und rechtlich beobachtbare) Verhalten der C ++ - Quelle für alle möglichen Eingabewerte erhalten bleibt , mit Ausnahme derjenigen, die zu undefiniertem Verhalten führen.

(Ein einfaches i <= sizewürde auch das Problem verursachen, aber ich dachte, die Berechnung einer Obergrenze wäre ein realistischeres Beispiel für die versehentliche Einführung der Möglichkeit einer Endlosschleife für eine Eingabe, die Sie nicht interessieren, die der Compiler jedoch berücksichtigen muss.)

In diesem Fall size=0führt upper_bound=UINT_MAXund i <= UINT_MAXist immer wahr. Diese Schleife ist also unendlich für size=0, und der Compiler muss dies respektieren, obwohl Sie als Programmierer wahrscheinlich nie beabsichtigen, size = 0 zu übergeben. Wenn der Compiler diese Funktion in einen Aufrufer einbinden kann, in dem er beweisen kann, dass size = 0 unmöglich ist, kann er großartig optimieren, wie es für möglich wäre i < size.

Asm like if(!size) skip the loop; do{...}while(--size);ist eine normalerweise effiziente Methode zur Optimierung einer for( i<size )Schleife, wenn der tatsächliche Wert von iinnerhalb der Schleife nicht benötigt wird ( Warum werden Schleifen immer im Stil "do ... while" kompiliert (Tail Jump)? ).

Aber das kann nicht unendlich sein: Wenn size==0wir mit eingeben, erhalten wir 2 ^ n Iterationen. (Das Iterieren über alle vorzeichenlosen Ganzzahlen in einer for-Schleife C ermöglicht es, eine Schleife über alle vorzeichenlosen Ganzzahlen einschließlich Null auszudrücken, aber ohne ein Übertragsflag ist es nicht einfach, wie es in asm ist.)

Da der Umlauf des Schleifenzählers möglich ist, geben moderne Compiler oft nur auf und optimieren nicht annähernd so aggressiv.

Beispiel: Summe von ganzen Zahlen von 1 bis n

Verwenden von vorzeichenlosen i <= nNiederlagen Clangs Redewendung, die sum(1 .. n)Schleifen mit einer geschlossenen Form basierend auf der Gaußschen n * (n+1) / 2Formel optimiert .

unsigned sum_1_to_n_finite(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i < n+1 ; ++i)
        total += i;
    return total;
}

x86-64 asm von clang7.0 und gcc8.2 im Godbolt-Compiler-Explorer

 # clang7.0 -O3 closed-form
    cmp     edi, -1       # n passed in EDI: x86-64 System V calling convention
    je      .LBB1_1       # if (n == UINT_MAX) return 0;  // C++ loop runs 0 times
          # else fall through into the closed-form calc
    mov     ecx, edi         # zero-extend n into RCX
    lea     eax, [rdi - 1]   # n-1
    imul    rax, rcx         # n * (n-1)             # 64-bit
    shr     rax              # n * (n-1) / 2
    add     eax, edi         # n + (stuff / 2) = n * (n+1) / 2   # truncated to 32-bit
    ret          # computed without possible overflow of the product before right shifting
.LBB1_1:
    xor     eax, eax
    ret

Aber für die naive Version bekommen wir nur eine dumme Schleife von Clang.

unsigned sum_1_to_n_naive(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i<=n ; ++i)
        total += i;
    return total;
}

# clang7.0 -O3
sum_1_to_n(unsigned int):
    xor     ecx, ecx           # i = 0
    xor     eax, eax           # retval = 0
.LBB0_1:                       # do {
    add     eax, ecx             # retval += i
    add     ecx, 1               # ++1
    cmp     ecx, edi
    jbe     .LBB0_1            # } while( i<n );
    ret

GCC verwendet in keiner Weise eine geschlossene Form, so dass die Wahl der Schleifenbedingung nicht wirklich schadet . Es wird automatisch mit einer SIMD-Ganzzahladdition vektorisiert, wobei 4 iWerte parallel in den Elementen eines XMM-Registers ausgeführt werden.

# "naive" inner loop
.L3:
    add     eax, 1       # do {
    paddd   xmm0, xmm1    # vect_total_4.6, vect_vec_iv_.5
    paddd   xmm1, xmm2    # vect_vec_iv_.5, tmp114
    cmp     edx, eax      # bnd.1, ivtmp.14     # bound and induction-variable tmp, I think.
    ja      .L3 #,       # }while( n > i )

 "finite" inner loop
  # before the loop:
  # xmm0 = 0 = totals
  # xmm1 = {0,1,2,3} = i
  # xmm2 = set1_epi32(4)
 .L13:                # do {
    add     eax, 1       # i++
    paddd   xmm0, xmm1    # total[0..3] += i[0..3]
    paddd   xmm1, xmm2    # i[0..3] += 4
    cmp     eax, edx
    jne     .L13      # }while( i != upper_limit );

     then horizontal sum xmm0
     and peeled cleanup for the last n%3 iterations, or something.

Es hat auch eine einfache Skalarschleife, die meiner Meinung nach für sehr kleine nund / oder für den Endlosschleifenfall verwendet wird.

Übrigens verschwenden diese beiden Schleifen einen Befehl (und einen UOP auf CPUs der Sandybridge-Familie) für den Schleifen-Overhead. sub eax,1/ jnzanstelle von add eax,1/ cmp / jcc wäre effizienter. 1 uop statt 2 (nach Makrofusion von sub / jcc oder cmp / jcc). Der Code nach beiden Schleifen schreibt EAX bedingungslos, sodass nicht der Endwert des Schleifenzählers verwendet wird.

Nur wenn die Leute, die die Computer erstellt haben, schlecht mit boolescher Logik umgehen können. Was sie nicht sein sollten.

Jeder Vergleich ( >= <= > <) kann mit der gleichen Geschwindigkeit durchgeführt werden.

Was jeder Vergleich ist, ist nur eine Subtraktion (der Unterschied) und zu sehen, ob er positiv / negativ ist.
(Wenn das msbeingestellt ist, ist die Zahl negativ)

Wie überprüfe ich a >= b? Sub a-b >= 0Überprüfen Sie, ob a-bpositiv ist.
Wie überprüfe ich a <= b? Sub 0 <= b-aÜberprüfen Sie, ob b-apositiv ist.
Wie überprüfe ich a < b? Sub a-b < 0Überprüfen Sie, ob a-bnegativ ist.
Wie überprüfe ich a > b? Sub 0 > b-aÜberprüfen Sie, ob b-anegativ ist.

Einfach ausgedrückt, der Computer kann dies einfach unter der Haube für die gegebene Operation tun:

a >= b== msb(a-b)==0
a <= b== msb(b-a)==0
a > b== msb(b-a)==1
a < b==msb(a-b)==1

und natürlich würde der Computer das ==0oder auch ==1nicht tun müssen .
für das ==0könnte es einfach das msbvon der schaltung umkehren.

Wie auch immer, sie hätten es mit Sicherheit nicht a >= bals a>b || a==blol berechnet