Od programu obvykle chceme, aby zabíral co nejmén╪ místa a p²itom aby b╪ºel co nejrychleji. Toho lze, jak známo, dosáhnout jeho optimalizací a snad kaºd∞, kdo alespoσ trochu p²iƒichl k programování, vysype toto obecné tvrzení z rukávu. Horτí uº to bude s odpov╪dí na otázku, co to ta optimalizace vlastn╪ je.
Dobr∞, lepτí, nejlepτí
Neº se do úvah o optimalizaci pustíme, rád bych upozornil, ºe i kdyº je následující povídání zaloºeno p²edevτím na zkuτenostech s jazyky C a C++, mnohé z jeho záv╪rà platí i obecn╪.
Velikost versus rychlost
Na první pohled by se mohlo zdát, ºe ze dvou programà, které ²eτí t∞º problém, bude ten menτí také rychlejτí. Dále si ukáºeme, ºe to obecn╪ neplatí, ale urƒitá souvislost tu p²ece jenom je, zejména u opravdu rozsáhl∞ch programà.
Dneτní operaƒní systémy pracují s tzv. virtuální pam╪tí, coº je mechanismus, kter∞ umoºσuje vyuºívat ƒást diskového prostoru jako operaƒní pam╪£, tedy RAM. (Mechanismy pro podporu virtuální pam╪ti jsou dnes zpravidla zabudovány p²ímo v procesoru. Mají je nap². i procesory Intel 80386 a pozd╪jτí.) Program se tedy nemusí cel∞ vejít do operaƒní pam╪ti, n╪které ƒásti (tzv. stránky) kódu nebo dat mohou b∞t uloºeny na disku. Program pak p²i b╪hu "swapuje": p²i v∞padku stránky (page fault), tj. poºadavku na data nebo kód, kter∞ není v operaƒní pam╪ti, p²eƒte operaƒní systém pot²ebné stránky z disku a p²ípadn╪ odloºí zp╪t ty, které nepot²ebuje, ale které se p²edtím zm╪nily.
P²itom je ovτem podstatné, ºe p²ístup na disk je o n╪kolik ²ádà pomalejτí neº p²ístup do operaƒní pam╪ti. Proto ƒím v╪tτí je program, tím v╪tτí je i pravd╪podobnost v∞padku stránky, a tak se màºe jinak kvalitní program stát prakticky nepouºiteln∞m, jestliºe zabírá p²íliτ mnoho místa, nebo jestliºe i jinak "rozumn╪" velik∞ program spustíme na poƒítaƒi s p²íliτ malou operaƒní pam╪tí.
T²i oblasti optimalizace
Zamyslíme-li se nad problémem optimalizace obecn╪ji, zjistíme, ºe màºeme hovo²it o t²ech oblastech, ve kter∞ch se p²ekladaƒ a programátor v ràzném pom╪ru d╪lí o kompetence. První oblast se t∞ká volby algoritmà p²i ²eτení problému a spadá v∞luƒn╪ do pravomoci programátora. V této oblasti lze získat nebo ztratit zdaleka nejvíce. Druhá oblast zahrnuje spolupráci programátora s p²ekladaƒem; jde o vyuºití registrov∞ch prom╪nn∞ch, voleb pro optimalizaci atd. Do t²etí oblasti pak lze zapoƒítat optimalizace zaloºené na specifick∞ch vlastnostech strojního kódu cílového poƒítaƒe - ty uº pat²í v∞luƒn╪ do kompetence p²ekladaƒe.
V∞znam t²etí oblasti - stejn╪ jako druhé - je menτí neº v∞znam oblasti první, to ale neznamená, ºe je vºdy zanedbateln∞. Uplatní se hlavn╪ u dlouh∞ch programà, u programà obsahujících cykly s velk∞m poƒtem opakování apod. Povídání o druhé oblasti vτak bude nejrozsáhlejτí, a proto si je necháme aº na konec.
Optimalizace nejvyττí úrovn╪
Zeptáte-li se programátora, proƒ je jeho program tak pomal∞, ƒasto uslyτíte n╪jak∞ povzdech na téma nedokonalého p²ekladaƒe, kter∞ vàbec neumí optimalizovat, nedokonalého operaƒního systému a bàhví ƒeho jeτt╪. Málokdy uslyτíte o nedokonalém programátorovi, kter∞ nedokáºe vybrat optimální algoritmus - a p²ece práv╪ to màºe b∞t p²íƒinou pomalého b╪hu programu. Zisky nebo ztráty v této oblasti jsou totiº obvykle zdaleka nejv∞razn╪jτí.
Typick∞m p²íkladem mohou b∞t algoritmy pro t²íd╪ní polí, tj. pro p²erovnání jejich prvkà podle velikosti. Ze základního kurzu programování víme, ºe sloºitost algoritmu t²íd╪ní haldou (heap sort) nebo rychlého t²íd╪ní (quick sort) je v p²ípad╪ pole o n prvcích rovna hodnot╪ O(n*ln n), tzn. je úm╪rná ƒíslu n*ln n, zatímco sloºitost jednoduττích metod, jako je t²íd╪ní vkládáním (insertion sort), je O(n2). V╪c se tedy zdá jasná: zapomeneme na jednoduché metody, které se sice snadno uƒí a snadno programují, ale jinak za mnoho nestojí, a budeme pouºívat jen metody efektivní, by£ sloºité.
Zdání ovτem màºe klamat. Pro t²íd╪ní polí s mal∞m poƒtem prvkà mohou totiº b∞t jednoduché metody v∞hodn╪jτí. Postavme si vedle sebe n╪kolik podobn∞ch (a zdánliv╪ ekvivalentních) úloh:
- set²ídit jedno jediné celoƒíselné pole o 1 000 000 prvkà,
- set²ídit 10 celoƒíseln∞ch polí o 100 000 prvkà,
- set²ídit 100 celoƒíseln∞ch polí o 10 000 prvkà
atd.
I kdyº ve vτech p²ípadech t²ídíme milion cel∞ch ƒísel, v∞sledky ràzn∞ch t²ídicích metod se budou v∞razn╪ liτit. P²ipojená tabulka ukazuje pràm╪rné ƒasy v sekundách pot²ebné pro tyto úlohy p²i t²íd╪ní vkládáním a p²i t²íd╪ní haldou. Vidíme, ºe pro velmi malá pole màºe b∞t v∞hodn╪jτí t²íd╪ní vkládáním (které p²edstavuje více jednoduch∞ch operací), neº t²íd╪ní haldou, které znamená sice mén╪ operací, ovτem podstatn╪ sloºit╪jτích.
Optimalizace nejniºτí úrovn╪
Tato oblast optimalizace vyuºívá specifik strojního kódu cílového procesoru. Mnohé konstrukce z vyττích programovacích jazykà lze p²eloºit n╪kolika zpàsoby. Efekt je stejn∞, tedy program ud╪lá totéº, ovτem v∞sledn∞ kód je podle okolností menτí nebo rychlejτí.
Jako p²íklad vezmeme procesory jedné z nejrozτí²en╪jτích znaƒek - Intel. Chceme-li nap². do prom╪nné X typu int uloºit hodnotu 0, màºeme pouºít bu╘ instrukci
MOV dword ptr[X],0
nebo
AND dword ptr[X],0
V∞sledek, tedy stav dat, je v obou p²ípadech stejn∞, avτak první instrukce zabere 6 bajtà a trvá 3 takty, zatímco druhá zabere 9 bajtà a trvá 1 takt. Zde tedy stojíme p²ed volbou rychlost nebo velikost, nemàºeme vτak mít obojí.
V tomto p²ípad╪ màºeme uτet²it na jedné instrukci 2 takty. Abychom si uv╪domili souvislosti, p²ipomeσme si, ºe procesor s taktovací frekvencí 100 MHz - ale tak "zastaralé" procesory se uº snad ani nedají sehnat - provede za sekundu práv╪ sto milionà taktà. Abychom tedy zrychlili b╪h programu o jedinou sekundu, musíme uτet²it stovky milionà taktà. To je moºné, pokud program obsahuje nap²íklad velmi rozsáhlé cykly.
Je asi jasné, ºe optimalizace na této úrovni je v∞luƒnou záleºitostí p²ekladaƒe - samoz²ejm╪ pokud nechceme programovat v asembleru a neustále porovnávat ƒasovou a prostorovou nároƒnost kódu.
St²ední úroveσ optimalizace
Do této oblasti spadají optimalizaƒní techniky, na kter∞ch spolupracuje p²ekladaƒ s programátorem. V╪tτinou to znamená, ºe programátor p²ekladaƒi pomocí voleb nebo klíƒov∞ch slov naznaƒí, kterou z moºností má p²ekladaƒ pouºít a co màºe p²ekladaƒ o programu p²edpokládat. Obvykle ale màºe zasáhnout programátor a provést odpovídající úpravy na úrovni zdrojového kódu sám.
Tyto techniky mohou, ale nemusí vést k cíli. N╪které lze pouºít jen za jist∞ch p²edpokladà, jiné mohou n╪kdy dokonce situaci zhorτit. ¼asto je t²eba zkusmo urƒit, které z nich mají a které nemají v daném p²ípad╪ ºádan∞ úƒinek. Podíváme se na n╪které z nejƒast╪ji pouºívan∞ch zpàsobà.
Sluƒování cyklà
Pokud se v programu vyskytují dva cykly se stejn∞m rozsahem a s nezávisl∞m obsahem, je rozumné je slouƒit do jednoho cyklu (loop jamming). Chceme-li nap². vynulovat dv╪ pole a a b o N prvcích, màºeme napsat
for(int i = 0; i < N; i++) a[i] = 0;
for(int i = 0; i < N; i++) b[i] = 0;
ale rozumn╪jτí je slouƒit oba cykly do jednoho,
for(int i = 0; i < N; i++)
{
a[i] = 0;
b[i] = 0;
}
nebo£ se tím uτet²í "administrativa", tj. instrukce, které ²ídí opakování cyklu.
Práce s registry
Pouºívání klíƒového slova register pat²í k nejstarτím optimalizaƒním moºnostem, zaveden∞m jiº v jazyce C podle Kernighana a Ritchieho. Jist╪ si vzpomenete, ºe toto klíƒové slovo má za úkol naznaƒit p²ekladaƒi, ºe práv╪ deklarovanou prom╪nnou nebo parametr budeme dále ƒasto pouºívat a ºe by se m╪l pokusit uloºit ji do n╪kterého z registrà procesoru; p²ístup k registràm je totiº zpravidla podstatn╪ rychlejτí neº p²ístup do pam╪ti.
Dnes uº je vτak toto klíƒové slovo tém╪² zbyteƒné, nebo£ v╪tτina p²ekladaƒà pouºívá rafinované algoritmy, pomocí nichº urƒí, které prom╪nné je vhodné uloºit do registrà (a obvykle to odhadne lépe neº programátor). P²ekladaƒe ƒasto dávají programátorovi na vybranou, zda chce, aby se ²ídily jeho poºadavky, aby registrové prom╪nné nepouºívaly vàbec (ani tam, kde je to v programu p²edepsáno - to se hodí p²i lad╪ní), nebo aby je p²ekladaƒ pouºíval dle vlastního uváºení. Poslední moºnost zpravidla vede k nejlepτím v∞sledkàm.
Vloºené funkce
Pouºívání vloºen∞ch funkcí (inline) není (zatím) souƒástí jazyka C, najdeme je aº v jazyce C++, ale ve skuteƒnosti jde o jeden z nejstarτích optimalizaƒních trikà, které mohl programátor pouºívat. S jejich obdobou jsme se mohli setkat nap². uº v dávn∞ch verzích Fortranu (jednop²íkazové funkce - statement function).
Volání b╪ºné funkce znamená vºdy jistou reºii. P²i volání je to uloºení parametrà a návratové adresy do zásobníku, vytvo²ení rámce zásobníku a lokálních prom╪nn∞ch atd., p²i návratu mj. p²edání návratové hodnoty, odstran╪ní lokálních prom╪nn∞ch a skuteƒn∞ch parametrà atd.
Vloºené funkce, tj. funkce s modifikátorem inline, se sice po syntaktické stránce chovají jako funkce, ale p²ekladaƒ je pouºívá podobn╪ jako makra. To znamená, ºe na místo volání vloºí t╪lo této funkce. To zpravidla vede k rozsáhlejτímu, ale rychlejτímu programu.
Modifikátor inline ovτem - podobn╪ jako modifikátor register - není pro p²ekladaƒ závazn∞. To znamená, ºe p²ekladaƒ màºe usoudit, ºe danou funkci není vhodné p²ekládat jako vloºenou, a bude s ní zacházet jako s obyƒejnou funkcí. Zapíτeme-li takovouto funkci do hlaviƒkového souboru, màºe se stát, ºe p²ekladaƒ vytvo²í její t╪lo v kaºdém ze souborà, ve kterém takov∞to hlaviƒkov∞ soubor pouºijeme. Pak pouºitím vloºen∞ch funkcí nezískáme ºádnou v∞hodu, pouze zv╪tτíme v∞sledn∞ program. (To ovτem není typická situace.)
P²ekladaƒe obvykle dávají na vybranou moºnost klíƒové slovo inline ignorovat; to se hodí op╪t zejména p²i lad╪ní. Vedle toho nabízejí n╪které p²ekladaƒe také moºnost p²ekládat jako vloºené n╪které z knihovních funkcí, které jsou jinak p²ekládány "normáln╪" (obvykle se tato volba jmenuje inline intrinsic functions).
Poznamenejme jeτt╪, ºe p²ekladaƒ màºe v p²ípad╪ pot²eby pouºít funkci obojím zpàsobem - jako vloºenou i jako normální.
µí²ení konstant a kopií
Tato optimalizaƒní technika je zaloºena na skuteƒnosti, ºe pouºití konstant v instrukcích je rychlejτí neº práce s registry a práce s registry je rychlejτí neº práce s operaƒní pam╪tí. µí²ení konstant (constant propagation) lze pouºít v situaci, kdy do jedné prom╪nné p²i²adíme konstantu a tuto hodnotu pak "poτleme dál", aniº bychom ji mezitím pouºili. To znamená, ºe pokud v programu napíτeme nap².
a = 10; // (1)
b = a; // (2)
kde a, b jsou typu int, p²epíτe to p²ekladaƒ do tvaru
a = 10;
b = 10;
P²itom mezi (1) a (2) mohou b∞t dalτí p²íkazy, nesm╪jí ovτem pracovat s hodnotu uloºenou do a. (Zde se tedy "rozτí²ila" konstanta 10.)
µí²ení kopií (copy propagation) je podobné: Jestliºe p²i²adíme do jedné prom╪nné hodnotu a tuto hodnotu pak "poτleme dál", aniº bychom ji mezitím pouºili, màºe si p²ekladaƒ ponechat v registru její hodnotu a tak urychlit b╪h programu tím, ºe uτet²í p²ístup do pam╪ti. Jestliºe tedy v programu napíτeme
a = x;
F(a);
kde a i x jsou stejného typu, p²epíτe to p²ekladaƒ do tvaru
a = x;
f(x);
Nepouºit∞ kód a nepouºitá pam╪£
P²i optimalizaci (ale také vinou nepozornosti programátora, p²i rozvoji maker nebo τablon atd.) màºe nastat situace, ºe do prom╪nné uloºíme hodnotu, kterou program nikdy nepouºije. Takové p²i²azení lze z programu vypustit (store elimination). Podívejme se na uƒebnicov∞ p²íklad. Jestliºe ve zdrojovém textu napíτeme
a = x;
f(a);
a = y;
a p²ekladaƒ pouºije techniku τí²ení kopií, vznikne
a = x; // (1)
f(x);
a = y;
P²i²azení hodnoty prom╪nné a je naprosto zbyteƒné, samoz²ejm╪ za p²edpokladu, ºe a není globální prom╪nná a funkce f() ji nepouºívá. To ale znamená, ºe p²ekladaƒ màºe p²íkaz (1) prost╪ odstranit a p²epsat tento úsek programu do tvaru
f(x);
a = y;
Podobn╪ se v programu màºe objevit nepouºit∞ (mrtv∞) kód (dead code) - úsek programu, kter∞ nemàºe b∞t nikdy provád╪n. P²ekladaƒ ho màºe odstranit. Tím se sice program nezrychlí, ale zmenτí, a to màºe za jist∞ch okolností také vést ke zrychlení.
Spoleƒné podv∞razy
Tato optimalizace je podobná τí²ení kopií. Jestliºe se na n╪kolika místech v programu objeví t∞º v∞raz nebo dílƒí v∞raz, màºe p²ekladaƒ p²epsat program tak, ºe se tento podv∞raz vypoƒte jen jednou a jeho hodnota se uloºí do pomocné prom╪nné. To znamená, ºe nap². následující úsek programu
x = (a+b)*c;
y = sin(a+b);
p²epíτe do tvaru
pom = a+b;
x = pom*c;
y = sin(pom);
Je urƒit╪ z²ejmé, ºe eliminace spoleƒn∞ch podv∞razà (common subexpression elimination) povede tém╪² vºdy ke zrychlení programu. Za jist∞ch okolností - jestliºe se podv∞razy objevují dostateƒn╪ ƒasto - màºe zpàsobit i zmenτení programu.
P²íτt╪
Tolik pro dneτek - p²íτt╪ si povíme o n╪kter∞ch dalτích optimalizaƒních technikách a p²ipojíme i n╪kolik obecn∞ch úvah o v∞znamu optimalizace.
