Optimizacija - clanak

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Autor: Emil Beli, tj Ja.

Nekoliko reci o optimizaciji kôda
=====================

Kao programer, verovtno ste se zapitali: "Kako da moj program bude brži?". Ovaj tekst ?e da vam da par saveta kako da pove?ate performanse
svojih programa, tako i da vas razreši osnovnih zabluda što se optimizacije ti?e.
Važno je napomenuti da optimizacija nije jednozna?na ve? da se sastoji iz više oblasti koje mogu, ali ne moraju imati veze jedna sa drugom.
Oblasti optimizacije po prioritetu:
- Brzina
- Veli?ina
- Održavanje
- Testiranje
- Ponovno koriš?enje kôda
- Robustnost
- Skalabilnost
- Efikasnost koriš?enja
- Sigurnost

Pre po?etka svake optimizacije, moramo postaviti ciljeve koje želimo da posti?i, i biti što realniji. Na primer, ne realno je da postavimo za cilj
poboljšanje kompresije sa sadašnjeg proseka od 50% na novi prosek od 98%.
Jednom kada se ciljevi postave, od dalje optimizacije se odustaje ?im dostignemo taj cilj. U praksi je dokazano da preterana optimizacija ne donosi
nikakvo poboljshanje, ve? stvara bagove, pogoršava ?itljivost kôda, a samim tim otežava održavanje.
Osnovno što treba znati, je da se optimizuju samo verzije programa koje su prošle kroz detaljano testiranje i debug, kao što su beta verzije i
verzija pred kona?no objavljivanje programa. Ne smemo zaboraviti da svaka optimizacija ima svoju cenu: program postaje manje ?itljiv, teže je
održavanje i može stvoriti nove greške.

Na po?etku, da se razrešimo osnovnih zabluda:
- Ve?a EXE arhiva, sem što o?igledno pove?ava vreme provedeno na internetu, skidaju?i ili postavljaju?i arhivu, ne usporava izvršavanje
programa. Sama funkcija CreateProcess koju Windows koristi da bi otvorio arhivu to radi na "On demand" tehnologiji, tj. u?itava samo ono što je
potrebno da bi se program pokrenuo i prikazao. Da ne ulazim u detalje kako sam Windows radi sa RAM i Virtualnom memorijom, možete se osloniti
na njega u potpunosti. Postoji slu?aj kada velicina EXE arhive usporava, a to je samo u slu?aju kada se program natrpava resursima nepotrebnnim
za osnovni korisni?ki interfejs, kao što su slike, fotografije, ikone, string tabele i sl. U slu?aju da su pomenuti resursi potrebni u nekoj drugoj fazi
izvršavanja, bolja je ideja napraviti jedan ili više resursnih biblioteka (DLL) i pozivati resurse po potrebi.
- U slu?aju malog broja lokalnih promenjljivih, optimizacija integera u word ili byte tip (double u single) i sl. kada njihove vrednosti ne prelaze
maksimum manjeg tipa na koji optimizujete, ne donosi nikakvo ubrzanje. Da bolje ilustrujem: Ako imate dve celobrojne promenjljive i vi ih postavite
na po?etku kao tip integer, a kasnije ustanovite da ni jedna ne?e biti negativna i da ne?e pre?i vrednost 255, dobra je programerska praksa
zameniti integer tip u tip Byte, jer ?e program zauzeti dva bajta memorije umesto osam, ali poboljšanja brzine ne?e biti. Ukoliko, ipak, imate
potrebu za ve?im brojem promenjljivih, promena tipa ?e da ima za posledicu zna?ajno smanjenje upotrebe memorije, a samim tim i performanse
rastu. Medjutim, upotreba velikog broja promenjljivih postavlja pitanje da li je ideja rešenja uopste dobra.


Naslov:Pove?anje brzine izvršavanja
Podnaslov: Otkrivanje uskog grla (Bottleneck detection)

Prvi korak ka optimizaciji je otkrivanje uskih grla u našem programu. Objasni?u kako se to radi ru?no, bez upotrebe naprednih aplikacija kao što
su: "Sleuth StopWatch", "Profiler" i dr. koji mere vreme izvršavanja svake funkcije ili procedure i daju savete kako rešiti izvestan deo problema.
Za po?etak, trebate otkriti koliko se puta koja funkcija ili procedura izvršava u programu i vreme trajanja prolazka kroz iste.
Za tu potrebu je dobro napraviti funkciju za merenje proteklog vremena kao i broja?e koliko puta je koja funkcija pozvana. Sve to treba zabeležiti u
jednu tekstualnu arhivu radi analize. Logicno je da je prva funkcija na redu za optimizaciju ona koja se izvršava najviše puta.
Funkcija za merenje proteklog vremena za Delphi 2-6:

function MiliSecondsElapsed(start: TDateTime): LongInt;
var
hour, min, sec, mSec: Word;
timeDifference: TDateTime;
begin
timeDifference := Now - start;
DecodeTime(timeDifference, hour, min, sec, mSec);
Result := mSec + ( sec * 1000 ) + (min * 60000) + (hour * 3600000) + (24 * 3600 * 1000 * Trunc(timeDifference));
end;

Kako meriti:

procedure NekaNasaProcedura;
var
Start:TDateTime;
mSec:LongInt;
begin
Start:=Now;
...
// kôd koji merimo
...
mSec:= MiliSecondsElapsed (Start);
// zapisati rezultat promenjljive mSec (milisekunde) u arhivu za dalju analizu
// ili je prikazati na ekranu
ShowMessage(Format('Proteklo je %d milisekundi',[mSec]));
end;

Sada znamo koliko traje da se data procedura izvrši i ve? imamo opštu sliku da li je to brzo ili sporo. Treba još to pomnožiti sa brojem
izvršavanja da bi se dobio kona?ni rezultat koliko zapravo traje celokupna operacija.


podnaslov:Uslovi

Postoje tri tipa uslovnih skokova: Bezuslovni (continue, break i goto), unapred uslovljeni (if, case i for) i unazad uslovljeni (while, repeat).
Prevodilac (compiler) prevodi unapred i unazad uslovljene u bezuslovne skokove koje predhodno mora da predvidi. Predvidjanje može biti stati?ko
i dinami?ko. Stati?ko predvidjanje je dosta sporo i odigrava se kada ni jedno predvidjanje nije ve? uradjeno. Dinami?ko predvidjanje koristi
"istoriju predvidjanja" i registruje samo promene, te je dosta brzze.
Pogledajmo loše i dobro napisane uslove i analizirajmo ih:

if (Radius > MaxRadius) then Exit;
if ((Radius < 50) and Filled) then NapraviMaliNapunjenKrug;
if ((Radius < 50) and (not filled)) then NapraviMaliPrazanKrug;
if ((Radius >= 50) and filled) then NapraviVelikiNapunjenKrug;
if ((Radius >= 50) and (not filled)) then NapraviVelikiPrazanKrug;

Iako sli?ni, ni jedan od uslova se ne ponavlja, te prevodilac mora svaki put da predvidja skokove. Svaki od uslova zahteva stati?ko predvidjanje
koje je jako sporo.
Pogledajmo optimizovani kôd:

if (Radius <= MaxRadius) then
begin
if (Radius <= 50) then
if Filled then NapraviMaliNapunjenKrug else NapraviMaliPrazanKrug
else
if Filled then NapraviVelikiNapunjenKrug else NapraviVelikiPrazanKrug;
end;

Prevodilac, u ovom slu?aju, prolazi kroz stati?ko predvidjanje samo na uslovu (Radius <= MaxRadius), dok za ostale uslove koristi dinami?ko
predvidjanje. Pretpostavka je da radius 99% krugova ne?e pre?i maksimalni dozvoljeni radius. Tada glavno razdvajanje se izvršava na osnovu
vrednosti radiusa, pa tek onda da li je krug ispunjen ili ne. Kao što vidimo, gornji algoritam proverava dva uslova ?etiri puta, dok se u drugom,
uslovi proveravaju 3 puta, samo po jednom.
Ovaj kôd je oko 60% brži od gornjeg, loše napisanog, kôda.

podnaslov:Keš (Cache)

Bilo koji Pentium procesor ima bar 16 KB internog keša. To je sva memorija koja se koristi za podatke i izvršavanje instrukcija. Ako naša funkcija
prelazi tu memoriju, ona mora biti, deo po deo, u?itana iz RAM memorije što je dosta spor proces u odnosu na izvršavanje iz samog keša. Ako
je naša funkcija dovoljno mala da može da se cela smesti u keš memoriju, bi?e izvršena neuporedivo brže od bilo koje koja mora da se u?ita
iz jednog ili više puta da bi se izvršila. Zbog toga je naro?ito bitno kod programiranja petlji, da svaka petlja bude dovoljno mala da može da se
smesti u keš u celosti. Imaju?i to u vidu, velike petlje, ako je mogu?e, treba razbiti u manje što ?e se direktno odraziti na brzinu izvršavanja.

podnaslov:Procedure i funkcije

Ako ste C++ programer, imate mogu?nost da male funkcije i procedure, koje se ne pozivaju ogroman broj puta definišete kao "inline" procedure.
Obi?ne procedure i funkcije zahtevaju "overhead" - malo vreme da pripreme promenljive i rezultate koje vra?aju pre nego što se predje na samo
izvršavanje. Ukoliko su male, "overhead" može biti ve?i od vremena izvršavanja. Tada treba koristiti "inline" opciju koja ce re?i prevodiocu da
postavi kôd funkcije u liniji sa pozivom funkcije što ?e eliminisati "overhead".
Ove funkcije generišu ve?i kôd jer se sam kôd kopira odakle god je zovemo, te ?e znatno usporiti rad ukoliko se pozivaju iz neke petlje.
Inline procedure i funkcije se definišu sa klju?nom re?i "inline":

inline int Negate(int IniValue)
{
return(-IniValue);
}

Mnoštvo lokalnih objekata i promenjlivih usporava rad. Hmm... ovo je malo odse?na izjava. Medjutim, istina je.
Svaki lokalni objekat mora da se konstruiše i uništi, što zahteva odredjeno vreme, a koje zavisi od kôda u njihovim konstruktorima i
destruktorima. Takodje, promenjljive moraju da imaju rezervisan prostor u memoriji da bi se njihove vrednosti upisivale i menjale.
Dobro obratite pažnju, neke promenljive u stvari, ni ne moraju da budu promenjljive ve? konstante. Optimizer prevodioca mnogo brže radi sa
konstantama nego promenjljivama jer ve? ima listu svih konstanti u programu, gde se definišu i gde se upotrebljavaju. To naro?ito dolazi do
izražaja kod parametara funkcija i procedura. Ukoliko ne naglasimo da je neka promenjljiva referencirana ili konstanta, prevodilac ?e morati da
napravi lokalnu kopiju, troše?i vreme i memoriju.
Pravljenje lokalne kopije oduzima više vremena nego definisanje lokalne promenjljive istog tipa.

Procedure NekaProcedura(Node:TTreeNode; Count:integer);
?e biti dosta sporija od procedure
Procedure NekaProcedura(const Node:TTreeNode;Count:integer);

Takodje ako imamo slu?aj:

function NekaFunkcija(AValue:integer):integer;
begin
result:=AValue + 10;
end;

?e biti mnogo sporija od referencirane procedure:

procedure NekaFunkcija( var AValue:integer);
begin
AValue:=AValue + 10;
end;


podnaslov: Indeksiranje

Obratite pažnju na slede?e procedure koje rade istu stvar:

procedure NekaProcedura;
var
i:integer;
begin
for i:=0 to PageControl.pageCount -1 do
begin
TMyRichEdit(PageControl.Pages[i].controls[0]).visible:=true;
if TMyRichEdit(PageControl.Pages[i].controls[0]).plainText = true then
TMyRichEdit(PageControl.Pages[i].controls[0]).PlainText:=false;
end;
end;

Procedure NekaProcedura;
var
i:integer;
Re:TMyRichEdit;
begin
for i:=0 to PageControl.pageCount - 1 do
begin
Re:=TMyRichEdit(PageControl.Pages[i].controls[0]);
re.visible:=true;
if re.plainText = true then re.plainText:=false;
end;
end;

Apsolutno ista stvar, s razlikom što druga ne?e svaki put da TypeCast-uje kontrolu ve? ?e to da uradi samo jednom i da radi sa pointerom iste
da bi namestila željene parametre. Isto se dogadja ukoliko imamo neki niz i dolazimo do željenog indeksa preko indeksa druge kontrole:
i:=LetterPos[Words[WordNum].Letters[LetterNum]].x;
Bolje je kreirati lokalnu promenjljivu koja ?e da sadrži indeksne brojeve i koristiti nju kao index jer dosta ubrzava operaciju.

Kod nizova, ukoliko imate dva niza kojima ne pristupate sinhrono, bolje je kreirati dva razli?ita niza kao sto je i uobi?ajeno, medjutim ukoliko im
pristupate sinhrono i simultano, bolje je kreirati Record (struct) sa ta dva niza kao ?lana jer zauzimaju isti memorijski prostor sa kojim prevodilac
brže radi.

TNiz=record
a,b : array [0..10] of Integer;
end;

Procedure NekaProcedura;
var
N:TNiz;
i:integer;
begin
N.a[0]:=100;
N.b[0]:=20;
for i:=1 to 10 do
begin
N.a[i]:=(i*60) div 50;
N.b[i]:=(i*30) div 20;
end;
end;


Podnaslov: ?ista logika

U ve?ini slu?ajeva, optimizacija se uspešno završava ?istom ljudskom logikom.
Imao sam slu?aj gde je trebalo izvršiti obra?une bruto i neto plata, poreza i ostalih finansijskih zavrzlama na dvadesetak lista pla?anja, ukupno
nešto vise od 300 zaposlenih. Ono što mi je odmah palo na pamet je napraviti 2 upita na bazi, jedan za liste, vrteti petlju i prosledjivati parametar
liste na drugi upit koji je davao zaposlene i njihove podatke. Opet petljica, upisati podatke i prora?un je zavrshen.
Sledilo je vrlo neprijatno iznenadjenje: gotovo 4 sekunde za 300 zaposlenih. Da li je mogu?e?
Od optimizacije prora?una sam odmah odustao, jer ma kakvi da su prora?uni, operacije sa brojevima su izuzetno brze. Gde onda? Upiti, naravno.
To je izgledalo ovako:

Procedure TSallaryProcess.CalculateSallaries;
const
SQL1='Select LVE_CdiLeave from Leaves';
SQL2='Select CON_CdiContractor,CON_VlnSallary,CON_VlnTax from Contractors Where CON_CdiLeave= :param';
Var
qry1,qry2,qry3:TRPCQuery;
Begin
qry1:=Create_QueryObject(Connection);
qry2:=Create_QueryObject(Connection);
qry3:=Create_QueryObject(Connection); //koristio sam za Update
try
qry1.sql.add(SQL1);
qry2.sql.add(SQL2);
qry1.open;
qry1.first;
while not qry1.EoF do
begin
qry2.params[0].asInteger:=qry1.fields[0].asInteger;
qry2.open;
// ovde proracuni
// ovde update sa qry3
qry2.close;
qry1.next;
end;
finally
DeleteQuery(qry1,connection);
DeleteQuery(qry1,connection);
DeleteQuery(qry1,connection);
end;
end;

Zna?i, otvarao sam tri Query objekta, otvorio jedan, prosledio parametar na drugi, otvorio ga, prora?unao, izvršio update na tre?em, zatvorio
drugi, prešao na slede?i zapis u prvom i sve iz po?etka.
Nikako nije dobro.
Zašto su mi uopste potrebna tri upita koja ?u da zatvaram i otvaram? Nisu potrebna.
Nakon razmišljanja, došao sam do slede?eg rešenja i smanjio vreme izvršavanja sa nešto više od 3800 milisekundi na skoro 400 milisekundi.
Ubrzanje od 9.5 puta me je zaprepastilo. O?ekivao sam duplo brže, ali ne 9 puta.
Tajna je u slede?em: Napravio sam jedan ogroman upit koji sadrži oba predhodna upita, zasnovano na ?injenici da je nalaženje zapisa mnogo
brže od otvaranja upita. Takodje, update nisam obavljao odmah po prora?unu vec ih skupio na gomilu pa izvršio od jednom.

Procedure TSallaryProcess.CalculateSallaries;
var
qry1,qry2:TRPCQuery;
list:TStringList;
arr:Array of Integer;
NextVal:boolean;
begin
qry1:=Create_QueryObject(Connection);
qry2:=Create_QueryObject(Connection);

list:=TStringList.Create;
try
qry1.sql.text:='Select LVE_CdiLeave from Leaves';
qry2.sql.text:='Select LVE_CdiLeave,CON_CdiContractor,CON_VlnSallary,CON_VlnTax from Leaves '+
'inner join Contractors on (CON_CdiLeave=LVE_CdiLeave) '+
'Order by LVE_CdiLeave,CON_CdiContractor';
qry1.open;
qry2.open;
qry1.first;
qry2.first;
while not qry1.Eof do
Begin
if qry2.locate('LVE_CdiLeave',qry1.fields[0].asInteger,[]) then
begin
While not NextVal do
begin
if qry2.fields[0].asInteger=qry1.fields[0].asInteger then
begin
//uzmi podatke i izvrsi proracun
//montiraj Update SQL
list.add(MontiranUpdateSQL);
end else NextVal:=true;
qry2.next;
end;
end;
NextVal:=false;
qry1.next;
end;
//izvrsi update odjednom
qry1.sql.clear;
qry1.sql.assign(list);
qry1.ExecSQL;
finally
DeleteQuery(qry1,Connection);
DeleteQuery(qry2,Connection);
FreeAndNil(list);
end;
end;