V prvním dílu povídání o optimalizaci jsme se seznámili s n╪kolika technikami, které mohou vést ke zrychlení nebo ke zmenτení rozsahu p²eloºeného programu. Dnes toto povídání dokonƒíme. P²ipomeσme nejprve, ºe jsme si moºné optimalizaƒní postupy rozd╪lili do t²í základních kategorií. V minulém ƒísle jsme probrali nejniºτí a nejvyττí z nich a zaƒali jsme se v╪novat té nejrozsáhlejτí - optimalizaƒním technikám, p²i nichº spolupracuje p²ekladaƒ. Nyní se podíváme na dalτí moºnosti.
Optimalizace cyklà
Cyklus by m╪l obsahovat jen p²íkazy, které je nezbytné opakovat - vτe ostatní zdrºuje. Jestliºe nap². chceme vyplnit vτechny prvky pole a sinem x, màºeme napsat
for(int i = 0; i < N; i++) a[i] = sin(x);
Ovτem v∞poƒet funkce sinus pro konstantní argument je zbyteƒné opakovat N-krát a sluτn∞ p²ekladaƒ tento cyklus upraví (²íká se tomu constant code elimination) na tvar
pom = sin(x);
for(int i = 0; i < N; i++) a[i] = pom;
P²erovnávání instrukcí
Superskalární procesory, jako je Pentium a jeho následovníci, obsahují dv╪ v∞konné jednotky. To znamená, ºe takov∞ procesor màºe provád╪t dv╪ instrukce zároveσ, ovτem za p²edpokladu, ºe na sob╪ nezávisí, tj. ºe v∞sledek jedné není vstupem druhé. Pokud na sob╪ instrukce závisí, bude jedna z v∞konn∞ch jednotek blokována a program se tím zpomalí. N╪kdy je ovτem moºné instrukce v p²eloºeném programu p²erovnat (instruction scheduling) tak, aby k blokování nedocházelo. Podívejme se na uƒebnicov∞ p²íklad. Jestliºe p²eloºen∞ program obsahuje instrukce
sub ax, 10 ; (1)
movsx ebx, ax ; (2)
xor ecx, ecx ; (3)
v uvedeném po²adí, pak první dv╪ instrukce na sob╪ závisí (v první odeƒítáme 10 od obsahu registru AX, ve druhé p²esunujeme v∞sledek se znaménkov∞m rozτí²ením do registru EBX). T²etí instrukce nuluje obsah registru ECX a je na p²edchozích dvou nezávislá. Pokud by m╪l procesor provád╪t tyto instrukce v uvedeném po²adí, musel by s druhou instrukcí poƒkat, aº skonƒí první. Jestliºe je ale p²ekladaƒ p²erovná do po²adí
sub ax, 10 ; (1)
xor ecx, ecx ; (3)
movsx ebx, ax ; (2)
mohou prob╪hnout instrukce (1) a (3) zároveσ a k blokování nedojde.
Posun místo d╪lení a násobení
Celoƒíselné násobení mocninou dvou, tedy ƒíslem tvaru 2n, znamená vlastn╪ jen posun o n bità doleva, tj. v∞poƒet x*8 je ekvivalentní v∞poƒtu x << 3. Podobn╪ d╪lení je ekvivalentní posunu doprava (se znaménkem). Náhrada aritmetick∞ch operací bitov∞m posunem vede nejen ke zrychlení, ale ƒasto i ke zkrácení programu. Jednak instrukce pro posun jsou samy o sob╪ v∞razn╪ rychlejτí neº aritmetické operace, jednak lze posuny provád╪t p²ímo v pam╪ti, zatímco pro aritmetické operace musíme operandy nejprve p²enést do registrà a pak v∞sledek zase uloºit do pam╪ti. Poznamenejme, ºe tuto optimalizaci (strength reduction) provád╪jí mnohé p²ekladaƒe automaticky, dokonce i p²i vypnutí vτech optimalizaƒních p²epínaƒà.
Sluƒování ²et╪zcà
Pokud se v programu opakují znakové ²et╪zce, màºe je p²ekladaƒ slouƒit, tj. pouºít ve vτech p²ípadech odkaz na tutéº ²et╪zcovou konstantu (string pooling). To vede ke zmenτení programu, na rychlost to p²ím∞ vliv pochopiteln╪ nemá.
Standardní rámec zásobníku
P²i p²ekladu podprogramà (tj. funkcí) se obvykle pouºívá konstrukce, které se ²íká standardní rámec zásobníku (standard stack frame). Je to posloupnost instrukcí v úvodu a záv╪ru funkce. Θvodní posloupnost, "prolog", definuje ƒást zásobníku, která je pro aktuální volání funkce vyhrazena. K orientaci v této ƒásti pam╪ti vyuºívá p²ekladaƒ registru EBP, kter∞ obsahuje ukazatel na v∞znaƒné místo v zásobníku, slouºící jako jak∞si "poƒátek soustavy sou²adnic". Záv╪reƒná posloupnost instrukcí, "epilog", tento rámec zruτí a obnoví rámec funkce volající.
Jestliºe p²ekladaƒi zakáºeme pouºívat standardní rámec zásobníku, bude jako vztaºn∞ bod pouºívat místo EBP vrchol zásobníku, tedy registr ESP. Zjednoduτí se tím o n╪kolik instrukcí t╪lo funkce (tedy zrychlí se nepatrn╪ b╪h programu) a uvolní se tak registr EBP pro jiná pouºití (to màºe b∞t podstatn╪ v∞znamn╪jτí). Na druhé stran╪ tím ale znesnadníme, nebo znemoºníme ƒinnost n╪kter∞m ladicím nástrojàm, které na standardní rámec zásobníku spoléhají.
Podrobn╪ji se na standardní rámec zásobníku n╪kdy podíváme v samostatném ƒlánku.
Kontrola zásobníku
Volba umoºσující zakázat, nebo povolit kontrolu zásobníku (stack checking) se vyskytovala uº v 16bitov∞ch p²ekladaƒích, její dneτní v∞znam je vτak diametráln╪ odliτn∞. V obou p²ípadech zákaz kontroly zásobníku znamená zmenτení programu a zrychlení jeho b╪hu, ovτem za cenu jistého rizika b╪hové chyby.
V 16bitovém prost²edí byla velikost zásobníku pevn╪ stanovena p²i spuτt╪ní programu. Kontrola zásobníku tedy znamenala volání pomocné funkce, která p²i vstupu do podprogramu zjistila, zda je k dispozici dostatek místa pro jeho lokální prom╪nné. Teprve pak se v zásobníku pot²ebné místo vyhradilo.
Ve 32bitov∞ch Windows není kontrola tohoto typu nezbytná, nebo£ operaƒní systém obsahuje mechanismus, kter∞ zabraσuje p²eteƒení zásobníku. Abychom tento mechanismus pochopili, musíme si uv╪domit, ºe Windows p²id╪lují pam╪£ programàm po tzv. stránkách (zpravidla o velikosti 4 KB), a to ve dvou krocích. Nejprve pam╪£ vyhradí (reserve), pak ji p²edají (commit). P²itom s pouze vyhrazenou pam╪tí program jeτt╪ nesmí pracovat - pokus o p²ístup do ní zpàsobí poruτení ochrany pam╪ti. Pouºívat lze aº pam╪£ p²edanou.
Zásobník se skládá z n╪kolika stránek p²edan∞ch programu. Poslední z nich p²itom slouºí jako jakési "hladinové ƒidlo": jestliºe ji program pouºije, pochopí to operaƒní systém jako upozorn╪ní, ºe màºe dojít k p²eteƒení zásobníku, a p²edá programu dalτí stránku.
Problémy zde mohou nastat, jestliºe program deklaruje velké pole, které zabírá n╪kolik stránek. Deklarace
void test() {
int Pole[10000];
// ...
}
sice zpàsobí, ºe po vstupu do funkce test() se ukazatel na vrchol zásobníku posune nejmén╪ o sizeof(int)*10000 bajtà, ovτem tím se pam╪£ programu jeτt╪ nep²id╪lí, pouze vyhradí. To znamená, ºe pokud doplníme p²edchozí ukázku do podoby
void test() {
int Pole[10000];
Pole[9999] = 999999; // Chyba?
}
màºe volání této funkce skonƒit poruτením ochrany pam╪ti, nebo£ deklarace prom╪nné Pole vyhradí tém╪² 10 stránek, které se ale programu nep²edají; p²itom vτak následující p²íkaz pouºívá poslední z nich.
Standardn╪ se proto po vyhrazení pam╪ti volá pomocná funkce, která se "dotkne" po ²ad╪ vτech nov╪ vyhrazen∞ch stránek a tím zpàsobí jejich p²edání programu. (To je práv╪ ona "kontrola zásobníku" ve Win32.)
Pokud si ovτem jsme jisti, ºe s prvky nov╪ alokovan∞ch velk∞ch polí napoprvé budeme pracovat nap². v po²adí podle rostoucích indexà, màºeme kontrolu zásobníku vypnout a tím zrychlit b╪h programu.
P²ekr∞vání prom╪nn∞ch v zásobníku
Obƒas se v jedné funkci vyskytnou vedle sebe lokální prom╪nné, jejichº "doby ºivota" se nep²ekr∞vají. To mohou b∞t lokální prom╪nné deklarované ve dvou za sebou následujících blocích, mohou to ale také b∞t lokální prom╪nné - ²ekn╪me x a y - deklarované ve stejném bloku, pro které platí, ºe poslední pouºití x p²edchází prvnímu pouºití y. P²ekladaƒ màºe v takovém p²ípad╪ pouºít pro ob╪ prom╪nné totéº místo v zásobníku (stack overlays).
Jak∞ to màºe mít v∞znam? Jednak se tím samoz²ejm╪ zmenτuje nebezpeƒí p²eteƒení zásobníku, jednak to ale màºe vést i ke zmenτení a zrychlení b╪hu programu. P²ipomeσme si, ºe lokální prom╪nné jsou v programu adresovány relativn╪ vzhledem k urƒitému v∞znaƒnému bodu zásobníku, a to bu╘ k místu, na které ukazuje registr EBP (jestliºe pouºíváme standardní rámec zásobníku), nebo k vrcholu zásobníku. Je-li lokální prom╪nná od tohoto v∞znaƒného bodu vzdálena o mén╪ neº 128 bajtà, budou instrukce, které s ní pracují, o 3 bajty kratτí neº v p²ípad╪, ºe bude od tohoto bodu vzdálena více.
P²ezdívky
Jako "p²ezdívky" (aliases) se v této souvislosti oznaƒuje pouºívání ràzn∞ch identifikátorà pro tutéº prom╪nnou. V C++ se za tím màºe skr∞vat p²edevτím p²ístup k prom╪nné pomocí referencí nebo ukazatelà anebo pouºití prom╪nné jako sloºky anonymní unie; ve Fortranu by to mohlo b∞t pouºití prom╪nné v p²íkazu EQUIVALENCE. Pouºijeme-li v programu p²ezdívky, znemoºníme tím p²ekladaƒi celou ²adu optimalizací, nap². ukládání prom╪nn∞ch do registrà, τí²ení kopií nebo eliminaci spoleƒn∞ch podv∞razà, nebo£ p²ekladaƒ si nemàºe b∞t jist, zda se nap². prom╪nné ve spoleƒném podv∞razu mezi jeho jednotliv∞mi pouºitími nezm╪ní, a zda ho tedy není t²eba vyhodnocovat pokaºdé znova.
Jestliºe nap²íklad napíτeme
a = x+y;
fun(&x);
b = x+y;
musí p²ekladaƒ p²edpokládat, ºe funkce fun() zm╪ní hodnotu prom╪nné x, a proto musí podv∞raz vypoƒítat znovu.
V n╪kter∞ch p²ípadech dokáºe p²ekladaƒ zjistit, zda ukazatele nebo reference zpàsobí zm╪nu prom╪nné, a v p²ípad╪, ºe nikoli, v∞sledn∞ program optimalizovat. To ovτem neplatí t²eba v p²ípad╪ ukazatelà pouºit∞ch jako skuteƒné parametry funkcí, nebo£ ràzné funkce mohou b∞t p²ekládány samostatn╪.
Jeτt╪ horτí jsou ukazatele vracené funkcemi jako v∞sledek. Nap². ukazatel uk, kterému p²i²adíme hodnotu p²íkazem
char *uk = GetPtr();
màºe ukazovat na tém╪² kteroukoli prom╪nnou v programu a zpàsobovat tak její zm╪ny. Vyskytují-li se v programu podobné konstrukce, musí p²ekladaƒ pouºít konzervativní (pesimistickou) strategii a upustit od ²ady optimalizací. Volbou assume no aliases slibujeme p²ekladaƒi, ºe prom╪nné v programu nemají skryté p²ezdívky, a umoºσujeme mu vyuºít optimistickou strategii optimalizace.
N╪které p²ekladaƒe, nap². Visual C++, také nabízejí volbu assume aliasing across function call. Touto volbou ²íkáme, ºe p²ezdívky se v programu vyskytují pouze v rámci volání funkcí. To je sice velice vágní informace, ale i tak umoºσuje alespoσ n╪které optimalizace.
Sestavování jednotliv∞ch funkcí
Zdrojov∞ program màºe obsahovat funkce, které v programu nejsou vàbec volány. To mohou b∞t nap². nepouºité metody objektov∞ch typà z knihovny, mohou to ale b∞t i funkce, které p²ekladaƒ pouºil jako vloºené (inline). P²eloºené t╪lo funkce ovτem musí zàstat souƒástí souboru p²eloºeného programu (.OBJ), nebo£ p²i sestavování se màºe ukázat, ºe tuto funkci volá jiná ƒást programu, p²ekládaná samostatn╪. Optimalizaci tohoto druhu tedy màºe zajistit pouze sestavovací program (linker).
P²ekladaƒ ovτem màºe vτechny funkce v p²eloºeném kódu "zabalit", tj. vloºit do p²eloºeného modulu informace umoºσující linkeru rozpoznat nepouºité funkce a p²i sestavování je eliminovat (function-level linking). Tato optimalizace pochopiteln╪ neovlivní p²ímo rychlost programu, màºe ale zmenτit jeho velikost.
Zdroje neefektivnosti
P²edchozí odstavce ukazují, ºe v╪tτinu z "drobn∞ch" optimalizací by si - alespoσ v principu - mohl ud╪lat (dobr∞) programátor sám. Není tedy optimalizace tohoto druhu zbyteƒná? Vºdy£ koneckoncà programátor, kter∞ napíτe (ƒi spíτe spáchá) cyklus
for(int i = 0; i < 100000; i++)
a[i] = sin(x);
by se m╪l vrátit do τkoly a zopakovat si základy programování.
Ve skuteƒnosti se ale s podobn∞mi, a ƒasto i horτími konstrukcemi setkáme p²i rozvoji komplikovan∞ch maker nebo τablon. Zdrojem neefektivnosti mohou b∞t i dnes tak oblíbené generátory kódu (ràzní τamani, kte²í na základ╪ vypln╪ného dotazníku sestaví kostru aplikace, p²idávají do aplikace funkce, t²ídy atd.), prost²edky oznaƒované CASE, RAD atd., nebo£ tyto prost²edky pracují na úrovni p²íliτ vzdálené strojnímu kódu, neº aby dokázaly generovat za vτech okolností úƒinn∞ program.
Dalτím zdrojem neefektivit màºe b∞t samotn∞ p²ekladaƒ; koneckoncà alternativní termín kompilátor vystihuje jeho ƒinnost daleko p²esn╪ji: je to program, kter∞ na základ╪ zdrojového textu skládá z p²edem p²ipraven∞ch fragmentà cílov∞ program, v pravém smyslu slova jej kompiluje. V∞sledkem pak mohou b∞t ràzné podivné konstrukce, které jsou sice v╪cn╪ správné, ale nejsou optimální.
Nap²íklad p²ekladaƒ Borland C++ 3.1, dodnes pouºívan∞ pro vytvá²ení dosov∞ch aplikací, umoºσuje pouºívat tzv. registrové pseudoprom╪nné, které programátorovi zp²ístupσují obsah registrà procesoru. P²íkaz
f(_FLAGS);ve kterém voláme funkci f() a jako parametr (typu unsigned) jí p²edáváme obsah registru p²íznakà, se p²eloºí posloupností
pushf
pop ax
push ax
call near ptr @f$qui
První dv╪ instrukce p²ipraví obsah registru FLAGS do registru AX, t²etí instrukce uloºí takto p²ipravenou hodnotu na vrchol zásobníku jako parametr funkce f(). Druhá a t²etí instrukce je ovτem zbyteƒná; staƒilo by
pushf
call near ptr @f$qui
Má to vàbec v∞znam?
Z p²edchozího povídání by se mohlo zdát, ºe optimalizace na druhé a t²etí úrovni nemá praktick∞ v∞znam. Koneckoncà jde o jednotlivé instrukce, a my uº víme, ºe zde se úspory pohybují v jednotkách nebo desítkách taktà. Ovτem jestliºe se seƒtou úspory z celého programu, kter∞ obsahuje mnoho cyklà, mohou b∞t v∞sledky podstatné. P²ipojená tabulka ukazuje, jak se ƒas pot²ebn∞ k set²íd╪ní pole liτil v p²ípad╪, ºe p²ekladaƒ nepouºíval ºádné optimalizace, a v p²ípad╪, ºe pouºil standardní optimalizace pro koneƒnou verzi programu. (Jde o stejn∞ program jako v minulém ƒlánku.)
Kdy a co optimalizovat
Je asi jasné, ºe optimalizace, kterou uºivatel programu vàbec nezaznamená, je zbyteƒná. Rozdíl mezi t²íd╪ním haldou a vkládáním, kter∞ jsme ukázali v prvním dílu, je samoz²ejm╪ v∞znamn∞. Na druhé stran╪ úspory vzniklé pouºíváním registrov∞ch prom╪nn∞ch nemusí p²esáhnout pár sekund na jeden b╪h programu, a tedy nemusí b∞t nijak dàleºité.
V╪tτina dneτních programà spolupracuje interaktivn╪ s uºivatelem a ten je zpravidla nejpomalejτím ƒlánkem celého systému. To znamená, ºe - pokud jde o druhou úroveσ optimalizace - je v╪tτinou vhodn╪jτí optimalizovat velikost programu, nebo£ té si uºivatel vτimne vºdy. Optimalizace rychlosti má smysl p²edevτím u numerick∞ch v∞poƒtà, tedy u v╪deck∞ch a technick∞ch programà, a samoz²ejm╪ u ƒasov╪ kritick∞ch aplikací.
Miroslav Virius
Literatura
B. Zaratian: Microsoft Visual C++ 6.0 Programmer's Guide. Microsoft Press 1998.
N. Wirth: Algoritmy a τtruktúry údajov. Alfa, Bratislava 1988.
