Optimalizace (informatika)

Optimalizace je v informatice takový proces modifikace výpočetního systému, který vede k jeho vyšší efektivitě nebo ke snížení nároků celého výpočetního systému. Výpočetním systémem může být počítačový program, počítač, celá počítačová síť, komplexní řešení určitého problému a podobně.

Například program může být optimalizován tak, aby pracoval rychleji, potřeboval pro provedení výpočtu méně operační paměti, méně systémových prostředků, případně se rychleji spustil a podobně.

U optimalizace záleží na rychlosti provádění kódu, na velikosti výsledného kódu a na paměťové náročnosti.

Úrovně optimalizace

Dříve byla optimalizace prováděna hlavně člověkem, dnes je prováděna již strojově. Optimalizace mohou probíhat na různých úrovních:

Úroveň návrhu (designu) programu

Na nejvyšší úrovni, návrh může být optimalizován tak, aby co nejlépe využíval dostupné zdroje. Implementace tohoto návrhu bude těžit z dobrého výběru efektivních algoritmů a implementace těchto algoritmů bude profitovat z dobře napsaného kódu. Architektonický návrh systému má převážně vliv na jeho výkon. Volba algoritmu ovlivňuje účinnost více než jakékoli jiné položky návrhu. Výběr algoritmu je obvykle první věc, která musí být rozhodnuta. V některých případech však optimalizace spoléhá na použití složitějších algoritmů, využití „zvláštních případů“ a speciálních “triků“ a realizaci složitých kompromisů. „Plně optimalizován“ program může být obtížné pochopitelný a proto může obsahovat více softwarových chyb, než neoptimalizovaná verze.

Úroveň zdrojového kódu

Vyhnout se nekvalitnímu kódování může také zlepšit výkonnost tím, že zamezíme se zjevnému „zpomalení“. Některé optimalizace v současné době provádí optimalizace kompilátoru. Použití systému optimalizace kompilátoru má tendenci, aby spustitelný program byl optimalizován přinejmenším stejně tolik, jako kompilátor.

Úroveň sestavování kódu

Na nejnižší úrovni psaní kódu pomocí jazyka symbolických adres, určeného zejména pro hardware, může programátor vyrobit co nejúčinnější a kompaktní kód, pokud využívá plného repertoáru strojových instrukcí. Mnoho operačních systémů se používá na vestavěné systémy, které byly tradičně napsány v assembleru právě z tohoto důvodu. Všechny programy (kromě velmi malých) jsou zřídkakdy psaný od začátku do konce v assembleru vzhledem k času a nákladům. Většina z nich se sestaví z vyššího programovacího jazyka a jsou ručně optimalizované právě odtamtud. Když účinnost a velikost kódu jsou méně důležité, tak velké části mohou být napsány v jazyce vyšší úrovně. S modernějšími optimalizacemi kompilátoru a s větší složitosti CPU, je mnohem obtížnější psát kód, který je optimalizován lépe než kód generovaný kompilátorem. Nicméně, velké množství kódu napsaného v dnešní době je sestaveno s úmyslem běžet na co největším množství možných strojů. V důsledku toho, programátoři a překladače ne vždy využívají účinnějších nebo novější procesory. Navíc může být kód vyladěný pro konkrétní procesor bez použití těchto pokynů stále optimální na jiném procesoru, který vyžaduje jiný způsob ladění kódu.

Za běhu programu (runtime)

Just-in-time překladače assembleru a programátoři mohou být schopni provést optimalizace za běhu programu. Tyto optimalizace přesahují schopnosti statických kompilátorů tím, že dynamicky nastavují parametry v závislosti na aktuálním vstupu nebo jiných faktorů.

Optimalizace závislé na platformě

Optimalizace kódu mohou být také obecně klasifikovány jako platformy závislé a nezávislé na platformě techniky. Zatímco druhá z nich je účinná na většině nebo všech platformách, na platformě závislé techniky se používají specifické vlastnosti jedné platformy, nebo se spoléhá na parametry v závislosti na jediné platformě nebo dokonce na jednom procesoru. Psaní nebo vyrábění různých verzí stejného kódu pro různé procesory tedy může být zapotřebí. Například v případě kompilace úrovně optimalizace, nezávislé na platformě techniky jsou obecné techniky (například smyčky, snížení volání funkce, paměťové efektivní rutiny, snížení podmínek atd.), které nejvíce ovlivňují CPU architektury podobným způsobem. Obecně platí, že tyto techniky slouží ke snížení celkové délky instrukční cesty k dokončení programu a nebo snížení celkové využití paměti během procesu. Na druhou stranu, na platformě závislé techniky zahrnují plánování instrukcí, instrukční paralelismus, datový paralelismus, technologie vyrovnávací paměti optimalizace (tj. parametry, které se liší mezi různými platformami) a optimální plánování instrukcí by mohlo být odlišné i na různých procesorech stejné architektury.

Odlišné algoritmy

Výpočetní úlohy lze provést několika různými způsoby s různou účinností. Mějme například následující C fragment kódu, jehož záměrem je získat součet všech celých čísel od 1 do N:

int i, sum = 0;
for (i = 1; i <= N; ++i) {
  sum += i;
}
printf("sum: %d\n", sum);

Tento kód může (za předpokladu, že nenastane aritmetické přetečení) být přepsán pomocí matematického vzorce, jako je:

int sum = N * (1 + N) / 2;
printf("sum: %d\n", sum);

Optimalizace se v některých případech provádí automaticky prostřednictvím optimalizace kompilátoru. Dále je nutné vybrat metodu (algoritmus), která je výpočetně efektivní, při zachování stejné funkčnosti. Viz algoritmická účinnost k diskusi o některých z těchto technik. Nicméně, významné zlepšení výkonu se často dalo dosáhnout tím, že odstraní nadbytečné funkce.

Optimalizace není vždy jasný a intuitivní proces. Ve výše uvedeném příkladu, může „optimální“ verze vlastně být pomalejší než původní verze, pokud N je dostatečně malé. Je třeba si také dát pozor na předsudky založené na zastaralých informacích jako například stále odolávající tvrzení, že sčítání je rychlejší než na násobení a dělení.

Rozsah optimalizací

• Lokální optimalizace
  • v rámci bloku programu (bez skoků, lineární zpracování)
  • nemusíme znát kontextovou gramatiku
• Globální optimalizace
  • v rámci podprogramů (reorganizace kódu funkcí a procedur, zánik částí)
  • v rámci celého programu (spojování funkcí s ohledem na to, že nejpoužívanější jsou pospolu)

Optimalizace cyklů

Analýza indukčních proměnných

Indukční proměnné jsou takové proměnné, které se v každé iteraci cyklu změní o konstantní hodnotu. Příkladem může být výpočet proměnné j:=4*i+1, kde i je číslo iterace. Náročná operace násobení zde může být nahrazena rychlejším postupným přičítáním v každé iteraci.

Štěpení cyklů

Při štěpení cyklů se překladač snaží rozdělit cykly na několik jednodušších, kdy každý vykonává určitou část těla původního cyklu. Tím lze optimalizovat lokální proměnné i zpracovávaných dat.

Slučování cyklů

Opak štěpení, kdy dochází ke sloučení těl dvou cyklů se stejným rozsahem hodnot řídící proměnné (konkrétní rozsah nemusí být při kompilaci známý). Tím lze redukovat režijní náklady cyklu.

Zaměňování cyklů

V této technice se zaměňují vnější a vnořené cykly tak, aby byla zlepšena lokálnost proměnných nebo zpracovávaných dat a lépe využívána cache procesoru.

Invariant cyklu

Pokud je nějaký výraz v cyklu přepočítáván v každé iteraci znovu, přičemž má konstantní hodnotu, je možné ho vyhodnotit pouze jednou před začátkem cyklu a tím zjednodušit výpočet uvnitř těla cyklu.

Rozvinutí cyklu

Tělo původního cyklu se provede při každé iteraci několikrát, čímž dochází k redukci celkového počtu iterací a tím i režijních nákladů cyklu. Navíc tak dochází ke zmenšení počtu skoků, díky čemuž se lépe využívá pipeline procesoru. Pro úplné rozvinutí cyklu je nutné znát počet iterací již při kompilaci.

Unswitching

Unswitching je technika, při které se kompilátor snaží odstranit podmíněné skoky uvnitř těla cyklu tak, že je přesune vně cyklu a tělo cyklu poté duplikuje do každé větve podmínky. Podmínka se pak vyhodnocuje pouze jednou před začátkem cyklu.

Automatická paralelizace

Cyklus je převeden na vícevláknový nebo vektorizovaný kód pro efektivnější výpočet na víceprocesorových počítačích se sdílenou pamětí.

Analýza toku dat

Eliminace společných podvýrazů

Některé výrazy obsahují opakující se podvýrazy, které není nutné počítat vždy znovu. Například ve výrazu (a+b)-(a+b)/4 se podvýraz (a+b) během výpočtu nemění a je tedy možné ho vypočítat pouze jednou.

Výpočet konstantních výrazů

Konstantní výrazy jako (3+5) lze vypočítat již během překladu, nahradit ve zdrojovém kódu jejich výslednou hodnotou a tím ušetřit čas při běhu programu.

Analýza ukazatelů

Pokud jsou ve zdrojovém kódu použity ukazatele, je obtížné ho optimalizovat, protože při zápisu do paměti pomocí ukazatele může dojít ke změně libovolné proměnné uložené na adrese zápisu. Analýza ukazatelů se proto snaží určit, které ukazatele a proměnné operují se stejnou pamětí, čehož pak lze využít při další optimalizaci.

Optimalizace při generování kódu

Alokace registrů

Nejčastěji používané proměnné by měly být uloženy v registrech procesoru kvůli rychlému přístupu. Pro detekci proměnných, jejichž platnosti se vzájemně překrývají (existují nějakou dobu současně), je vytvořen graf, ve kterém uzly představují proměnné a hrany označují překrývání platností. Uzly tohoto grafu jsou poté obarveny nějakým algoritmem, přičemž počet použitých barev odpovídá počtu registrů. Pokud algoritmus barvení selže, je jedna proměnná odstraněna z grafu, přemístěna do operační paměti a algoritmus zopakován.

Výběr instrukcí

U mnoha procesorových architektur, obzvláště CISC a takových, které umožňují mnoho adresových módů, je obvykle možné požadovanou operaci provést různými sekvencemi instrukcí. Generátor kódu se pak snaží vybrat pro každý operátor tyto instrukce co nejvhodněji v závislosti na požadavcích (rychlost, velikost…).

Plánování instrukcí

Plánování instrukcí je důležité pro jejich správné zřetězení a efektivní využití pipeline procesoru, kde poté nevznikají prázdná místa. Toho je docíleno shlukováním instrukcí, které nejsou vzájemně závislé, přičemž vždy ale musí být dodržena sémantika původního kódu.

Opakovaný výpočet

Někdy může být opakovaný výpočet nějaké hodnoty efektivnějším způsobem, než její načtení z operační paměti. Tohoto způsobu se využívá pro omezení přenášení proměnných z registrů do paměti.

Reference

V tomto článku byl použit překlad textu z článku Compiler optimization na anglické Wikipedii.

Externí odkazy

• Stránka Paula Hsiehe o optimalizaci, má příklady některých zmíněných optimalizací v C kódu, anglicky