Při čtení "Dračí knihy" (Dragon book) jsem narazil u jednoho příkladu ruční implementace konečného automatu na poznámku, že nezáleží na pořadí uvedených case větví v příkazu switch, protože překladač to optimalizuje, a tudíž, i když tu nejméně pravděpodobnou variantu dáme na začátek, tak to nebude mít na výkon žádný vliv. Co se týče nezávislosti na pořadí (mimo speciální případy, např. vynechaný break), tak v jazycích C a C++ je to běžně známá záležitost, ale mě zaujala ona poznámka o optimalizaci a nedalo mi to, abych se nepřesvědčil, jak tomu ve skutečnosti je. Se svými výsledky, co se týče překladače gcc, bych se chtěl podělit v tomto příspěvku.
Vytvořil jsem si několik testovacích programů, které jsem nechal následně přeložit, ale jako výstup jsem místo binárního souboru zvolil jazyk symbolických instrukcí, abych se mohl podívat, jaký cílový kód překladač vygeneroval. Uvedu kompletní zadání prvního příkladu a u každého dalšího už jen změny, aby příspěvek nebyl zbytečně natahovaný :). Výstupy překladače neuvádím (pouze slovní zhodnocení, jak to ve výsledku dopadlo). Překlad probíhal překladačem gcc (gcc -std=c99 -pedantic -W -Wall -S prog.c, pokud není uvedeno jinak) ve verzi 4.4.1 na systému Debian (x86_64). Výsledky jsou získané experimentováním s překladačem, nikoliv studiem jeho zdrojového kódu.
První příklad
Pro jedoduchost jsem zvolil následující program (nad tím, že by to šlo zapsat mnohem jednodušeji se nezamýšlejte - šlo mně jen o ukázku):
Vstup:
int main() { int a = 5; switch (a) { case 1: a += 1; break; case 2: a += 2; break; case 3: a += 3; break; case 4: a += 4; break; case 5: a += 5; break; default: a += 6; break; } return a; }
Výstup:
Zde bylo výsledkem to, co autoři zmiňované knihy o překladačích uváděli v poznámce - vygenerovaný kód v assembleru nejdříve porovnal hodnotu proměnné a s maximální hodnotou, která se vyskytuje v jednotlivých větvích case (v našem případě 5) a pokud je větší, tak skočil na návěští default, jinak použil hodnotu proměnné a jako index do tabulky skoků a skočil přímo na příslušnou větev. V případě, kdy některá větev chybí (např. vyřadím větev, která se vykonává při a == 3), tak se jako hodnota v tabulce skoků uvede návěští default. Jak ale ukazuje následující příklad, tato implementace má smysl pouze při nevelikých číslech, jinak by tabulka skoků byla příliš veliká.
Druhý příklad
Nyní zkusíme zvýšit hodnotu, která se vyskytuje v jedné z case větví (konkrétně třeba ve větvi těsně před náveštím default).
Vstup:
int main() { // ... case 1000: a += 4; break; // ... }
Výstup:
Zde již implementace tabulkou ztrácí smysl. Pokud byste ale čekali, že se provede řada porovnání podle pořadí zápisu case větví v kódu, pak jste na omylu, jelikož překladač optimalizuje, a to následovně. Nejdříve se provede porovnání s prostřední hodnotou (např. s hodnotou 3) a pokud se rovná hodnotě proměnné a, tak provede skok na příslušné návěští. Pokud je menší, tak porovnává s prostřední hodnotou, která je menší než 3. Pokud je naopak větší, pak porovnáná s prostřední hodnotou, která je větší než 3 atd. Určitě vám to něco připomíná - ano, je to vyhledávání binárním půlením :). To má za následek teoretické zrychlení prováděného kódu z O(n) (postupné sekvenční porovnávání) na O(log2(n)) (vyhledávání binárním půlením). Při takto malém množství porovnání se to nijak neprojeví, ale pokud by se to provádělo v cyklu a při velkém množství větví, pak by urychlení bylo znatelné. Podle manuálu k gcc je dále možné přiřadit jednotlivým větvím pravděpodobnosti jejich vykonání a optimalizovat podle toho, ale to jsem nezkoušel.
Třetí příklad
Poslední otestování optimalizátoru překladače gcc - proměnné a přiřadíme hodnotu, která by měla provést skok na větev default a zapneme pokročilé optimalizace (-O3).
Vstup:
int main() { int a = 50; // ... }
Výstup:
V tomto případě (zapnuté pokročilé optimalizace) překladač kompletně celý příkaz switch (včetně definice proměnné a) vyoptimalizoval a vygeneroval kód, v němž po zavolání funkce main() dojde k prostému vrácení hodnoty 56 :) (50 + zvýšená hodnota ve větvi default).
Závěr
Jak je vidět, tak takovéto běžné příkazy switch dokáže překladač poměrně dobře optimalizovat, takže je názorně vidět, že na pořadí zápisu jednotlivých větví příkazu switch opravdu nezáleží (pokud nevynecháte break, ale to je na jinou debatu) - standard nic takového nepožaduje, takže proč to při překladu nezoptimalizovat?