Optimalizace program…
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.
Miroslav Virius