Překladače pod pokličkou - optimalizace

Ostatní 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!


 

  Aktivity (1)

Článek pro vás napsal coells
Avatar

Jak se ti líbí článek?
Celkem (37 hlasů) :
4.945954.945954.945954.945954.94595


 



 

 

Komentáře

Avatar
tastyfish
Redaktor
Avatar
tastyfish:

Jenom jsem to tak proletěl, ale zdá se mi to jako dost dobrý článek od autora, který ví, o čem mluví :)

Odpovědět  +2 22.11.2013 23:09
škoda mluvit
Avatar
ondrejkuhejda:

Dobré! To že se kód tak rapidně změní jsem nečekal... :D

 
Odpovědět  +2 23.11.2013 9:37
Avatar
Kit
Redaktor
Avatar
Kit:

Je to dobrý článek, jen ty příklady jsou nějak přeházené. Je z toho vidět, že není problém definovat konstantu jako výraz z konstant. Že je zbytečné a často i kontraproduktivní se o některé optimalizace vůbec snažit. Velký význam však má výběr vhodného algoritmu či návrhového vzoru.

Odpovědět  +1 23.11.2013 9:50
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
coells
Redaktor
Avatar
Odpovídá na ondrejkuhejda
coells:

Kód se často mění ještě víc, než by kdokoliv čekal. :-)

V rámci jedné soutěže v C++ jsem potřeboval co nejvyšší rychlost zpracování, protože vstupy i výstupy byly obrovské. Takže jsem musel dřít C++ i počítač na kost.

Během performance analýzy se děla podivná věc. Ve chvíli, kdy jsem dal jednu podmínku pryč, běžel program neuvěřitelně rychle. Vůbec to nedávalo smysl, dokud jsem nezjistil, že se v tu chvíli změnily okolnosti a kompilátor provedl kaskádově řadu optimalizací ... a odstranil mi větší část kódu, protože ji nepovažoval za potřebnou. ;-)

 
Odpovědět  +1 23.11.2013 12:45
Avatar
Kit
Redaktor
Avatar
Odpovídá na coells
Kit:

Vím, že kompilátor při optimalizaci často přemisťuje invarianty cyklu mimo cyklus, podmínku u while přemisťuje na konec cyklu a settery v jedné třídě expanduje do metod ve volajících třídách. Snažit se ručně optimalizovat tyto části kódu je zpravidla zbytečné.

Odpovědět 23.11.2013 13:40
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na coells
Zdeněk Pavlátka:

Úžasný a poučný článek. :O O optimalizacích jsem věděl jen to, že v C++ fungují všechny objektové metody jako inline. ;)

Odpovědět  +1 23.11.2013 15:19
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
1Pupik1989
Člen
Avatar
1Pupik1989:

Celkem užitečný článek. Věděl jsem, že překladače osekají nepoužívané proměnné, ale že jdou až do takových detailů, jsem nevěděl.

Kdyby chtěl někdo psát seriál o překladačích, byl bych rád a vděčný. Sice s tím teď blbnu, ale nejsem schopen o tom napsat článek.

 
Odpovědět  +1 18.10.2014 11:07
Avatar
1Pupik1989
Člen
Avatar
1Pupik1989:

Možná by nebylo na škodu se ještě zmínit o lexikální analýze, která se provádí jako první. Stačila by jen zmínka na řádek.

 
Odpovědět 19.12.2014 11:11
Avatar
coells
Redaktor
Avatar
Odpovídá na 1Pupik1989
coells:

Formální model analýzy se takhle sice vyučuje, ale v řadě moderních jazyků je lexikální zpracování už součástí syntaktické analýzy, např. i ++ j může mít více významů a to neberu v úvahu jazyky, kde můžeš definovat své vlastní operátory.

 
Odpovědět  +1 19.12.2014 11:46
Avatar
1Pupik1989
Člen
Avatar
Odpovídá na coells
1Pupik1989:

Já vím, že lexikální analýza je součástí syntaktické, ale ostatní to vědět nemusí. Proto jsem psal, že stačí jen zmínka na řádek. Já je mám třeba oddělené. Řekl bych, že to ničemu nevadí. V lexikální analýze žádné významy nejsou. Ta čte jen vstup a udělá z něj lexémy, víc jí nezajímá.

 
Odpovědět 19.12.2014 13:48
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 10.