Prekladača pod pokrievkou - optimalizácia

Už ste niekedy premýšľali, čo vlastne robí kompilátor? Čo sa deje potom, čo dokončíte svoj program a necháte ho preložiť?

Dnes sa krátko pozrieme do kuchyne kompilátorov vyšších programovacích jazykov a ich platforiem. Téma je to naozaj rozsiahle, takže sa len mrkneme na základy a niektoré zaujímavosti (a to značne zjednodušene), s ktorými sa môžete čas od času stretnúť.

Assembler - jazyk CPU

Srdcom počítača je centrálny procesor, CPU, ktorý prikazuje jednotlivým komponentom počítača, čo majú robiť. Procesor vykonáva inštrukcie zadané programátorom jednu po druhej a (skoro) vždy robí doslova to, čo sa mu povie. A jediný jazyk, ktorému procesor rozumie, je strojový kód, ktorý sa v čitateľnej forme pre programátorov nazýva assembler.

Assembler je veľmi prostý jazyk, ktorý toho vie len málo, takže jeho používanie je veľmi náročné. Krátka ukážka kódu (ktorý skoro nič nerobí) môže vyzerať takto:

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

Vyššia programovacie jazyky sa nazývajú "vyššia" práve z toho dôvodu, aby ste mali pohodlnejší život a nemuseli sa zaujímať o to, čo CPU vie alebo nevie. Nie je totiž CPU ako CPU a inštrukcie, ktorým jednotlivé varianty rozumie, sa môžu drasticky líšiť.

Program, ktorý napíšete vo svojom programovacom jazyku (či už je to C, Java alebo C #), bude nakoniec preložený až na úroveň strojového kódu, aby mohlo dôjsť k jeho spusteniu.

Kompilátor vyššieho jazyka

Celý proces, ktorý začína vaším zdrojovým kódom v C alebo Jave, a končí až na úrovni strojového kódu, je neuveriteľne komplexný. Prebieha v niekoľkých fázach, ktoré sa vzájomne prelínajú a kompilátory medzi sebou súťažia, kto z nich je rýchlejší a dôjde k lepšiemu výsledku. Jednotlivé fázy sú:

1. syntaktická analýza
2. sémantická analýza
3. Preklad do meta-jazyka
4. optimalizácia
5. Preklad do strojového kódu

Počas syntaktické analýzy prekladač číta váš text a zisťuje, či rozumie tomu, čo ste vytvorili - kontroluje sa syntax vety. Ak niečo nesedí, nahlási vám syntaktickú chybu. Takáto chyba môže byť napríklad:

float int x y;

Sémantická analýza sa naopak zaujíma o to, či váš program dáva zmysel. Medzi sémantickej chyby už patrí neznámy názov premennej alebo chýbajúce návratová hodnota.

Potom už je celý zdrojový kód preložený do meta-jazyka, čo je už kód, ktorý je skoro na úrovni strojového kódu, ale ešte nie úplne. Meta-jazyk alebo medzi-kód je nezávislý na aktuálnu verziu procesora a jeho inštrukcií a veľmi pekne sa s ním pracuje. Príkladom môže byť bytecode v Jave alebo CIL v C #.

V ďalšej fáze vykonáva prekladač optimalizácia, čo je možno najzaujímavejšie časť, ktorej sa budeme venovať už za chvíľku.

A vo finálnej fáze dôjde k prekladu inštrukcií z meta-jazyka priamo do strojového kódu vášho procesora a môže byť spustený.

Value-of-IQ (prekladač)> Value-of-IQ (programátor)

Ako som už uviedol, prekladač sa snaží vytvoriť čo najlepšie, najrýchlejšia, najkratšia a najkrajší kód, ktorý stále robí to, čo si zaumienil programátor. Fáza, kedy sa tomuto procesu naplno venuje, sa nazýva optimalizácia, a tá býva ohniskom súťaženie medzi prekladači.

Prečo to tak je? Pretože úplná optimalizácia kódu patrí medzi takzvané NP úlohy, čo je trieda algoritmov, ktoré nevieme efektívne riešiť. Prekladača si preto pomáhajú rôznymi algoritmami, triky i podvodíky a firmy vytvárajúce prekladača svoje tajomstvá starostlivo stráži. Poďme sa pozrieť na niekoľko trikov, ktoré spravidla vie každý prekladač. Pre ukážky budem používať jazyk C, ale verte mi, že ostatné jazyky nezostávajú pozadu as kódom si hrajú prakticky rovnako.

Optimalizácia v akcii

Pozrime sa na nasledujúce ukážku kódu. Najprv tak, ako ho napísal 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 teraz, ako ho vidí prekladač:

main() {
}

Tak moment! Kam to všetko zmizlo? Preč. Prekladač správne usúdil, že kód vlastne nič nerobí a dal ho preč. Poďme sa pozrieť, ako k tomu došlo.

Trik prvý - výpočet konštánt

int x = 1 / 3;

Kód po optimalizácii:

int x = 0;

Najprv prekladač hľadá v kóde konštanty - hodnoty, ktoré sa nemenia. A pretože sú nemenné, nie je nutné ich počítať za behu programu. Takže je spočíta sám a dosadí výsledné hodnoty. 1/3 v celých číslach je nula, a preto sa 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ý - funkcie bez funkcie

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

Kód po optimalizácii:

y = x + 1;

U každej funkcie prekladač zisťuje, ako je veľká a čo vlastne robí. Zavolanie funkcie totiž stojí procesorový čas a pamäť, takže v niektorých prípadoch môže dôjsť k tomu, že je telo funkcie priamo vložené na miesto jej zavolanie.

Trik tretí - zjednodušenie výrazov

(podminka == false)

Kód po optimalizácii:

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

Počas sémantickej analýzy prekladač usúdi, že vzájomné porovnávanie boolean je zbytočné, a preto nahradí podmienku zjednodušenou verziou. Zjednodušenú preto, že v prvom prípade sa jedná o zložitejšie inštrukciu než v prípade druhom.

Poznámka autora: Tento príklad uvádzam iba k študijným účelom. Nikdy, prosím, nepíšte "podmienka == false", hoci je zápis syntakticky správny, je to rovnaké, ako ručne si vyšívať na slipy svoje iniciály.

Trik štvrtý - opäť konštanty

bool podminka = true;
if (!podminka) …

Kód po optimalizácii:

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

V tejto časti si prekladač simuluje beh programu a zistí, že podmienka nemôže byť nikdy splnená. Z toho dôvodu odstráni časti kódu, ktoré nikdy neprebehnú.

Trik piaty - nepoužívané premenné

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

Kód po optimalizácii:

main() {
}

A sme vo finále. Premenná zaberá miesto v pamäti a ak premennú nepoužijete, nie je dôvod, aby tam bola. Čím kratšie, tým rýchlejšie, a preto prekladač odstráni aj túto časť programu.

Tak čo, prekladač je celkom šikovný, nie? Pre zaujímavosť si môžeme ukázať ešte niekoľko trikov.

Trik šiesty - rozloženie cyklu

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

Po optimalizácii:

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

Každý cyklus obsahuje podmienku a podmienka je v súčasnej dobe najbolestivejším miestom všetkých procesorov. Pretože je cyklus krátky, môže prekladač usúdiť, že takáto úprava bude výhodnejšie.

Trik siedmy - matematika

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

Po optimalizácii:

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

Ak sa v nejakej časti programu opakuje dokola stále rovnaký výraz, nie je nutné ho počítať viackrát. Prekladač zabezpečí, aby sa spočítal iba raz a získaná hodnota sa používala stále dokola. Naviac môže dôjsť k úprave známeho výrazu, aby bolo možné použiť optimálne inštrukcie.

Zložitejšie príklad na záver

Nakoniec vám ukážem príklad, v ktorom bude dochádzať k úplne nečakanému správania. Jedná sa o ukážku z praxe, ku ktorej dochádza v mnohých rôznych formách v prípade, že programátor nevie, čo naozaj dokáže urobiť optimalizácia.

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);
}

Teraz spustíme obe funkcie súčasne v dvoch vláknach a budeme sledovať, čo sa deje ...

Kvízová otázka - čo sa môže diať?

Jedna z mnohých správnych odpovedí - prvé vlákno, ktoré volá funkciu A, vypisuje čísla od 0 do 1000000 a potom skončí. Medzitým druhej vlákno vypisuje stále dokola 0 a nikdy neskončí.

Prečo sa to stane? A že to nedáva zmysel?

Práve naopak, prekladač sa totiž snaží čo najviac urýchliť beh programu a zistí, že cyklus vo funkcii A používa jedinú riadiacu premennú. Ak by v každom cykle zdvihol jej hodnotu, uložil ju do pamäte, opäť načítal a odovzdal ju ako parameter, bolo by to pomalé. Rýchlejšie variant je držať si premenou v pamäti priamo na jadre procesora, a až cyklus skončí, uloží sa posledná hodnota do pamäti.

Medzitým funkcie B iba testuje obsah premennej a ak v nej dôjde k rovnakej optimalizáciu, bude sa navždy kontrolovať prvý získaná hodnota a cyklus nemôže skončiť.

V jazyku C# sa táto situácia rieši kľúčovým slovom volatile a direktívou Thread.Memory­Barrier ().

Slovo na záver

Prekladača sú zložité programy a rad z nich vyvíja celé tímy ľudí, ktorí vo svojom obore patrí medzi absolútnu špičku. Nemajú to ľahké a odvádzajú skvelú prácu. Vďaka nim máme ľahší život a pokojnejší spánok. Až budete nabudúce písať svoju ďalšiu aplikáciu, spomeňte si na ne a vzdajte im hold!