Mislim da će se brže izvršiti (b>c)?(a=b):(a=c); jer se odmah ide na provjeru uslova, a tek kasnije dodjela dolazi na red.

(b>c)?(a=b):(a=c);
I ja mislim da bi ovo trebalo ici brze jer je nekako linearnije.
Ali opet ovisi o tome kako to kompajler interpretira.

Da, obojica ste u pravu ;)

Ako neko ima nesto slicno neka postuje.

Evo nesto o cemu smo pricali na jednom drugom forumu.
Dali ima razlike? Objasni.

Dobices nesto ovog oblika:


U oba slucaja je u ptianju kvadratna matrica istih dimenzija, razlika je samo u mestu smestanja rezultata u tabeli, mislim da se to matematicki kaze da je B transponovana matrica od A (mrzi me sad da gledam neku knjigu iz matematike ), tj zamenjena su mesta vrsta i kolona.

_{[Ovu poruku je menjao klichko dana 19.02.2006. u 21:16 GMT+1]}

Zaivisi od: kompajlera, nivoa optimizacije (kod dobrog kompajlera nema razlike), procesora i vrednosti promenjivih b i c!



A kako ste merili brzinu ako nije tajna? 99% sam siguran da imate propust u metodi merenja.

@klichko
Nije poneta u tome, u jednom slucaju mozes da pozivas somecalculation(i,j) a u drugom somecalculation(j,i) ili mozda ti someclalculation uvek vraca 1. Uopste nije poenta u tome nego se pitanje odnosi na brzinu izvrsavanja. Brze ce se izvrsiti druga petlja jer necemo u svakom prolazu pristupati novom bloku memorije tako da kada pristupimo jednom bloku taj blok ce biti u kesu pa cemo slececi put brze pristupiti.

Naravno u danasnje vreme je gubljenje vremena obracati paznju na takve stvari jer ce kompajler sam to da optimizuje mnogo bolje nego vi sami jer on zna kolika je velicina memorijskog bloka itd...

_{[Ovu poruku je menjao srki dana 19.02.2006. u 23:33 GMT+1]}

U pravu si nisam obratio paznju na naslov topica, inace slazem se sa obrazlozenjem.

Tocno srki! Nisam bas siguran da ce ti kompajler moci bas tako to optimizirati, jel odakle on zna da ti bas takav sporiji oblik nisi zelio? Sta ako u petljama ima jos nekih funkcija koje ovise o odredjenom izvrsavanju para ( i, j )?

Hoce, hoce, probano!


Iskljucis optimizaciju. Mozes i da koristis kompajlerske direktive samo za taj deo koda.


Kompajler ce to da vidi a ako ne moze da vidi onda nece optimizovati. Inace kompajler to ne optimizuje na taj nacin vec mnoogo kompalikovanije:

http://en.wikipedia.org/wiki/Loop_nest_optimization

Npr. mnozenje matrica:


kompajler pretvori u


Da li bi to umeo da uradis bez nekog razmisljanja? Tesko. Ako sam pokusas da optimizujes samo mozes da otezas kompajleru. Kompajler vodi racuna o velicini L1 kesa, L2 kesa, velicini memorijskih blokova, broju i duzini pipeline-a, vrsti procesora itd...Nema sanse da ti to sve uzmes u obzir. Tako su npr. koristili jednu rucno optimizovanu petlju na penijumu 4 na 2800 Mhz i tu je radila sporije nego na originalnom racunaru za koji je napravljena petlja a taj racunar radi na 133 Mhz!!! Posle kada su napisali sasvim obicnu petlju bez rucnih optimizacija na pentijumu je radila mnogo brze!

U 21. veku obracati paznju na memory management i optimizacije na nivou procesora je cista ludost osim ako se ne bavite razvojem kompajlera.

_{[Ovu poruku je menjao srki dana 20.02.2006. u 22:35 GMT+1]}

Sumnjam da se kompajler zanima za lepe zelje programera. Ako se ukljuci odredjeni nivo optimizacije sledice se algoritam za koji se ocekuje da ce proizvesti najefikasniji kod.
Bas me zanima koja je poenta cele ove teme, istrazivanje mogucnosti za neke race condition-e ili sta??

Odlican link srki. Bas cu se pozabaviti tim tekstom kasnije.

Recimo kada ne bi bilo optimizacije, i sve se to prevelo striktno, kod bi licio na ovo:

a=b>c?b:c


b>c?a=b:a=c


Mogu da kazem da ovako sagledano vreme izvrsavanja je isto (prodjite kroz slucajeve i brojite instrukcije :) ). A definitno se vidi da je prvi slucaj "krace" kodiran. Sta je citljivije, e to je pitanje i sta vise opisuje sta je zamisljeno, e to je pitanje.

Naravno kada se u igru umesaju optimizacije ...

Nemaju veze samo optimizacije vec imaju veze cak i vrednosti b i c.


Nije bas tako jednostavno, brzina izvrsavanja koda se ne meri brojem instrukcija (pa makar i sve instrukcije isto trajale) vec malo komplikovanije zbog pipeline-a. Npr. neka je u procesoru najobicniji pipeline kada krene da se ucitava instrukcija ifgt procesor nece znati da li da sledecu instukciju ucita onu koja ide po redu posle ili ona gde ce mozda da skoci i onda ako recimo ucita sledecu po redu a prilikom dekodovanja prethodne instukcije je ispalo je da je b<c onda ce tu da izgubi jedan ili vise ciklusa. Da je bilo b>c onda ne bi izgubio nijedan ciklus. Naravno kada se tu jos uvedu i paralelni pileline-ovi onda je maltene nemoguce oceniti sta bi bilo brzo i to zavisi od procesora (pod pretpostavkom da nema optimizacije i da svi kompajleri prave isti kod).

Jos jednom da ponovim da u danasnje vreme je jako losa praksa rucno optimizovati ono sto ce kompajler bolje da odradi. Treba pisati da kod bude sto razumljiviji a posle vrsiti merenja i gledati gde je usko grlo.

_{[Ovu poruku je menjao srki dana 27.02.2006. u 13:16 GMT+1]}

Ako pipelin za trenutak naovemo optimizacijom na procesoru onda ne gubimo mnogo :).

Naravno da zavisi od vrednosti b i c, mada je za oba slucaja i kada je b > c i kada nije isti broj instrukcija i iste su, cak i u istom redosledu.

Ja sam za referencu uzeo neki imaginarni 8 bitni procesor, kod kojeg ne postoji pipeline i koji je reicmo riscolik, jel hoces konkretno recimo za pic18f452 sa kojim se igram ovih dana :).

Mislim jedino se mozemo sloziti oko toga da programer ako vec pise u c=u napise kod, a kako ce se on optimizovati ....

Ali ajde da okrenemo na smeh, ja bi uvek koristio a=b>c?b:c jer ima manje slova u sourcetu :), manje kucas, manje prostora zauzima :).

Evo sada cu da se naljutim i gledam kako gcc to radi :))).

Prilicno neprecizno pitanje


Nigde ne pise na nije u pitanju C++ i da a, b i c nisu primerci neke klase sa zgodno definisanim operatorima...
Bilo sta od ta dva moze da bude brze

Ok, sada cu verovatno da zaradim drvlje i kamenje.

(b>c)?(a=b):(a=c); se na mom sistemu sa mojim kompajlerom pokazao za 77% neefikasnijeg od a=(b>c)?b:c;. Nisam primetio zavisnost potrebnog vremena i vrednosti b i c.

Poredjenje

bi bilo ekvivalentno poredjenju

Konkretno kod mene je sporije radila druga petlja i to za 41%.

Efikasnost sam utvrdjivao merenjem vremena potrebnog za odredjen broj izvrsavanja zadatih segmenata koda, pomocu SYSTEMTIME. Misljenja o metodi? Preporuke?

A sada probaj da povecas vrednost maksimalnu vrednost j na 100 000 ili milion a maksimalna vrednost promenjive i neka ti bude recimo 10 i onda startuj test i reci rezultate. Naravno iskljuci optimizaciju.

Srki je u globalu u pravu kad kaže da ovakve optimizacije treba prepustiti kompilatoru, ali postoje i specifične oblasti gde to baš ne važi. Npr., kada se pišu numerički intenzivni programi uske i kratkotrajne namene, često, mada ne obavezno, za izvršavanje na superračunarima.

Osnovno je da je u ovim posebnim slučajevima mašina poznata, a prvi prioritet je da se proračun izvršava brzo. Ako je proračun iole komplikovaniji od množenja vektor-vektor, matrica-vektor, matrica-matrica, i sličnih primitivnih operacija, šanse kompilatora da optimizuje kôd znatno se smanjuju.

Štaviše, da bi se kôd značajno ubrzao, često nije potrebno previše pametovati, već se samo držati nekih opštih vodilja i ne činiti gluposti. Baš smo prošlog semestra imali jedan predmet, gde je trebalo implementirati nekakav proračun, bez posebnog osvrtanja na brzinu. Pošto su nam bile pune ruke posla, nisam imao vremena da mnogo razmišljam o optimizaciji, samo sam primenjivao pomenute opšte vodilje. Rezultati su bili, barem meni, iznenađujući:

http://www10.informatik.uni-er...SS2005/NuSiF/performance.shtml

(Iako ne baš u vezi sa ovom pričom, posebno je zabavno da je na Intelovom procesoru GCC istukao Intelov kompilator :)

Jedna fina knjiga o optimizacijama ovog tipa, koju smo koristili u jednom drugom predmetu koji se baš i bavio time, jeste: „Performance Optimization of Numerically Intensive Codes“ - Goedecker, Hoisie. Nažalost, nešto ne vidim da je lako dostupna, čak ni na, kh, p2p, kh...

_{[Ovu poruku je menjao Časlav Ilić dana 01.03.2006. u 14:39 GMT+1]}

U tom slucaju si u pravu. Ako se pravi kod koji ce raditi i na buducim masinama onda ne treba skoro nista rucno optimizovati jer ne mozemo znati da li ce buduca masina imati duplo veci ili triput veci kes, da li ce imati istu duzinu pajplajna itd...

Inace za optimizaciju i na poznatoj arhitekturi mislim da je bitnije da se sto vise poznaje nacin na koji kompajler radi. Recimo pogledajmo ovaj jednostavan kod:


Ako je u tom fajlu funkcija foo samo deklarisana onda on ne moze znati da li izvrsavanje te funkcije zavisi od prethodnog izvrsavanja pa zbog toga nece zameniti vrednosti i i j u for petljama. Ali ako mi to znamo i vidimo da je to bottle neck onda mozemo da forsiramo inline i kompajler ce zbog toga da optimizuje sta treba. Znaci nije samo ubrzanje zbog inline nego se vrse i druge optimizacije zbog toga.

Drugi primer: zamislimo da neka funkcija prima pointer na neki objekat neke klase (tj. prima referencu) ali da ta funkcija ne menja objekat vec samo cita neke vrednosti Ako mi onda u glavnom kodu procitamo neku vrednost iz objekta pa pozovemo funkciju nad pointerom na taj objekat i posle poziva ponovo procitamo istu vrednost kompajler nece znati da li je nasa funkcija menjala vrednost objekta pa ce dvaput da cita istu vrednost iz objekta. Ali ako mi to znamo da kompajler zbog toga nece moci da optimizuje onda samo treba promeniti deklaraciju funkcije tako da umesto da joj parametar bude pokazivac na objekat neke klase onda ima kao parametar pokazivac na konstantni objekat neke klase. Samo ubacivanje jedne reci 'const' ce mnooogo da pomogne kompajleru da optimizuje ostatak koda...


To se cesto desava zato sto kod komplikovanog koda ljudi ne vode racuna o tome zasto kompajler nesto ne bi mogao da optimizuje...Naravno kompajler nikada nece moci da optimizuje neki eksponencijalni algoritam u polinomijalni iako ljudi to mogu u nekim slucajevima.



Slazem se! Jako je bitno poznavati nacine na koji kompajler nesto optimizuje da mu nebismo odmogli.



Bilo bi zanimljivo pronaci razloge za to jer ako znamo razloge mozda bismo sitnom promenom koda mogli da nateramo jedan kompajler da optimizuje bolje.

_{[Ovu poruku je menjao srki dana 01.03.2006. u 15:50 GMT+1]}

Koristim pravo na repliku. :)


Zasto? Prilicno sam siguran da to nece promeniti rezultat u korist druge petlje, jer je pred svakom od navedenih petlji stojala jos jedna sa k od 0 do 20000. Optimizacija je bila vec iskljucena jer je razlika nakon optimizacije stvarno neprimetna, ako je uopste ima...

Da, nisam lepo procitao, ucinilo mi se da si rekao da je prva petlja radila sporije.
Pokazi nam i nacine na koji si merio efikasnosti (b>c)?(a=b):(a=c) i a=(b>c)?b:c. Da li si stavio u neku petlju u kojoj si alternativno menjao vrednosti b i c tako da je u jednom slucaju b<c a u drugom b>c ? To je jako bitno jer procesor pamti gde je bio skok pa ce da pretpostavi da ce i sledeci put biti isti skok kada ponovo izvrsava tu instrukciju.

_{[Ovu poruku je menjao srki dana 01.03.2006. u 16:30 GMT+1]}

Ne, nisam uopste pokusavao da napravim realnu situaciju. Samo sam bio pustio dugacku petlju sa datim kodom. Kod je zakacen za post.

_{[Ovu poruku je menjao Mali Misha dana 01.03.2006. u 17:00 GMT+1]}

Moje iskustvo je da kompilator (čak ni Intelov) neće pokušati da optimalno iskoristi keš, kao što je učinjeno u onom primeru množenja matrica koji si naveo u jednoj od prethodnih poruka. Razmeniće petlje, odmotati ih i preurediti jezgro da bi što bolje iskoristio fP jedinice i njihove cevovode, ali neće umetnuti dodatne petlje radi boljeg iskorišćenja podataka u kešu.


Moje lično zapažanje je da je Intelov kompilator nekako jogunast, da GCC daje robusnije rezultate preko svega. Posebno sam uočio da Intel voli statički rezervisanu memoriju, umevao je da bude i dvostruko brži nego ako je memorija dinamički rezervisana. U jednom primeru Intel sa statičkom rezervacijom bio je ~15% brži od GCCa, a sa dinamičkom ~25% sporiji (GCC baš briga za način rezervacije). Možda je isto to došlo do izražaja i u gorepomenutom merenju performansi, ali nisam imao živaca da svrćem kôd na statičko rezervisanje.

Ideja za neki vudu-ples da bi se Intelov kompilator umilio da radi pošteno sa dinamičkom rezervacijom?

Da sam znao da ce ovako daleko otici... :)

Mozda koristi neki svoj memorijski alokator koji je spor za objekte te velicine koje si ti koristio. Neki alokatori su u nekim slucajevima dobri a u nekima losi. Npr. kada se zahteva veliki broj alokacija za objekte male (fiksne!) velichine onda je dobro koristiti boost::pool alokator:
http://www.boost.org/libs/pool/doc/index.html

Pisano je malo o alokatorima ovde:
http://www.elitesecurity.org/t...Boost-Pool-memorijski-alokator

gde ima link i ka ovoj temi:
http://www.codeproject.com/cpp/allocator.asp

Ako je zaista rad sa dinamickom memorijom boljka Intelovog kompajlera opet nije lose ako to znamo jer to onda mozemo i da promenimo. Slicno tome i za funkcije clanice koje ne menjaju sadrzaj objektra treba koristiti kljucnu rec const jer tako zaista mnogo mozemo da pomognemo kompajleru da optimizuje neke najobicnije petlje jer samo zbog te jedne kljucne reci on ce znati da funkcija ne menja objekat pa moze da pozove funciju i nekim drugacijim redosledom. Verujem da rucnim optimizacijama moze dosta stvari da se poboljsa ali bolje je taj trud uloziti na pisanje koda koji godi kompajleru jer na taj nacin isto mozemo da optimizujemo stvari uz cistiji kod a optimizacije ce raditi na bilo kom procesoru. Sve je stvar procene da li npr. platiti $50000 programeru (programerima) da potrose mesece rada na optimizovanju nekog koda za neki super racunar ili tih 50000 potrositi na unapredjivanje tig racunara sa brzim procesorima. Za takve stvari je najbolje pitati nekog operativnog menadzera jer su neki programeri dosta sujetni i vole da prckaju tamo gde postoji i jednostavniji nacin da se rese stvari. Menadzer moze da pogleda procenu vodje projekta o vremenu potrebnom za optimizaciju i onda da odluci sta da radi. I naravno pre bilo kakve optimizacije treba izvrsiti merenja i videti gde je bottleneck. Npr. ako imamo neki program koji cita gomilu podataka sa diska i obradjuje i stampa rezultate onda je gubljenje vremena optimizovati obradu podataka ako se ta obrada ionako brze izvrsava od citanja tih podataka sa diska. Merenjem mozemo videti sta najvise usporava program i onda dalje mozemo videti sta da radimo.

_{[Ovu poruku je menjao srki dana 03.03.2006. u 15:35 GMT+1]}

za specificne slucajeve (SMP okruzenje), korisno je pogledati i sledece alokatore:

http://www.hoard.org/
http://www.microquill.com/

alokatori su univerzum za sebe...