Dlaczego przełącznik nie jest zoptymalizowany w taki sam sposób, jak łańcuchowy, jeśli indziej w c / c ++?

Poniższa implementacja kwadratu tworzy serię instrukcji cmp / je, których oczekiwałbym po łańcuchowej instrukcji if:

int square(int num) {
    if (num == 0){
        return 0;
    } else if (num == 1){
        return 1;
    } else if (num == 2){
        return 4;
    } else if (num == 3){
        return 9;
    } else if (num == 4){
        return 16;
    } else if (num == 5){
        return 25;
    } else if (num == 6){
        return 36;
    } else if (num == 7){
        return 49;
    } else {
        return num * num;
    }
}

A poniższe tworzy tabelę danych do zwrotu:

int square_2(int num) {
    switch (num){
        case 0: return 0;
        case 1: return 1;
        case 2: return 4;
        case 3: return 9;
        case 4: return 16;
        case 5: return 25;
        case 6: return 36;
        case 7: return 49;
        default: return num * num;
    }
}

Dlaczego gcc nie jest w stanie zoptymalizować górnej do dolnej?

Demontaż w celach informacyjnych: https://godbolt.org/z/UP_igi

EDYCJA: co ciekawe, MSVC generuje tabelę skoków zamiast tabeli danych dla skrzynki przełączników. I, co zaskakujące, clang optymalizuje je do tego samego rezultatu.

Wygenerowany kod switch-casekonwencjonalnie używa tabeli skoków. W tym przypadku bezpośredni zwrot przez tabelę przeglądową wydaje się być optymalizacją wykorzystującą fakt, że każdy przypadek wymaga zwrotu. Chociaż standard nie daje żadnych gwarancji na ten efekt, byłbym zaskoczony, gdyby kompilator wygenerował szereg porównań zamiast tabeli skoków dla konwencjonalnej skrzynki przełączników.

Teraz if-elsedochodzi do czegoś dokładnie odwrotnego. Podczas switch-casewykonywania w stałym czasie, niezależnie od liczby gałęzi, if-elsejest zoptymalizowany dla mniejszej liczby gałęzi. Tutaj można oczekiwać, że kompilator generuje serię porównań w kolejności, w jakiej je napisałeś.

Więc gdybym użył if-elsebo spodziewam Większość połączeń do square()być za 0lub 1rzadko dla innych wartości, a następnie „optymalizacja” to stołowych odnośnika może faktycznie przyczyną mojego kodu uruchomić wolniej niż się spodziewać, pokonując swój cel dla stosując ifzamiast tematyce switch. Chociaż jest to dyskusyjne, uważam, że GCC postępuje właściwie, a optymalizacja jest zbyt agresywna.

W komentarzach ktoś udostępnił link, w którym clang dokonuje tej optymalizacji i generuje if-elserównież kod oparty na tabeli odnośników . Coś godnego uwagi dzieje się, gdy zmniejszamy liczbę przypadków do zaledwie dwóch (i domyślnych) za pomocą clang. Ponownie generuje identyczny kod zarówno dla if, jak i switch, ale tym razem przełącza się na porównania i przesuwa się zamiast podejścia do tabeli przeglądowej dla obu. Oznacza to, że nawet clang faworyzujący przełączanie wie, że wzorzec „if” jest bardziej optymalny, gdy liczba przypadków jest niewielka!

Podsumowując, sekwencja porównań if-elsei tabela skoków dla switch-caseto standardowy wzorzec, który kompilatorzy zwykle podążają, a programiści zwykle oczekują, kiedy piszą kod. Jednak w niektórych szczególnych przypadkach niektóre kompilatory mogą zdecydować się na przełamanie tego wzorca, jeśli uważają, że zapewnia to lepszą optymalizację. Inne kompilatory mogą po prostu trzymać się tego schematu, nawet jeśli pozornie nie są optymalne, ufając twórcy, że wie, czego chce. Oba są ważnymi podejściami z ich własnymi zaletami i wadami.

Jednym z możliwych uzasadnień jest to, że jeśli niskie wartości numsą bardziej prawdopodobne, na przykład zawsze 0, wygenerowany kod dla pierwszego może być szybszy. Wygenerowany kod dla przełącznika zajmuje jednakowy czas dla wszystkich wartości.

Porównywanie najlepszych przypadków, zgodnie z tą tabelą . Zobacz tę odpowiedź, aby uzyskać wyjaśnienie tabeli.

Jeśli num == 0dla „if” masz xor, test, je (ze skokiem), ret. Opóźnienie: 1 + 1 + skok. Jednak xor i test są niezależne, więc rzeczywista prędkość wykonania byłaby większa niż 1 + 1 cykli.

Jeśli num < 7dla „przełącznika” masz mov, cmp, ja (bez skoku), mov, ret. Opóźnienie: 2 + 1 + brak skoku + 2.

Instrukcja skoku, która nie powoduje skoku, jest szybsza niż instrukcja skoku. Jednak tabela nie określa opóźnienia skoku, więc nie jest dla mnie jasne, który z nich jest lepszy. Możliwe, że ostatni jest zawsze lepszy, a GCC po prostu nie jest w stanie go zoptymalizować.