Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Překladače pod pokličkou - optimalizace

Už jste někdy přemýšleli, co vlastně dělá kompilátor? Co se děje poté, co dokončíte svůj program a necháte ho přeložit?

Dnes se krátce podíváme do kuchyně kompilátorů vyšších programovacích jazyků a jejich platforem. Téma je to opravdu rozsáhlé, takže se jen mrkneme na základy a některé zajímavosti (a to značně zjednodušeně), se kterými se můžete čas od času setkat.

Assembler – jazyk CPU

Srdcem počítače je centrální procesor, CPU, který přikazuje jednotlivým komponentám počítače, co mají dělat. Procesor provádí instrukce zadané programátorem jednu po druhé a (skoro) vždy dělá doslova to, co se mu řekne. A jediný jazyk, kterému procesor rozumí, je strojový kód, který se v čitelné formě pro programátory nazývá assembler.

Assembler je velice prostý jazyk, který toho umí jen málo, takže jeho používání je velice náročné. Krátká ukázka kódu (který skoro nic nedělá) může vypadat takhle:

neg     al
and     eax,1
or      eax,2
cmp     eax,3
jge     .changed

Vyšší programovací jazyky se nazývají „vyšší“ právě z toho důvodu, abyste měli pohodlnější život a nemuseli se zajímat o to, co CPU umí nebo neumí. Není totiž CPU jako CPU a instrukce, kterým jednotlivé varianty rozumí, se mohou drasticky lišit.

Program, který napíšete ve svém programovacím jazyku (ať už je to C, Java nebo C#), bude nakonec přeložen až na úroveň strojového kódu, aby mohlo dojít k jeho spuštění.

Kompilátor vyššího jazyka

Celý proces, který začíná vaším zdrojovým kódem v C nebo Javě, a končí až na úrovni strojového kódu, je neuvěřitelně komplexní. Probíhá v několika fázích, které se vzájemně prolínají a kompilátory mezi sebou soutěží, kdo z nich je rychlejší a dojde k lepšímu výsledku. Jednotlivé fáze jsou:

  1. Syntaktická analýza
  2. Sémantická analýza
  3. Překlad do meta-jazyka
  4. Optimalizace
  5. Překlad do strojového kódu

Během syntaktické analýzy překladač čte váš text a zjišťuje, jestli rozumí tomu, co jste vytvořili – kontroluje se syntaxe věty. Pokud něco nesedí, nahlásí vám syntaktickou chybu. Taková chyba může být například:

float int x y;

Sémantická analýza se naopak zajímá o to, jestli váš program dává smysl. Mezi sémantické chyby už patří neznámý název proměnné nebo chybějící návratová hodnota.

Poté už je celý zdrojový kód přeložen do meta-jazyka, což je už kód, který je skoro na úrovni strojového kódu, ale ještě ne úplně. Meta-jazyk nebo mezi-kód je nezávislý na aktuální verzi procesoru a jeho instrukcí a velice hezky se s ním pracuje. Příkladem může být Bytecode v Javě nebo CIL v C#.

V další fázi provádí překladač optimalizace, což je možná nejzajímavější část, které se budeme věnovat už za chvilinku.

A ve finální fázi dojde k překladu instrukcí z meta-jazyka přímo do strojového kódu vašeho procesoru a může být spuštěn.

Value-of-IQ(překladač) > Value-of-IQ(programátor)

Jak už jsem uvedl, překladač se snaží vytvořit co nejlepší, nejrychlejší, nejkratší a nejhezčí kód, který stále dělá to, co si umanul programátor. Fáze, kdy se tomuto procesu naplno věnuje, se nazývá optimalizace, a ta bývá ohniskem soutěžení mezi překladači.

Proč tomu tak je? Protože úplná optimalizace kódu patří mezi takzvané NP úlohy, což je třída algoritmů, které neumíme efektivně řešit. Překladače si proto pomáhají různými algoritmy, triky i podvůdky a firmy vytvářející překladače svá tajemství pečlivě střeží. Pojďme se podívat na několik triků, které zpravidla umí každý překladač. Pro ukázky budu používat jazyk C, ale věřte mi, že ostatní jazyky nezůstávají pozadu a s kódem si hrají prakticky stejně.

Optimalizace v akci

Podívejme se na následující ukázku kódu. Nejprve tak, jak ho napsal programátor.

int increment(int i) {
  return i + 1;
}

main() {
  bool podminka = true;
  int x = 1 / 3, y;
  if (podminka == false)
    y = increment(x);
}

A teď, jak ho vidí překladač:

main() {
}

Tak moment! Kam to všechno zmizelo? Pryč. Překladač správně usoudil, že kód vlastně nic nedělá a dal ho pryč. Pojďme se podívat, jak k tomu došlo.

Trik první – výpočet konstant

int x = 1 / 3;

Kód po optimalizaci:

int x = 0;

Nejprve překladač hledá v kódu konstanty – hodnoty, které se nemění. A protože jsou neměnné, není nutné je počítat za běhu programu. Takže je spočítá sám a dosadí výsledné hodnoty. 1 / 3 v celých číslech je nula, a proto se kód upraví na:

int increment(int i) {
  return i + 1;
}

main() {
  bool podminka = true;
  int x = 0, y;
  if (podminka == false)
    y = increment(x);
}

Trik druhý – funkce bez funkce

int increment(int i) {
  return i + 1;
}
y = increment(x)

Kód po optimalizaci:

y = x + 1;

U každé funkce překladač zjišťuje, jak je velká a co vlastně dělá. Zavolání funkce totiž stojí procesorový čas a paměť, takže v některých případech může dojít k tomu, že je tělo funkce přímo vloženo na místo jejího zavolání.

Trik třetí – zjednodušení výrazů

(podminka == false)

Kód po optimalizaci:

main() {
  bool podminka = true;
  int x = 0, y;
  if (!podminka)
    y = x + 1;
}

Během sémantické analýzy překladač usoudí, že vzájemné porovnání typu boolean je zbytečné, a proto nahradí podmínku zjednodušenou verzí. Zjednodušenou proto, že v prvním případě se jedná o složitější instrukci než v případě druhém.

Poznámka autora: Tento příklad uvádím pouze ke studijním účelům. Nikdy, prosím, nepište “podmínka == false“, ačkoliv je zápis syntakticky správný, je to stejné, jako ručně si vyšívat na slipy svoje iniciály.

Trik čtvrtý – opět konstanty

bool podminka = true;
if (!podminka) …

Kód po optimalizaci:

main() {
  bool podminka = true;
  int x = 0, y;
}

V této části si překladač simuluje běh programu a zjistí, že podmínka nemůže být nikdy splněna. Z toho důvodu odstraní části kódu, které nikdy neproběhnou.

Trik pátý – nepoužívané proměnné

main() {
  bool podminka = true;
  int x = 0, y;
}

Kód po optimalizaci:

main() {
}

A jsme ve finále. Proměnná zabírá místo v paměti a pokud proměnnou nepoužijete, není důvod, aby tam byla. Čím kratší, tím rychlejší, a proto překladač odstraní i tuto část programu.

Tak co, překladač je docela chytrý, ne? Pro zajímavost si můžeme ukázat ještě několik triků.

Trik šestý – rozložení cyklu

for (int i = 0; i < 3; i++)
  printf(“%d”, i);

Po optimalizaci:

const char *tmp = “%d“;
printf(tmp, 0);
printf(tmp, 1);
printf(tmp, 2);

Každý cyklus obsahuje podmínku a podmínka je v současné době nejbolestivějším místem všech procesorů. Protože je cyklus krátký, může překladač usoudit, že taková úprava bude výhodnější.

Trik sedmý – matematika

int a, b;
int c = (a + b) * (a + b) - (a - b) * (a - b);

Po optimalizaci:

int a, b;
int t1 = a + b, t2 = a - b, t3 = t1 + t2, t4 = t1 - t2;
int c = t3 * t4;

Pokud se v nějaké části programu opakuje dokola stále stejný výraz, není nutné ho počítat vícekrát. Překladač zajistí, aby se spočítal pouze jednou a získaná hodnota se používala stále dokola. Navíc může dojít k úpravě známého výrazu, aby bylo možné použít optimální instrukce.

Složitější příklad na závěr

Nakonec vám ukážu příklad, ve kterém bude docházet ke zcela nečekanému chování. Jedná se o ukázku z praxe, ke které dochází v mnoha různých formách v případě, že programátor neví, co doopravdy dokáže udělat optimalizace.

Na pomoc si tentokrát vezmeme vlákna:

int i = 0;

void funkce_A() {
  while (i++ < 1000000) printf(“%d”, i);
}

void funkce_B() {
  while (i < 1000000) printf(“%d” , i);
}

Nyní spustíme obě funkce současně ve dvou vláknech a budeme sledovat, co se děje…

Kvízová otázka – co se může dít?

Jedna z mnoha správných odpovědí – první vlákno, které volá funkci A, vypisuje čísla od 0 do 1000000 a poté skončí. Mezitím druhé vlákno vypisuje stále dokola 0 a nikdy neskončí.

Proč se to stane? A že to nedává smysl?

Právě naopak, překladač se totiž snaží co nejvíce urychlit běh programu a zjistí, že cyklus ve funkci A používá jedinou řídící proměnnou. Pokud by v každém cyklu zvedl její hodnotu, uložil ji do paměti, opět načetl a předal ji jako parametr, bylo by to pomalé. Rychlejší varianta je držet si proměnou v paměti přímo na jádře procesoru, a až cyklus skončí, uloží se poslední hodnota do paměti.

Mezitím funkce B pouze testuje obsah proměnné a pokud v ní dojde ke stejné optimalizaci, bude se navždy kontrolovat první získaná hodnota a cyklus nemůže skončit.

V jazyce C# se tato situace řeší klíčovým slovem volatile a direktivou Thread.Memory­Barrier().

Slovo na závěr

Překladače jsou složité programy a řadu z nich vyvíjí celé týmy lidí, kteří ve svém oboru patří mezi absolutní špičku. Nemají to lehké a odvádějí skvělou práci. Díky nim máme snadnější život a klidnější spánek. Až budete příště psát svoji další aplikaci, vzpomeňte si na ně a vzdejte jim hold!


 

Všechny články v sekci
Články nejen o programování
Článek pro vás napsal coells
Avatar
Uživatelské hodnocení:
41 hlasů
Aktivity