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

242

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.

użytkownik541686
źródło
47
Co, u licha, głosują za zamknięciem tego myślenia? Czy tak wierzą w ideę optymalizującego kompilatora, że ​​jakakolwiek myśl o jego generowaniu kodu mniej niż idealnego jest herezją? Czy sama idea jakiejkolwiek optymalizacji nigdzie obrażać je?
Crashworks,
6
Co dokładnie jest nie tak z tym pytaniem?
Tugrul Ates
25
Dla każdego, kto zastanawia się, co jest nie tak z tym pytaniem : na początek nie jest to pytanie, są to 3 pytania, co oznacza, że ​​wiele odpowiedzi dotyczy teraz różnych problemów. Oznacza to, że trudno będzie zaakceptować odpowiedź, która odpowie na wszystko . Dodatkowo, typową reakcją na kolano w odpowiedzi na powyższe pytanie jest zamknięcie go jako „niezupełnie interesujące” głównie ze względu na fakt, że na tym poziomie optymalizacji prawie zawsze optymalizujesz przedwcześnie . Na koniec, 5196 vs. 5261 nie powinno wystarczyć, aby się tym przejmować. Napisz logiczny kod, który ma sens.
Lasse V. Karlsen
40
@Lasse: czy naprawdę wolałby mnie aby umieścić trzy pytania na SO zamiast? Ponadto: 5196 vs. 5261 shouldn't be enough to actually care-> Nie jestem pewien, czy źle zrozumiałeś pytanie, czy też źle zrozumiałem twój komentarz, ale czy sedno mojego pytania nie polega na pytaniu, dlaczego nie ma różnicy? (Czy kiedykolwiek twierdziłem, że jest to istotna różnica?)
user541686,
5
@Robert: Cóż, ma więcej niż 20 komentarzy, ponieważ są to meta-komentarze. Tutaj jest tylko 7 komentarzy związanych z pytaniem. Opinia: Nie widzę tutaj „opinii”. Jest powód , dla którego nie widzę różnicy w wydajności, nie? Czy to tylko smak? Debata: Może, ale dla mnie wygląda to na zdrową debatę, tak jak widziałem w innych miejscach na SO (daj mi znać, czy jest coś przeciwnego). Argumenty: nie widzę tu żadnych argumentów (chyba, że ​​traktujesz to jako synonim „debaty”?). Rozszerzona dyskusja: jeśli dodasz te meta-komentarze.
user541686,

Odpowiedzi:

122

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.

Billy ONeal
źródło
3
+1 za faktyczną odpowiedź na pytanie i za przydatne informacje. :-) Jednak pytanie: Z tego, co rozumiem, tabela skoków używa skoków pośrednich ; czy to jest poprawne? Jeśli tak, to czy zwykle nie jest to wolniejsze ze względu na trudniejsze pobieranie / tworzenie potoków?
user541686,
1
@ Mehrdad: Tak, używa skoków pośrednich. Jednak jeden skok pośredni (z przeciągnięciem rurociągu, z którym jest dostarczany) może być mniejszy niż setki skoków bezpośrednich. :)
Billy ONeal
1
@Mehrdad: Nie, niestety. :( Cieszę się, że jestem w obozie ludzi, którzy zawsze myślą, że IF jest bardziej czytelny! :)
Billy ONeal
1
Kilka znaków - „[przełączniki] działają tylko wtedy, gdy dane wejściowe można w jakiś sposób ograniczyć” „trzeba wstawić jakiś formularz if test wokół tabeli, aby upewnić się, że dane wejściowe są prawidłowe w tabeli. Zwróć też uwagę, że działa tylko w określonych przypadek, gdy dane wejściowe są ciągiem kolejnych liczb. ”: całkowicie możliwe jest posiadanie rzadko zapełnianej tabeli, w której potencjalny wskaźnik jest odczytywany i tylko wtedy, gdy skok inny niż NULL jest wykonywany, w przeciwnym razie domyślny przypadek, jeśli którykolwiek zostanie przeskoczony, następnie switchwyjścia. Soren powiedział kilka innych rzeczy, które chciałem powiedzieć po przeczytaniu tej odpowiedzi.
Tony Delroy,
2
„Każdy kompilator warty swojej soli zobaczy drabinę if / else i przekształci go w równoważny przełącznik lub odwrotnie” - jakieś wsparcie dla tego twierdzenia? kompilator może założyć, że kolejność ifklauzul została już ręcznie dostosowana, aby pasowała do częstotliwości i względnych potrzeb w zakresie wydajności, przy czym switchtradycyjnie postrzegane jest jako otwarte zaproszenie do optymalizacji, niezależnie od wyboru kompilatora. Dobry punkt, skacząc obok switch:-). Rozmiar kodu zależy od przypadków / zakresu - może być lepszy. Wreszcie niektóre wyliczenia, pola bitowe i charscenariusze są z natury ważne / ograniczone i wolne od kosztów ogólnych.
Tony Delroy
47

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

wprowadź opis zdjęcia tutaj

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 :)

zaszyfrowane
źródło
(edytuj: nvm, odpowiedź Billy'ego zawiera już to, co sugerowałem. Myślę, że to fajny suplement.) Dobrze byłoby dołączyć gcc -Sdane wyjściowe: sekwencja wpisów .long L1/ .long L2table jest bardziej znacząca niż zrzut heksowy i bardziej przydatna dla kogoś, kto chce nauczyć się patrzeć na kompilator. (Chociaż wydaje mi się, że wystarczy spojrzeć na kod przełącznika, aby zobaczyć, czy jest to pośredni plik jmp lub plik jcc).
Peter Cordes,
31

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ć.

Soren
źródło
13
Nie sądzę, że to odpowiada na pytanie OP. W ogóle.
Billy ONeal
5
@Soren: Gdyby to było „podstawowe pytanie”, nie zawracałbym sobie głowy 179 innymi liniami w pytaniu, byłby to tylko 1 wiersz. :-)
user541686
8
@ Soren: Widzę co najmniej 3 ponumerowane pytania cząstkowe jako część pytania PO. Zaliczyłeś tylko tę samą odpowiedź, która dotyczy wszystkich pytań dotyczących „wydajności” - a mianowicie to, że musisz najpierw zmierzyć. Pomyśl, że być może Mehrdad już dokonał pomiaru i wyizolował ten fragment kodu, aby był gorącym punktem. W takich przypadkach twoja odpowiedź jest gorsza niż bezwartościowa, to hałas.
Billy ONeal
2
Pomiędzy tym, co jest stołem skokowym, a tym, co nie zależy od twojej definicji, jest niewyraźna linia. Przekazałem informacje na pytanie 3.
Soren,
2
@wnoise: Jeśli jest to jedyna właściwa odpowiedź, nigdy nie byłoby powodu, aby zadawać pytania dotyczące wydajności. Jednak niektórzy z nas w świecie rzeczywistym mierzą nasze oprogramowanie i czasami nie wiemy, jak przyspieszyć fragment kodu po zmierzeniu. To oczywiste, że Mehrdad włożył trochę wysiłku w to pytanie, zanim je zadał; i myślę, że na jego konkretne pytania można odpowiedzieć więcej niż tylko.
Billy ONeal,
13

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.

BobTurbo
źródło
Idk, nie mogę tego udowodnić; czy otrzymujesz różne wyniki?
user541686,
+1: Benchmarking jest trudny i naprawdę nie można wyciągać żadnych wniosków z niewielkiej różnicy czasu na jednym uruchomieniu na normalnym komputerze. Możesz spróbować uruchomić dużą liczbę testów i przeprowadzić statystyki dotyczące wyników. Lub zliczanie cykli procesora podczas kontrolowanego wykonywania w emulatorze.
Thomas Padron-McCarthy
Eee, gdzie dokładnie dodałeś printoświadczenie? Dodałem go pod koniec całego programu i nie widziałem żadnej różnicy. Nie rozumiem też, czym jest „problem” z tym drugim… czy możesz wyjaśnić, czym jest „bardzo duża różnica”?
user541686,
1
@BobTurbo: 45983493 trwa ponad 12 godzin. Czy to była literówka?
Gus
1
świetnie, teraz muszę to zrobić jeszcze raz :)
BobTurbo,
7

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.

Igor Skochinsky
źródło
W rzeczywistości kompilator jest również w stanie zastąpić go hashem i skokiem, który działa lepiej niż proponowane rzadkie dwupoziomowe rozwiązanie.
Alice,
5

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.

Bill Forster
źródło
+1 dzięki za odpowiedź na # 2! :) (Przy okazji, oto wyniki z większymi możliwościami.)
user541686,
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 .

Ryan Gross
źródło
1
Twoje linki się zepsuły.
TS
4

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).

Jerry Coffin
źródło
1
Trudno się dowiedzieć, co z tym zrobić, jeśli nie wiemy, czy test celowo szuka wartości, która nie jest dopasowana lub tylko na końcu łańcucha if/ elsekontra rozproszenie ich itp. Nie można znaleźć bench++źródeł po 10 minut google.
Tony Delroy,
3

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

Brian Kennedy
źródło
Jest to wyraźnie nieprawdziwe; kompilatory są więcej niż w stanie ZROBIĆ te optymalizacje.
Alice,
1
Alice, skąd kompilator ma wiedzieć, które przypadki będą występować częściej niż inne przypadki w oczekiwanych obciążeniach? (O: Nie może wiedzieć, więc nie może dokonać takiej optymalizacji.)
Brian Kennedy
(1) można łatwo wykonać i jest to wykonywane w niektórych kompilatorach, po prostu przez wyszukiwanie binarne. (2) można przewidzieć na różne sposoby lub wskazać kompilatorowi. Czy nigdy nie korzystałeś z GCC jako „prawdopodobne” lub „mało prawdopodobne”?
Alice,
Niektóre kompilatory pozwalają na uruchomienie programu w trybie, który gromadzi statystyki, a następnie optymalizuje na podstawie tych informacji.
Phil1970
2

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.

old_timer
źródło
2

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. :-)

Nemo
źródło
2
Nie wiem, skąd setki razy wolniej. Najgorszym przypadkiem źle przewidywanej gałęzi jest przeciągnięcie rurociągu, które byłoby ~ 20 razy wolniejsze na większości współczesnych procesorów. Nie setki razy. (Okej, jeśli używasz starego układu NetBurst, może być 35 razy wolniejszy ...)
Billy ONeal
@Billy: OK, więc trochę patrzę w przyszłość. W procesorach Sandy Bridge „Każda źle przewidywana gałąź spłukuje cały rurociąg, tracąc pracę do około stu instrukcji w locie”. Rurociągi naprawdę pogłębiają się z każdym pokoleniem, ogólnie ...
Nemo,
1
Nie prawda. P4 (NetBurst) miał 31 etapów budowy; Sandy Bridge ma znacznie mniej etapów. Myślę, że „utrata pracy około 100 instrukcji” zakłada się, że pamięć podręczna instrukcji zostanie unieważniona. W przypadku ogólnego skoku pośredniego, który faktycznie się zdarza, ale dla czegoś takiego jak tabela skoków prawdopodobnie cel skoku pośredniego znajduje się gdzieś w pamięci podręcznej instrukcji.
Billy ONeal,
@Billy: Nie sądzę, żebyśmy się nie zgadzali. Moje oświadczenie brzmiało: „Nieodpowiednie gałęzie są dziesiątki do setek razy droższe niż prawidłowo przewidywane gałęzie”. Lekka przesada, być może ... Ale dzieje się coś więcej niż tylko trafienia w I-cache i głębokość potoku wykonania; z tego co przeczytałem, sama kolejka do dekodowania to ~ 20 instrukcji.
Nemo,
Jeśli sprzęt do przewidywania rozgałęzień błędnie przewiduje ścieżkę wykonania, zrzuty z niewłaściwej ścieżki, które znajdują się w potoku instrukcji, są po prostu usuwane tam, gdzie są, bez blokowania wykonania. Nie mam pojęcia, jak to możliwe (ani czy źle to interpretuję), ale najwyraźniejw Nehalemnie ma przeciągnięć rurociągów z niewłaściwie przewidywanymi odgałęzieniami? (Z drugiej strony nie mam i7; mam i5, więc nie dotyczy to mojego przypadku.)
user541686,
1

Ż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ć.

Jens Gustedt
źródło