Czy "switch" jest szybszy niż "if"?

Na twoje pytanie:

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

Jump table to adres pamięci, który zawiera wskaźnik do etykiet w strukturze tablicy. poniższy przykład pomoże Ci zrozumieć, jak są ułożone 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ść d8 09 AB 00 reprezentuje wskaźnik etykiety.

2.Is ten kod za pomocą skoku stolik? W tym przypadku nie.

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, nie ma tabeli skoków.

4.Is czy jest jakaś sytuacja, w której istnieje znacząca różnica w wydajności?

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

Kod dla wszystkich instrukcji compare ma również pewien rozmiar, więc szczególnie w przypadku 32-bitowych wskaźników lub offsetów, wyszukiwanie pojedynczej tabeli skoków może nie kosztować dużo większego rozmiaru w pliku wykonywalnym.

Wniosek: kompilator jest na tyle inteligentny, że radzi sobie z takim przypadkiem i generuje odpowiednie instrukcje:)

Kompilator może swobodnie kompilować instrukcję switch jako kod, który jest odpowiednikiem instrukcji if, lub tworzyć tabelę skoków. Prawdopodobnie wybierze jeden na drugim na podstawie tego, co wykona najszybszy lub wygeneruje najmniejszy kod w zależności od tego, co podałeś w opcjach kompilatora - więc w najgorszym przypadku będzie to ta sama prędkość, jak gdyby-statements

Zaufałbym kompilatorowi, który zrobi najlepszy wybór i skupi się na tym, co sprawia, że kod jest najbardziej czytelny.

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

Skąd wiesz, że Twój komputer nie wykonywał zadania niezwiązanego 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 zbyt mało przypadków

Moje wyniki:

Dodałem:

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

Do końca, aby nie optymalizować pętli, ponieważ licznik nigdy użyte w twoim przykładzie więc dlaczego kompilator miałby wykonywać pętlę? Od razu przełącznik zawsze wygrywał nawet z takim mikro-benchmarkiem.

Inny problem z Twoim kodem to:

switch (counter % 4 + 1)

In your switch loop, versus

const size_t c = counter % 4 + 1; 

W pętli if. Bardzo duża różnica, jeśli to naprawisz. Wierzę, że umieszczenie instrukcji wewnątrz instrukcji switch prowokuje kompilator do wysyłania wartości bezpośrednio do rejestrów procesora, a nie umieszczania jej najpierw na stosie. To jest zatem zwolennikiem instrukcji switch, a nie testu zbalansowanego.

Mam zmodyfikował Kod Ryana na tyle, aby upewnić się, że kompilator nie może tego rozgryźć 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);
} 

Switch: 3740
if: 3980

(podobne wyniki przy wielu próbach)

Zmniejszyłem również liczbę spraw / ifs do 5, a funkcja przełącznika nadal wygrała.

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

1. prosta tabela skoków, jeśli przypadki są ułożone w ładnym długim przedziale
2. nieliczna (dwupoziomowa) tabela skoków, jeśli jest wiele luk
3. szereg ifs, jeśli liczba przypadków jest mała lub wartości są Nie blisko siebie
4. kombinacja powyższych przypadków, jeśli przypadki reprezentują kilka grup ściśle rozmieszczone zakresy.

W skrócie, jeśli przełącznik wygląda na wolniejszy niż szereg ifs, kompilator może po prostu przekonwertować go na jeden. I prawdopodobnie nie będzie to tylko sekwencja porównań dla każdego przypadku, ale binarne drzewo wyszukiwania. Zobacz tutaj dla przykładu.

Odpowiem 2) i przedstawię kilka ogólnych uwag. 2) Nie, Nie ma tabeli Skoku w kodzie montażu, który napisałeś. Tabela skoków to tabela miejsc skoków i jedna lub dwie instrukcje, aby przejść bezpośrednio do zindeksowanej lokalizacji z tabeli. Tabela skoku ma większy sens, gdy istnieje wiele możliwych miejsc przełączania. Może optymalizator wie, że proste, jeśli logika else jest szybsza, chyba że liczba miejsc jest większa niż jakiś próg. Spróbuj jeszcze raz swojego przykładu za pomocą say 20 możliwości zamiast 4.

Byłem zaintrygowany i przyjrzałem się, co mogę zmienić w twoim przykładzie, aby przyspieszyć uruchamianie instrukcji switch.

Jeśli osiągniesz 40 poleceń if i dodasz 0 case, to blok if będzie działał wolniej niż równoważna Instrukcja switch. Wyniki mam tutaj: https://www.ideone.com/KZeCz .

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

Oto wyniki starego (teraz trudnego do znalezienia) bench++ benchmark:

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 tej maszynie, z tym kompilatorem -- VC++ 9.0 x64), każdy if test trwa około 0,7 nanosekundy. Wraz ze wzrostem liczby testów czas skaluje się niemal idealnie liniowo.

Z instrukcją switch, nie ma prawie żadnej różnicy prędkości między testem 2-drożnym a 10-drożnym, o ile wartości są gęste. Test 10-drożny z rzadkim wartości zajmuje około 1,6 x tyle czasu, co test 10-drożny z gęstymi wartościami-ale nawet z rzadkimi wartościami, nadal lepiej niż dwa razy szybciej niż 10-drożny if/else if.

Reasumując: Korzystanie tylko z testu 4-way nie pokaże ci wiele {[16] } o wydajności switch vs if/else. Jeśli spojrzymy na liczby z tego kodu, dość łatwo jest interpolować fakt, że w przypadku testu 4-drożnego spodziewamy się, że te dwa wyniki będą podobne (~2,8 nanosekundy dla testu 4-drożnego). if/else, ~2.0 dla switch).

Zauważ, że gdy przełącznik nie jest skompilowany do tabeli skoków, bardzo często można napisać if ' S wydajniej niż przełącznik...

(1) jeśli przypadki mają kolejność, a nie najgorszy przypadek testowania dla wszystkich N, można napisać if ' S do testowania if w górnej lub dolnej połowie, a następnie w każdej połowie tego, Binarny Styl wyszukiwania... w wyniku czego w najgorszym przypadku logN zamiast N

(2) jeśli niektóre przypadki / grupy są znacznie częstsze niż inne przypadki, to projektowanie if ' S to odizoluj te przypadki najpierw może przyspieszyć średni czas przez

Nie są to if then jump else if then jump else...Tabela skoków ma tabelę adresów lub używa hasha lub czegoś takiego.

Szybszy czy wolniejszy jest subiektywny. Na przykład case 1 może być ostatnią rzeczą zamiast pierwszej i jeśli twój program testowy lub program w świecie rzeczywistym używał case 1 przez większość czasu, kod byłby wolniejszy z tą implementacją. Tak więc samo ponowne ułożenie listy spraw, w zależności od implementacji, może zrobić dużą różnicę.

Jeśli gdyby użyto przypadków 0-3 zamiast 1-4 kompilator mógłby użyć tabeli skoków, kompilator i tak powinien się zorientować, że usuwa twój +1. Być może była to niewielka liczba przedmiotów. Gdybyś zrobił to 0-15 lub 0 - 31 na przykład może zaimplementować go z tabelą lub użyć innego skrótu. Kompilator ma swobodę wyboru sposobu implementacji, o ile spełnia funkcje kodu źródłowego. I to dostaje się do różnic kompilatora i różnice wersji i optymalizacji różnice. Jeśli chcesz tabelę skoków, zrób tabelę skoków, jeśli chcesz drzewo if-then-else zrób drzewo if-then-else. Jeśli chcesz, aby kompilator zdecydował, użyj instrukcji switch/case.

Nie wiem, dlaczego jeden jest szybszy, a drugi wolniejszy.

W wersji % 20 pierwszy przypadek/if jest zawsze tym, który uderza. Nowoczesne procesory "uczą się", które gałęzie są zwykle brane, a które nie, dzięki czemu mogą łatwo przewidzieć, jak ta gałąź będzie się zachowywać na prawie każdej iteracji pętla. To wyjaśnia, dlaczego wersja" if " leci; nigdy nie musi wykonywać niczego poza pierwszym testem i (poprawnie) przewiduje wynik tego testu dla większości iteracji. Oczywiście" przełącznik " jest zaimplementowany nieco inaczej - być może nawet tabela skoków, która może być powolna dzięki obliczonej gałęzi.

W wersji % 21 gałęzie są zasadniczo losowe. Więc nie tylko wielu z nich wykonuje każdą iterację, ale procesor nie może odgadnąć, w którą stronę pójdą. To jest to przypadek, w którym tabela skoku (lub inna optymalizacja "przełącznika") może pomóc.

Bardzo trudno jest przewidzieć, jak kawałek kodu będzie działał z nowoczesnym kompilatorem i procesorem, a z każdą generacją jest to coraz trudniejsze. Najlepszą radą jest "nawet nie próbuj, zawsze profiluj". Ta rada staje się lepsza , a liczba ludzi, którzy mogą ją z powodzeniem ignorować, zmniejsza się z każdym rokiem.

Brak. W większości przypadków, gdy idziesz do asemblera i wykonujesz rzeczywiste pomiary wydajności, twoje pytanie jest po prostu złe. Dla podanego przykładu twoje myślenie jest zdecydowanie zbyt krótkie, ponieważ

counter += (4 - counter % 4);

Wygląda mi na poprawne wyrażenie przyrostowe, którego powinieneś używać.