wake-up-neo.com

Wenn Anweisung vs if-else-Anweisung, welche ist schneller?

Ich habe neulich mit einem Freund über diese beiden Schnipsel gestritten. Welches ist schneller und warum?

value = 5;
if (condition) {
    value = 6;
}

und:

if (condition) {
    value = 6;
} else {
    value = 5;
}

Was ist, wenn value eine Matrix ist?

Hinweis: Ich weiß, dass value = condition ? 6 : 5; existiert und ich erwarte, dass es schneller ist, aber es war keine Option.

Bearbeiten (von Mitarbeitern angefordert, da die Frage momentan gehalten wird):

  • bitte antworten Sie, indem Sie entweder x86 Assembly betrachten, das von Mainstream-Compilern (z. B. g ++, clang ++, vc, mingw) in optimierten und nicht optimierten Versionen oder MIPS Assembly generiert wird.
  • wenn sich die Assemblys unterscheiden, erklären Sie, warum eine Version schneller ist und wann (z. B. "besser, weil keine Verzweigung und Verzweigung das folgende Problem hat").
79
Julien__

TL; DR: In nicht optimiertem Code scheint if ohne else irrelevant effizienter zu sein, aber selbst wenn die grundlegendste Optimierungsebene aktiviert ist, wird der Code grundsätzlich in value = condition + 5 umgeschrieben.


Ich gab es einen Versuch und generierte die Assembly für den folgenden Code:

int ifonly(bool condition, int value)
{
    value = 5;
    if (condition) {
        value = 6;
    }
    return value;
}

int ifelse(bool condition, int value)
{
    if (condition) {
        value = 6;
    } else {
        value = 5;
    }
    return value;
}

Bei gcc 6.3 mit deaktivierten Optimierungen (-O0) ist der relevante Unterschied:

 mov     DWORD PTR [rbp-8], 5
 cmp     BYTE PTR [rbp-4], 0
 je      .L2
 mov     DWORD PTR [rbp-8], 6
.L2:
 mov     eax, DWORD PTR [rbp-8]

für ifonly, während ifelse hat 

 cmp     BYTE PTR [rbp-4], 0
 je      .L5
 mov     DWORD PTR [rbp-8], 6
 jmp     .L6
.L5:
 mov     DWORD PTR [rbp-8], 5
.L6:
 mov     eax, DWORD PTR [rbp-8]

Letzteres sieht etwas weniger effizient aus, da es einen zusätzlichen Sprung hat, aber beide haben mindestens zwei und höchstens drei Aufgaben. Wenn Sie nicht wirklich jeden letzten Tropfen Leistung abpressen müssen (Hinweis: Wenn Sie nicht an einem Space Shuttle arbeiten, tun Sie dies nicht und selbst dann, wenn Sie wahrscheinlich nicht), wird der Unterschied nicht wahrgenommen.

Selbst bei der niedrigsten Optimierungsstufe (-O1) reduzieren sich beide Funktionen jedoch auf das gleiche:

test    dil, dil
setne   al
movzx   eax, al
add     eax, 5

das ist im Grunde das Äquivalent von 

return 5 + condition;

angenommen, condition ist null oder eins . Höhere Optimierungsstufen ändern die Ausgabe nicht wirklich, außer sie schaffen es, die movzx zu vermeiden, indem sie das EAX-Register beim Start effizient auf Null setzen.


Disclaimer: Sie sollten 5 + condition wahrscheinlich nicht selbst schreiben (obwohl der Standard garantiert, dass die Konvertierung von true in einen Integer-Typ 1 ergibt), da Ihre Absicht für Leute, die Ihren Code lesen, möglicherweise nicht sofort offensichtlich ist (was möglicherweise Ihr zukünftiges Ich betrifft ). Dieser Code soll zeigen, dass das, was der Compiler in beiden Fällen produziert, (praktisch) identisch ist. Ciprian Tomoiaga sagt es ganz gut in den Kommentaren:

die Aufgabe eines human besteht darin, den Code für Menschen zu schreiben und den compiler Code für die Maschine schreiben zu lassen. 

272
CompuChip

Die Antwort von CompuChip zeigt, dass beide für int auf dieselbe Assembly optimiert sind, es spielt also keine Rolle.

Was ist, wenn Wert eine Matrix ist?

Ich werde dies auf eine allgemeinere Weise interpretieren, d. H. Was ist, wenn value von einem Typ ist, dessen Konstruktionen und Zuweisungen teuer sind (und Bewegungen billig sind).

dann

T value = init1;
if (condition)
   value = init2;

ist suboptimal, da in condition true die init1-Initialisierung unnötig ist und dann die Kopierzuweisung erfolgt.

T value;
if (condition)
   value = init2;
else
   value = init3;

Das ist besser. Aber immer noch nicht optimal, wenn die Standardkonstruktion teuer ist und die Kopienkonstruktion teurer ist als die Initialisierung.

Sie haben die bedingte Operatorlösung, die gut ist:

T value = condition ? init1 : init2;

Wenn Sie den bedingten Operator nicht mögen, können Sie eine Hilfsfunktion wie folgt erstellen:

T create(bool condition)
{
  if (condition)
     return {init1};
  else
     return {init2};
}

T value = create(condition);

Abhängig davon, was init1 und init2 sind, können Sie dies auch berücksichtigen:

auto final_init = condition ? init1 : init2;
T value = final_init;

Aber ich muss noch einmal betonen, dass dies nur relevant ist, wenn Konstruktion und Zuweisung für den jeweiligen Typ sehr teuer sind. Und selbst dann, nur durch profiling wissen Sie es genau.

44
bolov

In der Pseudo-Assemblersprache

    li    #0, r0
    test  r1
    beq   L1
    li    #1, r0
L1:

kann oder kann nicht schneller sein als

    test  r1
    beq   L1
    li    #1, r0
    bra   L2
L1:
    li    #0, r0
L2:

je nachdem, wie hoch die tatsächliche CPU ist. Vom einfachsten zum schicksten:

  • Bei jeder CPU, die nach ungefähr 1990 hergestellt wurde, hängt eine gute Leistung von der Code-Anpassung im Anweisungs-Cache ab. Im Zweifelsfall minimieren Sie daher die Codegröße. Dies spricht für das erste Beispiel.

  • Bei einer einfachen " in-order, fünfstufigen Pipeline " CPU, die in vielen Mikrocontrollern immer noch ungefähr so ​​ist, gibt es bei jeder Verzweigung eine Pipeline-Blase bedingt oder nicht bedingt - wird verwendet, daher ist es auch wichtig, die Anzahl der Verzweigungsbefehle zu minimieren. Dies spricht auch für das erste Beispiel.

  • Etwas ausgefeiltere CPUs - die " Out-of-Order-Ausführung " ausführen möchten, aber nicht die bekanntesten Implementierungen dieses Konzepts verwenden möchten - können bei jedem Auftreten Pipeline-Blasen verursachen Write-After-Write-Gefahren . Dies spricht für das zweite Beispiel, in dem r0 wird nur einmal geschrieben, egal was passiert. Diese CPUs sind normalerweise gut genug, um unbedingte Verzweigungen im Anweisungsabruf zu verarbeiten, sodass Sie nicht nur die Strafe für das Schreiben nach dem Schreiben für eine Verzweigung eintauschen Strafe.

    Ich weiß nicht, ob noch jemand diese Art von CPU herstellt. Es ist jedoch wahrscheinlich, dass die CPUs, die die "bekanntesten Implementierungen" von Out-of-Order-Ausführung verwenden , Abstriche bei den weniger häufig verwendeten Befehlen machen. Sie müssen sich also darüber im Klaren sein, dass so etwas passieren kann. Ein reales Beispiel ist falsche Datenabhängigkeiten von den Zielregistern in popcnt und lzcnt auf Sandy Bridge-CPUs .

  • Am höchsten Punkt gibt die OOO-Engine für beide Codefragmente genau die gleiche Abfolge interner Operationen aus. Dies ist die Hardwareversion von "Keine Sorge, der Compiler generiert in beiden Fällen den gleichen Maschinencode." Die Codegröße spielt jedoch immer noch eine Rolle, und jetzt sollten Sie sich auch Gedanken über die Vorhersagbarkeit des bedingten Zweigs machen. Verzweigungsvorhersage Ausfälle verursachen möglicherweise eine vollständige Pipeline-Spülung , die für die Leistung katastrophal ist. Siehe Warum ist es schneller, ein sortiertes Array zu verarbeiten als ein unsortiertes Array? um zu verstehen, wie viel Unterschied dies bewirken kann.

    Wenn die Verzweigung in hohem Maße unvorhersehbar ist und Ihre CPU Anweisungen für bedingte Sätze oder bedingte Verschiebungen hat, ist dies die richtige Zeit, um sie zu verwenden:

        li    #0, r0
        test  r1
        setne r0
    

    oder

        li    #0, r0
        li    #1, r2
        test  r1
        movne r2, r0
    

    Die bedingte Version ist außerdem kompakter als jede andere Alternative. Wenn diese Anweisung verfügbar ist, ist sie für dieses Szenario garantiert das Richtige, auch wenn die Verzweigung vorhersehbar war. Die bedingte Verschiebung erfordert ein zusätzliches Scratch-Register und verschwendet immer den Wert einer li - Anweisung für das Versenden und Ausführen von Ressourcen. Wenn die Verzweigung tatsächlich vorhersehbar war, ist die verzweigte Version möglicherweise schneller.

11
zwol

Im nicht optimierten Code weist das erste Beispiel eine Variable immer einmal und manchmal zweimal zu. Das zweite Beispiel weist eine Variable immer nur einmal zu. Die Bedingung ist für beide Codepfade gleich, daher sollte dies keine Rolle spielen. Im optimierten Code hängt es vom Compiler ab.

Wenn Sie so besorgt sind, generieren Sie wie immer die Assembly und sehen, was der Compiler tatsächlich tut.

10
Neil

Was würde Sie dazu bringen, zu glauben, dass einer von ihnen schneller oder langsamer ist? 

unsigned int fun0 ( unsigned int condition, unsigned int value )
{
    value = 5;
    if (condition) {
        value = 6;
    }
    return(value);
}
unsigned int fun1 ( unsigned int condition, unsigned int value )
{

    if (condition) {
        value = 6;
    } else {
        value = 5;
    }
    return(value);
}
unsigned int fun2 ( unsigned int condition, unsigned int value )
{
    value = condition ? 6 : 5;
    return(value);
}

Mit mehr Codezeilen einer Hochsprache kann der Compiler besser arbeiten. Wenn Sie also eine allgemeine Regel festlegen möchten, geben Sie dem Compiler mehr Code für die Arbeit mit. Wenn der Algorithmus der gleiche ist wie in den obigen Fällen, würde man erwarten, dass der Compiler dies mit minimaler Optimierung herausfindet.

00000000 <fun0>:
   0:   e3500000    cmp r0, #0
   4:   03a00005    moveq   r0, #5
   8:   13a00006    movne   r0, #6
   c:   e12fff1e    bx  lr

00000010 <fun1>:
  10:   e3500000    cmp r0, #0
  14:   13a00006    movne   r0, #6
  18:   03a00005    moveq   r0, #5
  1c:   e12fff1e    bx  lr

00000020 <fun2>:
  20:   e3500000    cmp r0, #0
  24:   13a00006    movne   r0, #6
  28:   03a00005    moveq   r0, #5
  2c:   e12fff1e    bx  lr

es war keine große Überraschung, dass die erste Funktion in einer anderen Reihenfolge ausgeführt wurde, dieselbe Ausführungszeit jedoch.

0000000000000000 <fun0>:
   0:   7100001f    cmp w0, #0x0
   4:   1a9f07e0    cset    w0, ne
   8:   11001400    add w0, w0, #0x5
   c:   d65f03c0    ret

0000000000000010 <fun1>:
  10:   7100001f    cmp w0, #0x0
  14:   1a9f07e0    cset    w0, ne
  18:   11001400    add w0, w0, #0x5
  1c:   d65f03c0    ret

0000000000000020 <fun2>:
  20:   7100001f    cmp w0, #0x0
  24:   1a9f07e0    cset    w0, ne
  28:   11001400    add w0, w0, #0x5
  2c:   d65f03c0    ret

Hoffentlich haben Sie die Idee, Sie hätten es einfach ausprobiert, wenn nicht offensichtlich war, dass die verschiedenen Implementierungen nicht wirklich unterschiedlich waren.

Was eine Matrix angeht, weiß man nicht genau, worauf es ankommt.

if(condition)
{
 big blob of code a
}
else
{
 big blob of code b
}

ich werde einfach den gleichen if-then-else-Wrapper um die großen Code-Blobs legen, sei es value = 5 oder etwas komplizierter. Ebenso ist der Vergleich, selbst wenn es sich um einen großen Code-Block handelt, noch zu berechnen, und etwas gleich oder ungleich etwas wird oft mit dem Negativen kompiliert.

00000000 <fun0>:
   0:   0f 93           tst r15     
   2:   03 24           jz  $+8         ;abs 0xa
   4:   3f 40 06 00     mov #6, r15 ;#0x0006
   8:   30 41           ret         
   a:   3f 40 05 00     mov #5, r15 ;#0x0005
   e:   30 41           ret         

00000010 <fun1>:
  10:   0f 93           tst r15     
  12:   03 20           jnz $+8         ;abs 0x1a
  14:   3f 40 05 00     mov #5, r15 ;#0x0005
  18:   30 41           ret         
  1a:   3f 40 06 00     mov #6, r15 ;#0x0006
  1e:   30 41           ret         

00000020 <fun2>:
  20:   0f 93           tst r15     
  22:   03 20           jnz $+8         ;abs 0x2a
  24:   3f 40 05 00     mov #5, r15 ;#0x0005
  28:   30 41           ret         
  2a:   3f 40 06 00     mov #6, r15 ;#0x0006
  2e:   30 41

wir haben diese Übung kürzlich mit jemand anderem über stackoverflow durchgeführt. Dieser Mips-Compiler stellte in diesem Fall interessanterweise nicht nur fest, dass die Funktionen gleich waren, sondern dass eine Funktion einfach zur anderen springen musste, um Code zu sparen. Das habe ich hier nicht gemacht

00000000 <fun0>:
   0:   0004102b    sltu    $2,$0,$4
   4:   03e00008    jr  $31
   8:   24420005    addiu   $2,$2,5

0000000c <fun1>:
   c:   0004102b    sltu    $2,$0,$4
  10:   03e00008    jr  $31
  14:   24420005    addiu   $2,$2,5

00000018 <fun2>:
  18:   0004102b    sltu    $2,$0,$4
  1c:   03e00008    jr  $31
  20:   24420005    addiu   $2,$2,5

einige weitere Ziele.

00000000 <_fun0>:
   0:   1166            mov r5, -(sp)
   2:   1185            mov sp, r5
   4:   0bf5 0004       tst 4(r5)
   8:   0304            beq 12 <_fun0+0x12>
   a:   15c0 0006       mov $6, r0
   e:   1585            mov (sp)+, r5
  10:   0087            rts pc
  12:   15c0 0005       mov $5, r0
  16:   1585            mov (sp)+, r5
  18:   0087            rts pc

0000001a <_fun1>:
  1a:   1166            mov r5, -(sp)
  1c:   1185            mov sp, r5
  1e:   0bf5 0004       tst 4(r5)
  22:   0204            bne 2c <_fun1+0x12>
  24:   15c0 0005       mov $5, r0
  28:   1585            mov (sp)+, r5
  2a:   0087            rts pc
  2c:   15c0 0006       mov $6, r0
  30:   1585            mov (sp)+, r5
  32:   0087            rts pc

00000034 <_fun2>:
  34:   1166            mov r5, -(sp)
  36:   1185            mov sp, r5
  38:   0bf5 0004       tst 4(r5)
  3c:   0204            bne 46 <_fun2+0x12>
  3e:   15c0 0005       mov $5, r0
  42:   1585            mov (sp)+, r5
  44:   0087            rts pc
  46:   15c0 0006       mov $6, r0
  4a:   1585            mov (sp)+, r5
  4c:   0087            rts pc

00000000 <fun0>:
   0:   00a03533            snez    x10,x10
   4:   0515                    addi    x10,x10,5
   6:   8082                    ret

00000008 <fun1>:
   8:   00a03533            snez    x10,x10
   c:   0515                    addi    x10,x10,5
   e:   8082                    ret

00000010 <fun2>:
  10:   00a03533            snez    x10,x10
  14:   0515                    addi    x10,x10,5
  16:   8082                    ret

und Compiler

mit diesem i-Code würde man erwarten, dass die verschiedenen Ziele ebenfalls übereinstimmen

define i32 @fun0(i32 %condition, i32 %value) #0 {
  %1 = icmp ne i32 %condition, 0
  %. = select i1 %1, i32 6, i32 5
  ret i32 %.
}

; Function Attrs: norecurse nounwind readnone
define i32 @fun1(i32 %condition, i32 %value) #0 {
  %1 = icmp eq i32 %condition, 0
  %. = select i1 %1, i32 5, i32 6
  ret i32 %.
}

; Function Attrs: norecurse nounwind readnone
define i32 @fun2(i32 %condition, i32 %value) #0 {
  %1 = icmp ne i32 %condition, 0
  %2 = select i1 %1, i32 6, i32 5
  ret i32 %2
}


00000000 <fun0>:
   0:   e3a01005    mov r1, #5
   4:   e3500000    cmp r0, #0
   8:   13a01006    movne   r1, #6
   c:   e1a00001    mov r0, r1
  10:   e12fff1e    bx  lr

00000014 <fun1>:
  14:   e3a01006    mov r1, #6
  18:   e3500000    cmp r0, #0
  1c:   03a01005    moveq   r1, #5
  20:   e1a00001    mov r0, r1
  24:   e12fff1e    bx  lr

00000028 <fun2>:
  28:   e3a01005    mov r1, #5
  2c:   e3500000    cmp r0, #0
  30:   13a01006    movne   r1, #6
  34:   e1a00001    mov r0, r1
  38:   e12fff1e    bx  lr


fun0:
    Push.w  r4
    mov.w   r1, r4
    mov.w   r15, r12
    mov.w   #6, r15
    cmp.w   #0, r12
    jne .LBB0_2
    mov.w   #5, r15
.LBB0_2:
    pop.w   r4
    ret

fun1:
    Push.w  r4
    mov.w   r1, r4
    mov.w   r15, r12
    mov.w   #5, r15
    cmp.w   #0, r12
    jeq .LBB1_2
    mov.w   #6, r15
.LBB1_2:
    pop.w   r4
    ret


fun2:
    Push.w  r4
    mov.w   r1, r4
    mov.w   r15, r12
    mov.w   #6, r15
    cmp.w   #0, r12
    jne .LBB2_2
    mov.w   #5, r15
.LBB2_2:
    pop.w   r4
    ret

Technisch gesehen gibt es in einigen dieser Lösungen einen Leistungsunterschied. Manchmal ergibt sich ein Ergebnis von 5, ein Sprung über dem Ergebnis von 6-Code, und umgekehrt. man könnte argumentieren, aber die Ausführung sollte variieren. Dies ist jedoch eher eine if-Bedingung im Vergleich zu einer wenn-Bedingung im Code, die dazu führt, dass der Compiler die Ausführung dieses Befehls ausführt, wenn dieser Sprung ausgeführt wird. Dies ist jedoch nicht unbedingt auf den Codierstil zurückzuführen, sondern auf den Vergleich und die Falls und die Sonstigen Fälle in welcher Syntax.

8
old_timer

Ok, da Assembly eines der Tags ist, gehe ich einfach davon aus, dass es sich bei Ihrem Code um Pseudocode (und nicht unbedingt c) handelt, und übersetzen Sie ihn in 6502 Assembly.

1. Option (ohne sonst)

        ldy #$00
        lda #$05
        dey
        bmi false
        lda #$06
false   brk

2. Option (mit anderem)

        ldy #$00
        dey
        bmi else
        lda #$06
        sec
        bcs end
else    lda #$05
end     brk

Annahmen: Bedingung ist im Y-Register. Setzen Sie diese Option in der ersten Zeile der beiden Optionen auf 0 oder 1. Das Ergebnis wird im Akkumulator sein.

Nach dem Zählen von Zyklen für beide Möglichkeiten jedes Falls sehen wir also, dass das 1. Konstrukt im Allgemeinen schneller ist; 9 Zyklen, wenn die Bedingung 0 ist, und 10 Zyklen, wenn die Bedingung 1 ist, während Option 2 auch 9 Zyklen ist, wenn die Bedingung 0 ist, aber 13 Zyklen, wenn die Bedingung 1 ist. (Zykluszählungen enthalten nicht die BRK am Ende).

Schlussfolgerung: If only ist schneller als If-Else-Konstrukt.

Und zur Vollständigkeit ist hier eine optimierte value = condition + 5-Lösung:

ldy #$00
lda #$00
tya
adc #$05
brk

Dies reduziert unsere Zeit auf 8 Zyklen (wieder ohne BRK am Ende).

0
Glen Yates