Vraag Is

Ik ben een boek aan het lezen waar de auteur dat zegt if( a < 901 ) is sneller dan if( a <= 900 ).

Niet precies zoals in dit eenvoudige voorbeeld, maar er zijn kleine veranderingen in de prestaties van de lus-complexe code. Ik veronderstel dat dit iets met gegenereerde machinecode moet doen voor het geval het zelfs waar is.


1372
2017-08-27 02:10


oorsprong


antwoorden:


Nee, op de meeste architecturen zal het niet sneller zijn. U hebt niet opgegeven, maar op x86 worden alle integrale vergelijkingen meestal geïmplementeerd in twee machine-instructies:

  • EEN test of cmp instructie, die begint EFLAGS
  • En een Jcc (jump) instructie, afhankelijk van het vergelijkingstype (en code-indeling):
    • jne - Spring indien niet gelijk -> ZF = 0
    • jz - Spring als nul (gelijk) -> ZF = 1
    • jg - Spring indien groter -> ZF = 0 and SF = OF
    • (enz...)

Voorbeeld (Uitgegeven voor beknoptheid) Samengesteld met $ gcc -m32 -S -masm=intel test.c

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

Compileert naar:

    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:

En

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

Compileert naar:

    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:

Dus het enige verschil tussen de twee is een jg versus a jge instructie. De twee nemen evenveel tijd in beslag.


Ik zou graag de opmerking willen maken dat niets aangeeft dat de verschillende spronginstructies evenveel tijd in beslag nemen. Deze is een beetje lastig om te beantwoorden, maar hier is wat ik kan geven: in de Intel Instruction Set Reference, ze zijn allemaal gegroepeerd onder één gemeenschappelijke instructie, Jcc (Springen als aan voorwaarde is voldaan). Dezelfde groepering is samen gemaakt onder de Referentiehandleiding voor optimalisatie, in bijlage C. Latency and Throughput.

Wachttijd - Het aantal klokcycli dat vereist is voor de   uitvoering kern om de uitvoering van alle van de ips die zich vormen te voltooien   een instructie.

Doorvoer - Het aantal klokcycli dat nodig is om   wacht voordat de uitgiftepoorten vrij zijn om dezelfde instructie te accepteren   nog een keer. Voor veel instructies kan de doorvoer van een instructie zijn   aanzienlijk minder dan de latentie

De waarden voor Jcc zijn:

      Latency   Throughput
Jcc     N/A        0.5

met de volgende voetnoot Jcc:

7) De selectie van voorwaardelijke spronginstructies moet gebaseerd zijn op de aanbeveling van paragraaf Paragraaf 3.4.1, "Brondoorspoor optimalisatie", om de voorspelbaarheid van vertakkingen te verbeteren. Wanneer takken succesvol worden voorspeld, de latentie van jcc is effectief nul.

Dus niets in de Intel Docs behandelt er ooit een Jcc instructie anders dan de anderen.

Als men denkt aan het feitelijke circuit dat wordt gebruikt om de instructies te implementeren, kan men aannemen dat er eenvoudige EN / OF-poorten op de verschillende bits in EFLAGS, om te bepalen of aan de voorwaarden is voldaan. Er is dan geen reden dat een instructietest van twee bits meer of minder tijd in beslag zou nemen dan slechts één test (waarbij de poortvoortplantingsvertraging niet wordt genegeerd, wat veel minder is dan de klokperiode).


Bewerken: zwevend punt

Dit geldt ook voor x87 floating point: (vrijwel dezelfde code als hierboven, maar met double in plaats van 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 gezien (we hebben het over de jaren tachtig en vroege jaren negentig) waren dat er wel sommige architecturen waarin dit waar was. Het basisprobleem is dat de gehele vergelijking door intrinsieke aftrekkingen inherent wordt geïmplementeerd. Dit geeft aanleiding tot de volgende gevallen.

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

Nu wanneer A < B de aftrekking moet een high-bit lenen om de aftrekking correct te laten zijn, net zoals je bij het optellen en aftrekken met de hand draagt ​​en leent. Deze "geleende" bit werd meestal de draag beetje en zou getest kunnen worden door een filiaalinstructie. Een tweede bit genaamd de nul bit zou worden ingesteld als de aftrekking identiek nul was wat gelijkheid impliceerde.

Er waren meestal minstens twee conditionele vertakkingsinstructies, één om te vertakken op de carry-bit en één op de zero-bit.

Laten we nu, om de kern van de zaak te raken, de vorige tabel uitbreiden met de carry- en zero-bitresultaten.

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

Dus, een tak implementeren voor A < B kan in één instructie worden gedaan, omdat de carry-bit vrij is enkel en alleen in dit geval, dat wil zeggen,

;; 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

Maar als we een minder-dan-gelijke vergelijking willen maken, moeten we een aanvullende controle van de nulvlag uitvoeren om het geval van gelijkheid te vangen.

;; 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

Dus op sommige machines gebruikt u een "minder dan" vergelijking macht opslaan een machine-instructie. Dit was relevant in het tijdperk van sub-megahertz processorsnelheid en 1: 1 CPU-to-memory snelheidsverhoudingen, maar het is tegenwoordig bijna helemaal irrelevant.


555
2017-08-27 17:53



Ervan uitgaande dat we het hebben over interne integer-typen, is er geen enkele manier om sneller te zijn dan de ander. Ze zijn duidelijk semantisch identiek. Ze vragen de compiler om precies hetzelfde te doen. Alleen een vreselijk gebroken compiler zou inferieure code genereren voor een van deze.

Als er ergens een platform was < was sneller dan <= voor eenvoudige integer-typen zou de compiler moeten altijd converteren <= naar < voor constanten. Elke compiler die dat niet deed, zou gewoon een slechte compiler zijn (voor dat platform).


85
2017-08-27 02:31



Ik zie dat geen van beide sneller is. De compiler genereert in elke situatie dezelfde machinecode met een andere waarde.

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

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

Mijn voorbeeld if is van GCC op x86_64 platform op Linux.

Compiler-schrijvers zijn behoorlijk slimme mensen, en ze denken aan deze dingen en vele anderen de meesten van ons als vanzelfsprekend beschouwen.

Ik merkte dat als het geen constante is, in beide gevallen dezelfde machinecode wordt gegenereerd.

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



Voor drijvende-komma-code kan de <= vergelijking inderdaad langzamer zijn (met één instructie), zelfs op moderne architecturen. Dit is de eerste functie:

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

Op PowerPC voert dit eerst een vergelijking met drijvende komma uit (die wordt bijgewerkt crhet toestandsregister), verplaatst dan het toestandsregister naar een GPR, verschuift het "vergeleken minder dan" bit naar zijn plaats en keert dan terug. Er zijn vier instructies voor nodig.

Overweeg nu deze functie:

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

Dit vereist hetzelfde werk als compare_strict hierboven, maar nu zijn er twee interessante dingen: "was minder dan" en "was gelijk aan." Dit vereist een extra instructie (cror- conditie register bitsgewijs OF) om deze twee bits in één te combineren. Zo compare_loose vereist vijf instructies, terwijl compare_strict vereist vier.

Je zou denken dat de compiler de tweede functie zou kunnen optimaliseren zoals:

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

Dit zal echter verkeerd omgaan met NaN's. NaN1 <= NaN2 en NaN1 > NaN2 moeten beide evalueren tot onwaar.


48
2017-08-27 18:32



Misschien heeft de auteur van dat naamloze boek dat gelezen a > 0 werkt sneller dan a >= 1 en denkt dat dat universeel waar is.

Maar het is omdat a 0 is betrokken (omdat CMP kan, afhankelijk van de architectuur, bijvoorbeeld b.v. met OR) en niet vanwege de <.


34
2017-08-27 13:05



Op zijn minst, als dit waar zou zijn, zou een compiler triviaal een <= b naar! (A> b) kunnen optimaliseren, en dus zelfs als de vergelijking zelf langzamer zou zijn, met alle, behalve de meest naïeve compiler, zou je geen verschil merken .


29
2017-08-27 09:23