Czy „zmiana” jest szybsza niż „jeśli”?

Czy switchwyciąg jest rzeczywiście szybszy niż ifwyciąg?

Uruchomiłem poniższy kod na kompilatorze x64 C ++ programu Visual Studio 2010 z /Oxflagą:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAX_COUNT (1 << 29)
size_t counter = 0;

size_t testSwitch()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        switch (counter % 4 + 1)
        {
            case 1: counter += 4; break;
            case 2: counter += 3; break;
            case 3: counter += 2; break;
            case 4: counter += 1; break;
        }
    }
    return 1000 * (clock() - start) / CLOCKS_PER_SEC;
}

size_t testIf()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = counter % 4 + 1;
        if (c == 1) { counter += 4; }
        else if (c == 2) { counter += 3; }
        else if (c == 3) { counter += 2; }
        else if (c == 4) { counter += 1; }
    }
    return 1000 * (clock() - start) / CLOCKS_PER_SEC;
}

int main()
{
    printf("Starting...\n");
    printf("Switch statement: %u ms\n", testSwitch());
    printf("If     statement: %u ms\n", testIf());
}

i uzyskałem te wyniki:

Instrukcja switch: 5261 ms
If instrukcja: 5196 ms

Z tego, czego się nauczyłem, switchinstrukcje najwyraźniej wykorzystują tabele skoków do optymalizacji rozgałęzień.

Pytania:

1. Jak wyglądałaby podstawowa tabela skoków w wersji x86 lub x64?

2. Czy ten kod używa tabeli skoków?

3. Dlaczego w tym przykładzie nie ma różnicy w wydajności? Czy istnieje sytuacja, w której nie jest istotna różnica wydajności?

Demontaż kodu:

testIf:

13FE81B10 sub  rsp,48h 
13FE81B14 call qword ptr [__imp_clock (13FE81128h)] 
13FE81B1A mov  dword ptr [start],eax 
13FE81B1E mov  qword ptr [i],0 
13FE81B27 jmp  testIf+26h (13FE81B36h) 
13FE81B29 mov  rax,qword ptr [i] 
13FE81B2E inc  rax  
13FE81B31 mov  qword ptr [i],rax 
13FE81B36 cmp  qword ptr [i],20000000h 
13FE81B3F jae  testIf+0C3h (13FE81BD3h) 
13FE81B45 xor  edx,edx 
13FE81B47 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81B4E mov  ecx,4 
13FE81B53 div  rax,rcx 
13FE81B56 mov  rax,rdx 
13FE81B59 inc  rax  
13FE81B5C mov  qword ptr [c],rax 
13FE81B61 cmp  qword ptr [c],1 
13FE81B67 jne  testIf+6Dh (13FE81B7Dh) 
13FE81B69 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81B70 add  rax,4 
13FE81B74 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81B7B jmp  testIf+0BEh (13FE81BCEh) 
13FE81B7D cmp  qword ptr [c],2 
13FE81B83 jne  testIf+89h (13FE81B99h) 
13FE81B85 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81B8C add  rax,3 
13FE81B90 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81B97 jmp  testIf+0BEh (13FE81BCEh) 
13FE81B99 cmp  qword ptr [c],3 
13FE81B9F jne  testIf+0A5h (13FE81BB5h) 
13FE81BA1 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81BA8 add  rax,2 
13FE81BAC mov  qword ptr [counter (13FE835D0h)],rax 
13FE81BB3 jmp  testIf+0BEh (13FE81BCEh) 
13FE81BB5 cmp  qword ptr [c],4 
13FE81BBB jne  testIf+0BEh (13FE81BCEh) 
13FE81BBD mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81BC4 inc  rax  
13FE81BC7 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81BCE jmp  testIf+19h (13FE81B29h) 
13FE81BD3 call qword ptr [__imp_clock (13FE81128h)] 
13FE81BD9 sub  eax,dword ptr [start] 
13FE81BDD imul eax,eax,3E8h 
13FE81BE3 cdq       
13FE81BE4 mov  ecx,3E8h 
13FE81BE9 idiv eax,ecx 
13FE81BEB cdqe      
13FE81BED add  rsp,48h 
13FE81BF1 ret       

testSwitch:

13FE81C00 sub  rsp,48h 
13FE81C04 call qword ptr [__imp_clock (13FE81128h)] 
13FE81C0A mov  dword ptr [start],eax 
13FE81C0E mov  qword ptr [i],0 
13FE81C17 jmp  testSwitch+26h (13FE81C26h) 
13FE81C19 mov  rax,qword ptr [i] 
13FE81C1E inc  rax  
13FE81C21 mov  qword ptr [i],rax 
13FE81C26 cmp  qword ptr [i],20000000h 
13FE81C2F jae  testSwitch+0C5h (13FE81CC5h) 
13FE81C35 xor  edx,edx 
13FE81C37 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81C3E mov  ecx,4 
13FE81C43 div  rax,rcx 
13FE81C46 mov  rax,rdx 
13FE81C49 inc  rax  
13FE81C4C mov  qword ptr [rsp+30h],rax 
13FE81C51 cmp  qword ptr [rsp+30h],1 
13FE81C57 je   testSwitch+73h (13FE81C73h) 
13FE81C59 cmp  qword ptr [rsp+30h],2 
13FE81C5F je   testSwitch+87h (13FE81C87h) 
13FE81C61 cmp  qword ptr [rsp+30h],3 
13FE81C67 je   testSwitch+9Bh (13FE81C9Bh) 
13FE81C69 cmp  qword ptr [rsp+30h],4 
13FE81C6F je   testSwitch+0AFh (13FE81CAFh) 
13FE81C71 jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81C73 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81C7A add  rax,4 
13FE81C7E mov  qword ptr [counter (13FE835D0h)],rax 
13FE81C85 jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81C87 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81C8E add  rax,3 
13FE81C92 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81C99 jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81C9B mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81CA2 add  rax,2 
13FE81CA6 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81CAD jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81CAF mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81CB6 inc  rax  
13FE81CB9 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81CC0 jmp  testSwitch+19h (13FE81C19h) 
13FE81CC5 call qword ptr [__imp_clock (13FE81128h)] 
13FE81CCB sub  eax,dword ptr [start] 
13FE81CCF imul eax,eax,3E8h 
13FE81CD5 cdq       
13FE81CD6 mov  ecx,3E8h 
13FE81CDB idiv eax,ecx 
13FE81CDD cdqe      
13FE81CDF add  rsp,48h 
13FE81CE3 ret       

Aktualizacja:

Ciekawe wyniki tutaj . Nie jestem jednak pewien, dlaczego ktoś jest szybszy, a drugi wolniejszy.

Kompilator może dokonać kilku optymalizacji na przełączniku. Nie wydaje mi się jednak, aby często wspominano o „stole skokowym”, ponieważ działa ona tylko wtedy, gdy dane wejściowe można w jakiś sposób ograniczyć.

C Pseudokod dla „tabeli skoków” byłby mniej więcej taki - zwróć uwagę, że w praktyce kompilator musiałby wstawić jakiś test if wokół tabeli, aby upewnić się, że dane wejściowe są prawidłowe w tabeli. Zauważ też, że działa to tylko w konkretnym przypadku, gdy dane wejściowe są ciągiem kolejnych liczb.

Jeśli liczba rozgałęzień w przełączniku jest bardzo duża, kompilator może wykonywać takie operacje, jak wyszukiwanie binarne na wartościach przełącznika, co (moim zdaniem) byłoby znacznie bardziej przydatną optymalizacją, ponieważ znacznie zwiększa wydajność niektórych scenariusze są tak ogólne, jak przełącznik, i nie powodują większego wygenerowania kodu. Ale żeby to zobaczyć, twój kod testowy potrzebowałby DUŻO więcej oddziałów, aby zobaczyć różnicę.

Aby odpowiedzieć na konkretne pytania:

1. Clang generuje taki, który wygląda następująco :

   test_switch(char):                       # @test_switch(char)
           movl    %edi, %eax
           cmpl    $19, %edi
           jbe     .LBB0_1
           retq
   .LBB0_1:
           jmpq    *.LJTI0_0(,%rax,8)
           jmp     void call<0u>()         # TAILCALL
           jmp     void call<1u>()         # TAILCALL
           jmp     void call<2u>()         # TAILCALL
           jmp     void call<3u>()         # TAILCALL
           jmp     void call<4u>()         # TAILCALL
           jmp     void call<5u>()         # TAILCALL
           jmp     void call<6u>()         # TAILCALL
           jmp     void call<7u>()         # TAILCALL
           jmp     void call<8u>()         # TAILCALL
           jmp     void call<9u>()         # TAILCALL
           jmp     void call<10u>()        # TAILCALL
           jmp     void call<11u>()        # TAILCALL
           jmp     void call<12u>()        # TAILCALL
           jmp     void call<13u>()        # TAILCALL
           jmp     void call<14u>()        # TAILCALL
           jmp     void call<15u>()        # TAILCALL
           jmp     void call<16u>()        # TAILCALL
           jmp     void call<17u>()        # TAILCALL
           jmp     void call<18u>()        # TAILCALL
           jmp     void call<19u>()        # TAILCALL
   .LJTI0_0:
           .quad   .LBB0_2
           .quad   .LBB0_3
           .quad   .LBB0_4
           .quad   .LBB0_5
           .quad   .LBB0_6
           .quad   .LBB0_7
           .quad   .LBB0_8
           .quad   .LBB0_9
           .quad   .LBB0_10
           .quad   .LBB0_11
           .quad   .LBB0_12
           .quad   .LBB0_13
           .quad   .LBB0_14
           .quad   .LBB0_15
           .quad   .LBB0_16
           .quad   .LBB0_17
           .quad   .LBB0_18
           .quad   .LBB0_19
           .quad   .LBB0_20
           .quad   .LBB0_21
   

2. Mogę powiedzieć, że nie używa tabeli skoków - 4 instrukcje porównania są wyraźnie widoczne:

   13FE81C51 cmp  qword ptr [rsp+30h],1 
   13FE81C57 je   testSwitch+73h (13FE81C73h) 
   13FE81C59 cmp  qword ptr [rsp+30h],2 
   13FE81C5F je   testSwitch+87h (13FE81C87h) 
   13FE81C61 cmp  qword ptr [rsp+30h],3 
   13FE81C67 je   testSwitch+9Bh (13FE81C9Bh) 
   13FE81C69 cmp  qword ptr [rsp+30h],4 
   13FE81C6F je   testSwitch+0AFh (13FE81CAFh) 
   

   Rozwiązanie oparte na tabeli skoków w ogóle nie korzysta z porównania.

3. Za mało gałęzi, aby kompilator wygenerował tabelę skoków, lub kompilator po prostu ich nie generuje. Nie jestem pewien który.

EDYCJA 2014 : Odbyła się dyskusja z udziałem osób zaznajomionych z optymalizatorem LLVM, mówiąc, że optymalizacja tabeli skoków może być ważna w wielu scenariuszach; np. w przypadkach, w których występuje wyliczenie z wieloma wartościami i wiele przypadków przeciwko wartościom we wspomnianym wyliczeniu. To powiedziawszy, trzymam się tego, co powiedziałem powyżej w 2011 r. - zbyt często widzę, że ludzie myślą: „jeśli zrobię z tego zmianę, będzie to samo bez względu na to, ile mam przypadków” - i to jest całkowicie fałszywe. Nawet z tabelą skoków otrzymujesz pośredni koszt skoku i płacisz za wpisy w tabeli dla każdego przypadku; a przepustowość pamięci to wielka sprawa na nowoczesnym sprzęcie.

Napisz kod dla czytelności. Każdy kompilator warty swojej soli zobaczy drabinę if / else i przekształci go w równoważny przełącznik lub odwrotnie, jeśli byłoby to szybsze.

Na twoje pytanie:

1. Jak wyglądałaby podstawowa tabela skoków w wersji x86 lub x64?

Tabela skoków to adres pamięci, który utrzymuje wskaźnik do etykiet w postaci struktury tablicowej. poniższy przykład pomoże ci zrozumieć, w jaki sposób układane są tabele skoków

00B14538  D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 D8 09 AB 00  Ø.«.Ø.«.Ø.«.Ø.«.
00B14548  D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 00 00 00 00  Ø.«.Ø.«.Ø.«.....
00B14558  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
00B14568  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

Gdzie 00B14538 jest wskaźnikiem do tabeli skoków, a wartość jak D8 09 AB 00 oznacza wskaźnik etykiety.

2. Czy ten kod używa tabeli skoków? Nie w tym przypadku.

3.Dlaczego w tym przykładzie nie ma różnicy w wydajności?

Nie ma różnicy w wydajności, ponieważ instrukcja dla obu przypadków wygląda tak samo, bez tabeli skoków.

4. Czy jest jakaś sytuacja, w której występuje znacząca różnica w wydajności?

Jeśli masz bardzo długą sekwencję sprawdzania if , w takim przypadku użycie tabeli skoków poprawia wydajność (instrukcje rozgałęziania / jmp są drogie, jeśli nie przewidują prawie idealnie), ale wiąże się to z kosztem pamięci.

Kod wszystkich instrukcji porównywania również ma pewien rozmiar, więc szczególnie przy 32-bitowych wskaźnikach lub przesunięciach wyszukiwanie pojedynczej tabeli skoków może nie kosztować o wiele więcej rozmiaru w pliku wykonywalnym.

Wniosek: Kompilator jest wystarczająco inteligentny, aby obsługiwać takie przypadki i generować odpowiednie instrukcje :)

Kompilator może kompilować instrukcję switch jako kod równoważny instrukcji if lub tworzyć tabelę skoków. Prawdopodobnie wybierze jeden na drugim na podstawie tego, co wykona się najszybciej lub wygeneruje najmniejszy kod nieco w zależności od tego, co określiłeś w opcjach kompilatora - w najgorszym przypadku będzie to taka sama szybkość jak instrukcje if

Ufałbym kompilatorowi, aby dokonał najlepszego wyboru i skupił się na tym, co czyni kod najbardziej czytelnym.

Jeśli liczba przypadków stanie się bardzo duża, tabela skoków będzie znacznie szybsza niż seria if. Jeśli jednak kroki między wartościami są bardzo duże, tabela skoków może stać się duża, a kompilator może zdecydować, aby jej nie generować.

Skąd wiesz, że Twój komputer nie wykonywał zadań niezwiązanych z testem podczas pętli testowej przełącznika i wykonywał mniej zadań podczas pętli testowej if? Twoje wyniki testu nie pokazują niczego jako:

1. różnica jest bardzo mała
2. jest tylko jeden wynik, a nie seria wyników
3. jest za mało przypadków

Moje wyniki:

Dodałem:

printf("counter: %u\n", counter);

do końca, aby nie zoptymalizować pętli, ponieważ licznik nigdy nie był używany w twoim przykładzie, więc dlaczego kompilator miałby wykonywać pętlę? Natychmiast zmiana zawsze wygrywała, nawet przy takim mikro-teście porównawczym.

Drugi problem z twoim kodem to:

switch (counter % 4 + 1)

w twojej pętli przełączania, w przeciwieństwie do

const size_t c = counter % 4 + 1; 

w twojej pętli if. Bardzo duża różnica, jeśli to naprawisz. Uważam, że umieszczenie instrukcji w instrukcji switch powoduje, że kompilator wysyła wartość bezpośrednio do rejestrów procesora, zamiast umieszczać ją najpierw na stosie. Jest to zatem korzystne dla instrukcji switch, a nie dla zrównoważonego testu.

No i myślę, że powinieneś także zresetować licznik między testami. W rzeczywistości prawdopodobnie powinieneś użyć jakiegoś losowego numeru zamiast +1, +2, +3 itd., Ponieważ prawdopodobnie coś tam zoptymalizuje. Przez liczbę losową rozumiem na przykład liczbę opartą na bieżącym czasie. W przeciwnym razie kompilator może zamienić obie funkcje w jedną długą operację matematyczną i nawet nie zawracać sobie głowy żadnymi pętlami.

Zmodyfikowałem kod Ryana tylko po to, aby mieć pewność, że kompilator nie będzie w stanie zrozumieć rzeczy przed uruchomieniem kodu:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAX_COUNT (1 << 26)
size_t counter = 0;

long long testSwitch()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = rand() % 20 + 1;

        switch (c)
        {
                case 1: counter += 20; break;
                case 2: counter += 33; break;
                case 3: counter += 62; break;
                case 4: counter += 15; break;
                case 5: counter += 416; break;
                case 6: counter += 3545; break;
                case 7: counter += 23; break;
                case 8: counter += 81; break;
                case 9: counter += 256; break;
                case 10: counter += 15865; break;
                case 11: counter += 3234; break;
                case 12: counter += 22345; break;
                case 13: counter += 1242; break;
                case 14: counter += 12341; break;
                case 15: counter += 41; break;
                case 16: counter += 34321; break;
                case 17: counter += 232; break;
                case 18: counter += 144231; break;
                case 19: counter += 32; break;
                case 20: counter += 1231; break;
        }
    }
    return 1000 * (long long)(clock() - start) / CLOCKS_PER_SEC;
}

long long testIf()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = rand() % 20 + 1;
        if (c == 1) { counter += 20; }
        else if (c == 2) { counter += 33; }
        else if (c == 3) { counter += 62; }
        else if (c == 4) { counter += 15; }
        else if (c == 5) { counter += 416; }
        else if (c == 6) { counter += 3545; }
        else if (c == 7) { counter += 23; }
        else if (c == 8) { counter += 81; }
        else if (c == 9) { counter += 256; }
        else if (c == 10) { counter += 15865; }
        else if (c == 11) { counter += 3234; }
        else if (c == 12) { counter += 22345; }
        else if (c == 13) { counter += 1242; }
        else if (c == 14) { counter += 12341; }
        else if (c == 15) { counter += 41; }
        else if (c == 16) { counter += 34321; }
        else if (c == 17) { counter += 232; }
        else if (c == 18) { counter += 144231; }
        else if (c == 19) { counter += 32; }
        else if (c == 20) { counter += 1231; }
    }
    return 1000 * (long long)(clock() - start) / CLOCKS_PER_SEC;
}

int main()
{
    srand(time(NULL));
    printf("Starting...\n");
    printf("Switch statement: %lld ms\n", testSwitch()); fflush(stdout);
    printf("counter: %d\n", counter);
    counter = 0;
    srand(time(NULL));
    printf("If     statement: %lld ms\n", testIf()); fflush(stdout);
    printf("counter: %d\n", counter);
} 

przełącznik: 3740
jeśli: 3980

(podobne wyniki dla wielu prób)

Zmniejszyłem również liczbę przypadków / ifs do 5 i funkcja przełączania wciąż wygrywa.

Dobry kompilator optymalizujący, taki jak MSVC, może generować:

1. prosty stół skokowy, jeśli skrzynie są ustawione w ładnym długim zasięgu
2. rzadki (dwupoziomowy) stół skokowy, jeśli jest wiele luk
3. seria ifs, jeśli liczba przypadków jest niewielka lub wartości nie są blisko siebie
4. kombinacja powyższego, jeśli przypadki reprezentują kilka grup ściśle rozmieszczonych zakresów.

Krótko mówiąc, jeśli przełącznik wydaje się być wolniejszy niż seria ifs, kompilator może po prostu przekonwertować go na jeden. I prawdopodobnie będzie to nie tylko sekwencja porównań dla każdego przypadku, ale drzewo wyszukiwania binarnego. Zobacz tutaj przykład.

Odpowiem 2) i zrobię kilka ogólnych komentarzy. 2) Nie, nie ma tabeli skoków w opublikowanym kodzie zestawu. Tabela skoków to tabela miejsc docelowych skoków i jedna lub dwie instrukcje, aby przejść bezpośrednio do indeksowanej lokalizacji z tabeli. Tabela skoków byłaby bardziej sensowna, gdy istnieje wiele możliwych miejsc docelowych przełączników. Być może optymalizator wie, że prosta, jeśli inaczej logika jest szybsza, chyba że liczba miejsc docelowych jest większa niż pewien próg. Spróbuj ponownie swój przykład, powiedzmy 20 możliwości zamiast 4.

Byłem zaintrygowany i spojrzałem na to, co mogę zmienić w twoim przykładzie, aby szybciej uruchomić instrukcję switch.

Jeśli dojdziesz do 40 instrukcji if i dodasz przypadek 0, wtedy blok if będzie działał wolniej niż równoważna instrukcja switch. Mam wyniki tutaj: https://www.ideone.com/KZeCz .

Efekt usunięcia przypadku 0 można zobaczyć tutaj: https://www.ideone.com/LFnrX .

Oto niektóre wyniki ze starego (obecnie trudnego do znalezienia) testu porównawczego bench ++:

Test Name:   F000003                         Class Name:  Style
CPU Time:       0.781  nanoseconds           plus or minus     0.0715
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 2-way if/else if statement
 compare this test with F000004

Test Name:   F000004                         Class Name:  Style
CPU Time:        1.53  nanoseconds           plus or minus     0.0767
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 2-way switch statement
 compare this test with F000003

Test Name:   F000005                         Class Name:  Style
CPU Time:        7.70  nanoseconds           plus or minus      0.385
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way if/else if statement
 compare this test with F000006

Test Name:   F000006                         Class Name:  Style
CPU Time:        2.00  nanoseconds           plus or minus     0.0999
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way switch statement
 compare this test with F000005

Test Name:   F000007                         Class Name:  Style
CPU Time:        3.41  nanoseconds           plus or minus      0.171
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way sparse switch statement
 compare this test with F000005 and F000006

Widzimy z tego, że (na tym komputerze, z tym kompilatorem - VC ++ 9.0 x64), każdy iftest zajmuje około 0,7 nanosekundy. Wraz ze wzrostem liczby testów czas skaluje się prawie idealnie liniowo.

W instrukcji switch prawie nie ma różnicy prędkości między testem 2-drogowym a 10-drożnym, o ile wartości są gęste. Test 10-krotny z wartościami rzadkimi zajmuje około 1,6x więcej czasu niż test 10-krotny z wartościami gęstymi - ale nawet przy wartościach rzadkich, wciąż lepszym niż dwukrotność prędkości 10-krotnego if/ else if.

Podsumowując: użycie tylko testu czterokierunkowego tak naprawdę nie pokaże ci dużo o wydajności switchvs if/ else. Jeśli spojrzymy na liczby z tego kodu, łatwo interpolować fakt, że w przypadku testu 4-drogowego spodziewalibyśmy się, że oba przyniosą całkiem podobne wyniki (~ 2,8 nanosekundy dla if/ else, ~ 2,0 dla switch).

Zauważ, że kiedy przełącznik NIE jest skompilowany do tabeli skoków, możesz bardzo często pisać, jeśli jest on bardziej wydajny niż przełącznik ...

(1) jeśli przypadki mają uporządkowanie, a nie najgorsze testowanie wszystkich N, możesz napisać „jeśli”, aby sprawdzić, czy w górnej czy dolnej połowie, a następnie w każdej połowie tego stylu wyszukiwania binarnego… najgorszym przypadkiem jest logN zamiast N

(2) jeśli niektóre przypadki / grupy są znacznie częstsze niż inne przypadki, wówczas zaprojektowanie swojego, aby najpierw izolować te przypadki, może przyspieszyć średni czas

Nie, są to, jeśli następnie skocz inaczej, jeśli następnie skacz inaczej ... Tabela skoków zawiera tabelę adresów lub używa skrótu lub czegoś podobnego.

Szybsze lub wolniejsze jest subiektywne. Możesz na przykład ustawić przypadek 1 jako ostatni zamiast pierwszego, a jeśli program testowy lub program w świecie rzeczywistym używał przypadku 1 przez większość czasu, kod byłby wolniejszy przy tej implementacji. Tak więc zmiana układu listy spraw, w zależności od implementacji, może mieć duże znaczenie.

Jeśli używałeś przypadków 0-3 zamiast 1-4, kompilator mógł użyć tabeli skoków, kompilator powinien był wymyślić usunięcie +1. Być może była to niewielka liczba przedmiotów. Na przykład, jeśli zrobiłeś 0 - 15 lub 0 - 31, to mógł zaimplementować go ze stołem lub użyć innego skrótu. Kompilator może dowolnie wybierać sposób implementacji, o ile spełnia on funkcje kodu źródłowego. I to dotyczy różnic w kompilatorach, różnicach wersji i różnicach w optymalizacji. Jeśli chcesz mieć tabelę skoków, zrób tabelę skoków, jeśli chcesz drzewa if-then-else, stwórz drzewo if-then-else. Jeśli chcesz, aby kompilator decydował, użyj instrukcji switch / case.

Nie jestem jednak pewien, dlaczego ktoś jest szybszy, a drugi wolniejszy.

W rzeczywistości nie jest to zbyt trudne do wytłumaczenia ... Jeśli pamiętasz, że źle zaplanowane gałęzie są dziesiątki do setek razy droższe niż prawidłowo przewidywane gałęzie.

W % 20wersji pierwszy przypadek / if jest zawsze tym, który uderza. Współczesne procesory „uczą się”, które gałęzie są zwykle pobierane, a które nie, dzięki czemu mogą łatwo przewidzieć, jak zachowa się ta gałąź podczas niemal każdej iteracji pętli. To wyjaśnia, dlaczego leci wersja „jeśli”; nigdy nie musi wykonywać niczego po pierwszym teście i (poprawnie) przewiduje wynik tego testu dla większości iteracji. Oczywiście „przełącznik” jest implementowany nieco inaczej - być może nawet tabela skoków, która może być powolna dzięki obliczonej gałęzi.

W % 21wersji gałęzie są zasadniczo losowe. Dlatego nie tylko wiele z nich wykonuje każdą iterację, ale procesor nie może zgadnąć, w którą stronę pójdą. Jest to przypadek, w którym pomocna może być tabela skoków (lub inna optymalizacja „przełączania”).

Bardzo trudno jest przewidzieć, jak fragment kodu będzie działał przy użyciu nowoczesnego kompilatora i procesora, a z każdą generacją staje się coraz trudniejszy. Najlepszą radą jest „nawet nie próbuj, zawsze profiluj”. Ta rada staje się lepsza - a liczba osób, które mogą ją zignorować, zmniejsza się z każdym rokiem.

Wszystko to oznacza, że ​​moje wyjaśnienie powyżej jest w dużej mierze domysłem. :-)

Żaden. W większości przypadków, gdy wchodzisz do asemblera i robisz prawdziwe pomiary wydajności, twoje pytanie jest po prostu niewłaściwe. Dla podanego przykładu twoje myślenie jest zdecydowanie za krótkie

counter += (4 - counter % 4);

wydaje mi się, że jest to prawidłowe wyrażenie przyrostowe, którego powinieneś używać.