Předinstalovaný kompilátor GCC nabízí mnoho různých voleb. V dnešním příspěvku vysvětlím volby související s optimalizací a provedu jednoduchý test jejich účinnosti.

Teorie

Co lze obecně optimalizovat?:

• rychlost
• paměťovou náročnost
• velikost zkompilovaného (strojového) kódu
• další parametry (např. množství diskových operací)

Tyto optimalizace mohou být protichůdné. Například optimalizace rychlosti může směřovat k zvětšení zkompilovaného programu. GCC umožňuje zadat volby pro optimalizaci rychlosti (přepínače O0 až O3) a velikosti programu (přepínač Os).

Od optimalizace pochopitelně nelze očekávat, že odstraní důsledky špatného návrhu algoritmu, nebo jiné “zázraky”. Ostatně očividně problém dokonalé optimalizace kódu není ani algoritmicky řešitelný a ani algoritmus s nejlepší asymptotickou časovou (nebo paměťovou) složitostí nemusí vůbec existovat. Možná je výraznou překážkou při konstrukci kompilátoru i úroveň současného teoretického poznání, kdy nejsou známy odpovědi ani na základní otázky.

Volba úrovně optimalizace odpovídá spuštění celé série poměrně nezávislých jednoduchých optimalizací. Může jít například o optimalizaci skoků a větvení, vyčíslení známých výrazů, optimalizace aritmetických výrazů (např. místo a+a+a+a použít 4*a), vhodnou volbu obsahu registrů, rozepsání cyklů se známým nízkým počtem průchodů (např. f();f();f(); místo trojnásobného volání funkce ve for cyklu)…

Výsledkem je logicky ekvivalentní kód. Při použití více vláken, sdílené paměti, asynchronních událostech atd. však “nevinné” přehazování instrukcí může být nekorektní. Tato problematika je širší, protože obdobné optimalizace se provádí samovolně i při běhu programu na úrovni CPU.

Vlastní test

Neumím psát velké množství neoptimálního kódu Proto jsem s pomocí Eclipse (přehled jiných prostředí viz předminulý článek) napsal jednoduchý prográmek (zdrojový kód okolo sto řádků), který vygeneroval náhodný zdrojový kód v C o délce cca 15000 řádků obsahující různé aritmetické operace, for cykly a větvení if. Následuje ukázka kódu generátoru:

System.out.print(“pole[" + r.nextInt(pocet_prvku) + "]–;\n“);//dekrementace
}
if (nahodny == 5){//prirazeni
System.out.print(“pole[" +  r.nextInt(pocet_prvku) + "] = pole[" +  r.nextInt(pocet_prvku) + "];\n“);
}
if (nahodny == 6){//konstanta
System.out.print(“pole[" + r.nextInt(pocet_prvku) + "] = 10;\n“);
}
}
public static void for_cyklus1(){
System.out.print(“for (j” + zanoreni + “  = (pole[" + r.nextInt(pocet_prvku) + "] + “ +
“pole[" + r.nextInt(pocet_prvku) + "]) % 30 + 4″ +

A dále následuje ukázka malé části vygenerovaného C kódu:

for (j1  = (pole[1] + pole[9] + 5) % 30 + 4; j1 > 0; j1– ){
pole[5] %= 10;
pole[3] += 10;
if (pole[5] > pole[9]) pole[5] = pole[9];
}
pole[6] += 10;
pole[1] = pole[2];

Potřebné zdrojové kódy naleznete v přílohách blogu uložených na stránkách autora. Přílohy se schodují s přílohami k příspěvku Srovnání GCC a LLVM.

Výsledky testu

	doba kompilace[s]	velikost programu[kB]	délka běhu programu[s]
gcc -Os	23.250	95.8	8.718
gcc -O0	10.441	265.8	3.037
gcc -O1	20.622	135.8	1.725
gcc -O2	30.641	135.8	1.647
gcc -O3	38.624	135.6	1.566

Profiler

Tzv. profiler statisticky zpracovává různé poznatky získané při běhu profilovaného programu. Tato pomůcka zeefektivňuje plánování vývoje, protože víme na, která místa v kódu se soustředit. Dokonce profiler umožňuje bez teoretické přípravy správně vybrat mezi více algoritmy a může částečně eliminovat nutnost kompilace mnoha verzí a následných benchmarků.

Příklad : Náš program obsahuje řádek if (test_neoptimalnosti()) optimalizuj_datove_struktury();. Když profiler zjistí, že tato podmínka je téměř vždy splněna, bude možná lepší bez testování rovnou zavolat funkci optimalizuj_datove_struktury(). V případě, že není podmínka splněna téměř nikdy, bude možná lepší řádek úplně vypustit. atd.

GCC nemá při kompilaci podobnou statistiku. S poznatky z profileru by optimalizace mohla zohledňovat i např. pravděpodobnosti průchodu jednotlivými větvemi. (Poznámka : Nadstandardní rozšíření některých překladačů mohou umožnit programátorovi tyto poznatky vyjádřit. Může jít např. o vestavěné makro označující, že určitá podmínka bude téměř vždy splněna.)

Řešením je kompilace s direktivou -fprofile-generate. Spuštěním získaného programu se provede profilování a zápisu statistiky do zvláštních souborů. Při následné kompilaci s direktivou -fprofile-use jsou tyto údaje využity. V testovaném případě první kompilace trvala 45.546s a druhá 41.020s. Výsledený program (152.9kB) měl dobu běhu 1.357s, což je zlepšení o téměř 15% oproti pouhé kompilaci s volbou -O3.

Ilustrující příklad optimalizace : Mějme dva algoritmy realizující stejný výpočet:

d = a + b;
e = d + c;
if (e == 0) funkce(d);
else funkce(b + c);

a tentýž výpočet :

d = b+ c;
e = d + a;
if (e != 0) funkce(d);
else funkce(a + b);

Pokud je součet a+b+c téměř vždy nula, je vhodnější zvolit první algoritmus. Tím se téměř vždy ušetří zbytečné sčítání a+b. V opačném případě je lepší volit druhý algoritmus, který naopak šetří před zbytečným sčítáním b+c.

Upozornění : Běžné desktopové aplikace jsou zpomalovány diskovými operacemi apod., jejichž náročnost nesouvisí s optimalizacemi při kompilaci vlastní aplikace.

Štítky: Seriál : Za tajemstvím kompilace, Testy

Komentáře v diskuzi

Přidat komentář

Jméno

E-mail, nebude zveřejněn

Web

Ochrana proti spamu: (povinné)*
Opište prosím text z obrázku.