Jeśli instrukcja vs instrukcja if-else, która jest szybsza? [Zamknięte]

Pewnego dnia pokłóciłem się z przyjacielem o te dwa fragmenty. Co jest szybsze i dlaczego?

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

i:

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

A co jeśli valuejest matrycą?

Uwaga: wiem, że value = condition ? 6 : 5;istnieje i spodziewam się, że będzie szybsze, ale nie było takiej opcji.

Edytuj (wymagane przez personel, ponieważ pytanie jest w tej chwili wstrzymane):

• proszę odpowiedzieć, rozważając albo zestaw x86 wygenerowany przez główne kompilatory ( powiedzmy g ++, clang ++, vc, mingw ) w obu zoptymalizowanych i niezoptymalizowanych wersjach lub zestaw MIPS .
• jeśli zestaw jest inny, wyjaśnij, dlaczego wersja jest szybsza i kiedy ( np. „lepsza, ponieważ żadne rozgałęzianie i rozgałęzianie nie ma następującego problemu blahblah” )

TL; DR: W niezoptymalizowanym kodzie, ifbez elsewydaje się nieistotnie bardziej wydajny, ale nawet z włączonym nawet najbardziej podstawowym poziomem optymalizacji kod jest w zasadzie przepisywany na value = condition + 5.

I spróbowaliśmy i generowane zespół do następującego kodu:

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

W gcc 6.3 z wyłączoną optymalizacją ( -O0) istotna różnica to:

 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]

bo ifonly, podczas gdy ifelsema

 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]

Ten ostatni wygląda nieco mniej wydajnie, ponieważ ma dodatkowy skok, ale oba mają co najmniej dwa, a najwyżej trzy zadania, więc chyba że naprawdę musisz wycisnąć ostatnią kroplę wydajności (wskazówka: chyba że pracujesz na promie kosmicznym, nie , a nawet wtedy prawdopodobnie nie) różnica nie będzie zauważalna.

Jednak nawet przy najniższym poziomie optymalizacji ( -O1) obie funkcje zmniejszają się do tego samego:

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

co jest w zasadzie odpowiednikiem

return 5 + condition;

zakładając, że conditionwynosi zero lub jeden. Wyższe poziomy optymalizacji tak naprawdę nie zmieniają wyjścia, z wyjątkiem tego, że udaje im się tego uniknąć movzx, efektywnie zerując EAXrejestr na początku.

Zastrzeżenie: Prawdopodobnie nie powinieneś pisać 5 + conditionsamemu (nawet jeśli standard gwarantuje, że konwersja truena typ całkowity daje 1), ponieważ twój zamiar może nie być od razu oczywisty dla osób czytających twój kod (który może obejmować twoje przyszłe ja). Celem tego kodu jest pokazanie, że to, co tworzy kompilator w obu przypadkach, jest (praktycznie) identyczne. Ciprian Tomoiaga całkiem nieźle to stwierdza w komentarzach:

danej ludzka praca „s jest napisać kod dla ludzi i niech kompilator kodu zapisu dla maszyny .

Odpowiedź firmy CompuChip pokazuje, intże oba są zoptymalizowane pod kątem tego samego zestawu, więc nie ma to znaczenia.

A jeśli wartość jest macierzą?

Zinterpretuję to w sposób bardziej ogólny, tj. Co, jeśli valuejest to typ, którego konstrukcje i zadania są drogie (a ruchy są tanie).

następnie

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

jest nieoptymalne, ponieważ w przypadku, gdy conditionjest prawdziwe, wykonujesz niepotrzebną inicjalizację, init1a następnie wykonujesz przypisanie kopii.

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

To jest lepsze. Ale nadal nieoptymalne, jeśli domyślna konstrukcja jest droga i jeśli konstrukcja kopiowania jest droższa, to inicjalizacja.

Masz rozwiązanie operatora warunkowego, które jest dobre:

T value = condition ? init1 : init2;

Lub, jeśli nie podoba ci się operator warunkowy, możesz utworzyć funkcję pomocniczą w następujący sposób:

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

T value = create(condition);

W zależności od tego, czym init1i init2jesteś, możesz również rozważyć to:

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

Ale znowu muszę podkreślić, że ma to znaczenie tylko wtedy, gdy konstrukcja i zadania są naprawdę drogie dla danego typu. I nawet wtedy tylko poprzez profilowanie wiesz na pewno.

W języku pseudo-asemblera

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

może, ale nie musi, być szybszy niż

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

w zależności od tego, jak zaawansowany jest rzeczywisty procesor. Od najprostszego do najbardziej wyszukanego:

• W przypadku każdego procesora wyprodukowanego po około 1990 r. Dobra wydajność zależy od dopasowania kodu w pamięci podręcznej instrukcji . Dlatego w razie wątpliwości należy zminimalizować rozmiar kodu. To przemawia na korzyść pierwszego przykładu.

• W przypadku podstawowego procesora „ na zamówienie, pięciostopniowego potoku ”, który nadal jest mniej więcej tym, co można znaleźć w wielu mikrokontrolerach, za każdym razem, gdy brana jest gałąź - warunkową lub bezwarunkową - pojawia się bąbelek potoku , więc ważne jest również, aby zminimalizować liczba instrukcji rozgałęzienia. To również przemawia na korzyść pierwszego przykładu.

• Nieco bardziej wyrafinowane procesory - wystarczająco fantazyjne, by wykonywać „wykonanie poza kolejnością ”, ale niewystarczające, by używać najbardziej znanych implementacji tej koncepcji - mogą powodować powstawanie bąbelków potoku, ilekroć napotkają zagrożenie zapisu po zapisie . To przemawia na korzyść drugiego przykładu, w którym r0jest napisane tylko raz, bez względu na wszystko. Procesory te są zwykle dość fantazyjne przetwarzać oddziały bezwarunkowe w instrukcji pobierania poczty, dzięki czemu nie tylko handel karę zapis po zapisie na karę oddziału.

  Nie wiem, czy ktoś nadal robi tego rodzaju procesory. Jednak procesory, które używają „najbardziej znanych implementacji” wykonywania poza kolejnością, prawdopodobnie skracają rogi w rzadziej używanych instrukcjach, więc musisz mieć świadomość, że tego rodzaju rzeczy mogą się zdarzyć. Prawdziwym przykładem są fałszywe zależności danych w rejestrach docelowych popcnti lzcntna procesorach Sandy Bridge .

• Na najwyższym końcu silnik OOO zakończy wydawanie dokładnie tej samej sekwencji operacji wewnętrznych dla obu fragmentów kodu - jest to wersja sprzętowa „nie przejmuj się tym, kompilator i tak wygeneruje ten sam kod maszynowy”. Jednak rozmiar kodu nadal ma znaczenie, a teraz powinieneś również martwić się przewidywalnością gałęzi warunkowej. Błędy przewidywania rozgałęzień mogą potencjalnie spowodować całkowite opróżnienie potoku , co jest katastrofalne dla wydajności; zobacz Dlaczego posortowana tablica jest szybsza niż nieposortowana? aby zrozumieć, jakie może to mieć znaczenie.

  Jeśli gałąź jest wysoce nieprzewidywalna, a twój procesor ma instrukcje warunkowe lub warunkowe ruchy, to jest czas na ich użycie:

      li    #0, r0
      test  r1
      setne r0
  

  lub

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

  Wersja z ustawieniami warunkowymi jest również bardziej kompaktowa niż jakakolwiek inna alternatywa; jeśli ta instrukcja jest dostępna, praktycznie gwarantuje się, że będzie właściwą rzeczą dla tego scenariusza, nawet jeśli gałąź była przewidywalna. Wersja z ruchem warunkowym wymaga dodatkowego rejestru tymczasowego i zawsze marnuje wartość jednej liinstrukcji na wysłanie i wykonanie zasobów; jeśli gałąź była rzeczywiście przewidywalna, wersja rozgałęziona może być szybsza.

W niezoptymalizowanym kodzie pierwszy przykład przypisuje zmienną zawsze raz, a czasami dwa razy. W drugim przykładzie zmienna jest przypisywana tylko raz. Warunek jest taki sam na obu ścieżkach kodu, więc to nie powinno mieć znaczenia. W zoptymalizowanym kodzie zależy to od kompilatora.

Jak zawsze, jeśli jesteś tym zainteresowany, wygeneruj assembler i zobacz, co właściwie robi kompilator.

Co sprawiłoby, że pomyślałbyś, że którykolwiek z nich, nawet jeden liniowiec, jest szybszy lub wolniejszy?

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

Więcej wierszy kodu w języku wysokiego poziomu daje kompilatorowi więcej możliwości do pracy, więc jeśli chcesz stworzyć ogólną zasadę, daj kompilatorowi więcej kodu do pracy. Jeśli algorytm jest taki sam jak w powyższych przypadkach, można by oczekiwać, że kompilator z minimalną optymalizacją to zrozumie.

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

Nic więc dziwnego, że pierwszą funkcję wykonał w innej kolejności, jednak w tym samym czasie wykonania.

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

Miejmy nadzieję, że doszedłeś do wniosku, że mogłeś po prostu spróbować tego, gdyby nie było oczywiste, że różne implementacje tak naprawdę się nie różnią.

Jeśli chodzi o matrycę, nie wiem, jakie to ma znaczenie,

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

zamierzam po prostu umieścić to samo opakowanie if-then-else wokół dużych blobów kodu, czy to value = 5, czy czegoś bardziej skomplikowanego. Podobnie, porównanie, nawet jeśli jest to duży fragment kodu, nadal musi zostać obliczone i jest równe lub nierówne czemuś jest często kompilowane z wartością ujemną, jeśli (warunek) zrób coś jest często kompilowany tak, jakby nie był warunek goto.

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

właśnie przeszliśmy przez to ćwiczenie z kimś innym niedawno na stackoverflow. ten kompilator mips, co ciekawe, w tym przypadku nie tylko zdał sobie sprawę, że funkcje są takie same, ale miał jedną funkcję po prostu przeskoczyć do drugiej, aby zaoszczędzić miejsce na kod. Jednak nie zrobiłem tego tutaj

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

więcej celów.

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

i kompilatory

z tym kodem można by oczekiwać, że różne cele będą również pasować

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

Z technicznego punktu widzenia istnieje różnica w wydajności niektórych z tych rozwiązań, czasami wynikiem jest 5 przypadków, w których następuje przeskok, wynik to 6 kodu, i odwrotnie, czy gałąź jest szybsza niż wykonanie przez? można by się spierać, ale wykonanie powinno być inne. Ale jest to bardziej warunek if vs warunek if not w kodzie, w wyniku czego kompilator wykonuje operację if this jump over else wykonuje się przez. ale nie jest to koniecznie spowodowane stylem kodowania, ale porównaniem i przypadkami if i else w dowolnej składni.

Ok, ponieważ asembler jest jednym z tagów, po prostu zakładam, że twój kod jest pseudokodem (i niekoniecznie c) i tłumaczę go przez człowieka na assembler 6502.

Pierwsza opcja (bez innych)

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

Druga opcja (z else)

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

Założenia: Warunek jest w rejestrze Y ustaw go na 0 lub 1 w pierwszym wierszu dowolnej opcji, wynik będzie akumulowany.

Tak więc po zliczeniu cykli dla obu możliwości każdego przypadku widzimy, że pierwsza konstrukcja jest generalnie szybsza; 9 cykli, gdy warunek wynosi 0, i 10 cykli, gdy warunek wynosi 1, natomiast opcja druga to również 9 cykli, gdy warunek wynosi 0, ale 13 cykli, gdy warunek wynosi 1. ( liczba cykli nie obejmuje BRKkońca ).

Wniosek: If onlyjest szybszy niż If-Elsekonstruowanie.

A dla kompletności, oto zoptymalizowane value = condition + 5rozwiązanie:

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

To skraca nasz czas do 8 cykli ( znowu nie licząc BRKna koniec ).