Fungování hardwaru je jedna velká magie.

Tuto optimalizaci nejčastěji provádíme tím, že optimalizujeme zdrojový kód. Příkazy a možnosti překladače uvedené v této sekci fungují například překladači gcc.

Často bereme počítač jen jako černou skříňku, která dobře počítá, a nezajímáme se o to, jak funguje vevnitř. Pokud ale chceme psát optimální kód, tak se neobejdeme bez hlubších znalosti chování hardwaru a fungování operačního systému. Jinak se nám může stát, že budeme naší černé skříňce házet klacky pod nohy a ona bude muset uvnitř pracovat tím nejsložitějším a taky nejpomalejším způsobem.

Nejprve bychom si měli rozmyslet, jestli je optimalizace kódu dané části programu opravdu nutná. Optimalizace totiž často svádí programátory k takzvaným “prasárnám”, které dokonale znečitelňují zdrojový kód. Nečitelný kód může pěkně potrápit další čtenáře, nebo po pár týdnech i nás samotné. Navíc se zvyšuje riziko, že někde uděláme chybu.

Optimalizace zdrojového kódu má smysl, pokud je daný kus kódu “úzkým hrdlem (bottle neckem)” celého programu a pokud zvládneme kód optimalizovat lépe než překladač.1 Přiznejme si, že dnešní překladače jsou na optimalizace profíci. Je těžké být lepší. Optimalizace kódu se většinou píší přímo v Assembleru. Často dosahují zrychlení tím, že využijí i specializované instrukce procesoru/grafického procesoru, které se běžně nepoužívají (případně počítají paralelně — buď na nezávislých obvodech téhož procesoru a nebo klidně i na více procesorech, CPU, GPU — graphical processing unit,$\dots$ ).

Jak to funguje uvnitř počítače?

Jak to zhruba funguje uvnitř černé skříňky? Procesor funguje na určité frekvenci. Frekvence procesoru je počet taktů za vteřinu. Každý procesor má svoji instrukční sadu. To jsou příkazy (instrukce), které jsou “zadrátované” do elektrických obvodů. Každá instrukce trvá jiný počet taktů. Některé instrukce trvají jeden takt, jiné třeba až $150$ taktů. Aby to nebylo jednoduché, tak má každý typ procesoru jinou instrukční sadu. Některé instrukce mohou být společné pro více typů procesorů, ale pro změnu mohou trvat jiný počet taktů (a to i výrazně).

Procesor potřebuje komunikovat s pamětí. Rychlá paměť je drahá a proto je paměť rozdělena do hierarchie podle klesající rychlosti, ale rostoucí velikosti: registry procesoru, cache procesoru, rozšířená paměť,2 paměť na pevném disku. První dvě paměti jsou pro běžného programátora skryté, ale jsou výrazně rychlejší než rozšířená paměť.3 Rozšířená paměť je zase výrazně rychlejší než pevný disk.

Procesor pracuje pouze s registry a s cache. Pokud potřebuje proměnnou z rozšířené paměti, tak si ji nejprve nechá nahrát do cache (v cache se vytvoří kopie) a tam s ní pracuje (s rychlejším přístupem). Často se stane, že s proměnnou pracuje více než jednou. Procesor pracuje pouze s lokální kopií v cache. Hodnota odpovídající proměnné v rozšířené paměti se zatím neaktualizuje. Aktualizace rozšířené paměti proběhne až v momentě, kdy chceme její lokální kopii v cache zrušit a uvolnit.

Cache často funguje na principu LRU (Least Recently Used). To znamená, že pokud už je cache plná a další proměnná se do ní nevejde, tak poslední dobou nejméně používaná proměnná uvolní místo nově příchozí proměnné. Při vymazání proměnné z cache se přepíše její aktuální hodnota zpátky do externí paměti.4 5

Překladač sám provádí určité optimalizace kódu. Ovšem nic není dokonalé. Překladač se snaží pochopit strukturu kódu a když najde něco, co umí vylepšit, tak to vylepší. Stále se ale vyplatí optimalizovat si časově náročné části sám. Přeci jen toho o fungování algoritmu víme více než překladač, který to musí rozpoznat či odhadnout ze zdrojového kódu. Na druhou stranu použitím vlastních optimalizací můžeme zablokovat optimalizace, které mohl provést překladač (zneprůhlednili jsme mu tím kód) a ve výsledku můžeme dostat pomalejší kód.

To je vše, co si k fungování černé skřínky řekneme. Bližší zájemce odkazuji na literaturu o operačních systémech, hardwaru a překladačích.

Jestli ale nevíte, jak to na vašem počítači s vaším překladačem vašeho oblíbeného programovacího jazyka opravdu funguje, tak si s tím hrajte. Experimentujte. Napište si vlastní prográmek, ve kterém si změříte, jak dlouho které příkazy trvají. (Dobrý programátor by měl vědět, jak dlouho trvá sčítání oproti násobení. Jak pomalé je čtení z disku, apod.)

Zásady pro psaní efektivního kódu

Ačkoliv je situace složitá, je pár zásad, kterých se můžeme držet, abychom psali efektivní kód. V následujícím textu používáme slovo “drahý” ve významu časově náročný.

  • Přístup do paměti je drahý. Měli bychom se snažit vejít do cache. Případně bychom měli nejprve dokončit práci s proměnnými, které už jsou v cache, a pak se teprve vrhnout na nová data. Například pokud pracujeme s hodně dlouhým polem, tak je rychlejší dělat více práce na malých kusech, než vícekrát procházet celé pole.Varování: V předchozích doporučeních jsme uváděli slova jako velký, malý apod. Ta správná velikost není univerzální, ale je na každém počítači jiná. Proto je nejlepší experimentovat s různými hodnotami parametrů a vybrat tu optimální. Další připomínkou je, že některá zlepšení se vyplatí až na hodně velkých datech.

    Pokud potřebujeme vynulovat či překopírovat velký kus paměti, tak je lepší použít funkce k tomu určené (memset, memcopy).

    Pokud se vše nevejde do cache, tak může být rychlejší, když si jednoduché věci dopočítáme znova, než když je hledáme v rozšířené paměti.

  • Zapisování a čtení ze souboru je drahé. Připomeňme, že vypisování na obrazovku se chová stejně jako zápis do souboru a tudíž, je také celkem drahé. Hodně pomůže zavedení bufferů. Potom stačí zapisovat do souboru méně krát a po větších kusech. To vede k výraznému zrychlení. Také můžeme využít možnosti, namapovat si kus souboru do paměti, a s ním teprve pracovat.
  • Podmínky jsou drahé. Aby procesor fungoval rychleji, tak si některé věci předpočítává. Například ví, že o pár instrukcí dál bude potřebovat určitou proměnnou, tak si ji už dopředu začne nahrávat do cache.6 Pokud je ale následující nezpracovaná instrukce podmínka (větvení programu), tak se dopředu neví, jak dopadne a tudíž nevíme, co si předpočítat. Procesor se často připravuje na obě varianty a po vyhodnocení podmínky nepotřebnou variantu zahodí. Tím promarní část svého času.Příklad: Máme proměnnou $a$ obsahující buď $0$ nebo $1$. Pokud potřebujeme změnit její hodnotu na opačnou, tak se dá podmínka s kódem nalevo přepsat na kód napravo.7
    if  $a=1$ then $a:=0$
    else $a:=1$
     $a:=1-a$
  • Registry procesoru jsou dnes $64$-bitové, proto je lepší zpracovávat data po $64$ bitech a ne po menších dílech. Toho se dá využít například při zpracovávání řetězců, obrázků a dalších médií.Z podobných důvodů se paměť zarovnává na $64$ bitů. To znamená, že první bit proměnné začíná na bitu v paměti, který je dělitelný $64$. Pro jednoduchost si můžeme představit, že paměť funguje jako pole $64$-bitových položek. Pokud bychom chtěli přistoupit k nezarovnané $64$-bitové proměnné, tak budeme muset přečíst dvě políčka pole a z nich si vytáhnout potřebné bity.
  • Některé aritmetické operace jsou drahé. Například dělení. Dělení mocninou dvojky, se dá obejít bitovým posunem doprava (bitová operace shift doprava). Dělení známou konstantou už ale stejným způsobem optimalizuje překladač. Problém nastává, když dělíme dopředu neznámou proměnou. To se při kompilaci programu optimalizovat nedá.Celkově je dobré se dělení vyhnout. Například místo výpočtu hashovací funkce modulo prvočíslo, kde se prvočíslo spočítá až za běhu programu a uloží do proměnné, si můžeme dopředu zjistit všechna prvočísla, které budeme používat. Při výpočtu hashovací funkce použijeme switch, kterým se podle prvočísla rozskočíme na optimalizovanou rutinu modulení (modulo konstanta — optimalizace při dělení konstantou už provede překladač).
  • K zajímavým trikům patří použití zarážky. Například když procházíme pole velikosti $N$ a hledáme hodnotu $x$, tak běžně v podmínce cyklu kontrolujeme dvě věci: jestli index aktuálního políčka nepřekročil $N$ a jestli není hodnota aktuálního políčka rovná $x$. Hledání můžeme zrychlit tím, že si do pole na pozici $N+1$ uložíme $x$, které bude fungovat jako zarážka. Potom máme jistotu, že $x$ vždy najdeme, a můžeme podmínku v cyklu zjednodušit na test, jestli není hodnota aktuálního políčka rovná $x$. Až $x$ najdeme, tak se podíváme, na kterém indexu leží. Podle toho zjistíme, jestli jsme $x$ našli a nebo jen neúspěšně došli až na konec pole.
  • Mezi další triky patří použití inline funkcí, nahrazení jednoduchých funkcí makrem (např. pro výpočet minima, maxima, absolutní hodnoty apod.)