c tablice przełączników i skoków

Question

Rozumiem, że instrukcja switcha w języku c/C++ będzie czasami kompilować się do tabeli przeskoku. Moje pytanie brzmi, czy istnieją jakieś zasady dotyczące kciuka, aby to zapewnić?

W moim przypadku robię coś takiego:

enum myenum{ 
MY_CASE0= 0, 
MY_CASE0= 1, 
. 
. 
. 
}; 

switch(foo) 
{ 
    case MY_CASE0: 
    //do stuff 
    break; 
    case MY_CASE1: 
    //do stuff 
    break; 
. 
. 
. 
} 

ja obejmować wszystkie przypadki, od 1 do N przez kolejności. Czy można bezpiecznie założyć, że skompiluje się on do stołu skoku? Oryginalny kod był długim i niechlujnym stwierdzeniem if else, więc przynajmniej uzyskałem pewną czytelność.

Answer 1

Podejście to zależy wyłącznie od kompilatora.

Należy jednak pamiętać, że ze względu na twoje oświadczenia break nie odzwierciedlają one tabeli skoku czystego w asemblerze, więc postawiłbym na to. Ale to tylko zakład; Nie piszę kompilatorów C++.

Z testem switch, testujesz tylko jeden warunek (jakkolwiek skomplikowany), ale z if/else możesz przetestować kilka; chociaż możesz zoptymalizować, umieszczając najbardziej prawdopodobne przypadki jako pierwsze. To może być szybsze niż skomplikowane switch. To prawdopodobnie najważniejsze rozważania optymalizacyjne dla ciebie; Nie przejmowałbym się zbytnio wyborem kompilatora.

Answer 2

Dobry kompilator może i wybierze między tabelą skoku, połączonym łańcuchem/lub kombinacją. Źle zaprojektowany kompilator może nie dokonać takiego wyboru - i może nawet wygenerować bardzo zły kod dla bloków przełączających. Ale każdy przyzwoity kompilator powinien wytworzyć wydajny kod dla bloków przełączających. T

głównym czynnikiem decydującym o tym, że kompilator może wybrać, czy/else gdy liczby są daleko od siebie (i nie trywialnie (np. Dzieląc przez 2, 4, 8, 16, 256 itd.) Zmienione na bliżej wartości] np

switch(x) 
{ 
    case 1: 
    ... 
    case 4912: 
    ... 
    case 11211: 
    ... 
    case 19102: 
    ... 
} 

wymaga tabeli skoku co najmniej 19102 * 2 bajty.

Z drugiej strony, jeśli liczby są blisko siebie, kompilator będzie zazwyczaj używał opcji do pomylenia.

Nawet jeśli jest to if/else typ konstrukcji, to zazwyczaj zrobić „binarne przeszukiwanie” - jeśli weźmiemy powyższym przykładzie:

if (x <= 4912) 
{ 
    if (x == 1) 
    { 
     .... 
    } 
    else if (x == 4912) 
    { 
     .... 
    } 
} else { 
    if (x == 11211) 
    { 
     .... 
    } 
    else if (x == 19102) 
    { 
     ... 
    } 
} 

Jeśli mamy wiele przypadków, takie podejście będzie gniazdo dość głęboko , a ludzie prawdopodobnie zgubią się po trzech lub czterech poziomach głębokości (mając na uwadze, że każdy z nich zaczyna się w pewnym punkcie ŚREDNI zakresu), ale zmniejsza liczbę testów o log2 (n), gdzie n jest liczba opcji do wyboru. Jest to z pewnością dużo bardziej wydajny niż naiwnego podejścia

if (x == first value) ... 
else if (x == second value) ... 
else if (x == third value) ... 
.. 
else if (x == nth value) ... 
else ... 

ten może być nieco lepiej, jeśli niektóre wartości są umieszczane na początku łańcucha if-else, ale zakłada, można określić, co jest najczęstszą przed uruchomieniem kodu.

Jeśli wydajność jest KRYTYCZNA dla twojej sprawy, musisz porównać te dwie możliwości. Ale domyślam się, że samo napisanie kodu jako przełącznika sprawi, że kod stanie się bardziej przejrzysty, a jednocześnie będzie działał co najmniej tak szybko, jeśli nie szybciej.

Answer 3

Kompilatory mogą z pewnością przekonwertować dowolny przełącznik C/C++ na tabelę skoków, ale kompilator zrobi to dla zwiększenia wydajności. Zadaj sobie pytanie, co bym zrobił, gdybym pisał kompilator i właśnie zbudowałem drzewo analizy dla instrukcji switch/case? Uczyłam kompilatora projektowania i budowy, a oto niektóre z decyzji,

Jak pomóc kompilator decydują się na wdrożenie tabelę jump:

• wartości sprawy są małe liczby całkowite (0,1,2, 3, ...)
• wielkości skrzynek mieszczą się w zakresie kompaktowym (kilka otworów, domyślnie pamiętaj, pamiętaj o domyślnej opcji)
• jest wystarczająco dużo przypadków, aby optymalizacja była opłacalna (> N, sprawdź źródło kompilatora, aby znaleźć stałą wartość)
• sprytni kompilatorzy mogą odejmować/dodawać stałą do jumptabl indeks e jeśli zakres jest zwarty (przykład: 1000, 1001, 1002, 1003, 1004, 1005, etc.)
• uniknąć fallthrough i przekazanie sterowania (Goto, dalej)
• tylko jedna przerwa na końcu każdego przypadku

Chociaż mechanizmy mogą się różnić między kompilatorów, kompilator zasadniczo tworzenie funkcji anonimowych (dobrze, może nie funkcji, gdyż kompilator może wykorzystywać skok do bloku kodu i skok outof bloku kodu, albo może być doskonałym i użyj jsr i return)

W pewien sposób, aby uzyskać tabelę skoku, należy ją zapisać. Jest to tablica wskaźników do funkcji, indeksowana przez żądaną wartość.

Jak?

Zdefiniuj typedef dla wskaźnika funkcji, Understanding typedefs for function pointers in C,

typedef void (* FunkPtr) (double double A1 A2);

FunkPtr JumpTable[] = { 
    function_name_0, 
    function_name_1, 
    function_name_2, 
    ... 
    function_name_n 
}; 

Oczywiście, już zdefiniowane function_name_ {0..N}, więc kompilator może znaleźć adres funkcji do wywołania.

Zostawię wywołanie wskaźnika funkcji i sprawdzanie granic jako ćwiczenie dla czytelnika.