[es] - uporedjivanje koda

marko000
marko vucinic
Beograd

Član broj: 6501
Poruke: 63
*.verat.net

Profil

^{11.07.2003. u 17:32 - pre 252 meseci}

kako se vrsi analiza brzine izvrsavanja koda...naprimer imam programcic uradjen na dva razlicita nacina..kako da odredim koji brze radi..da li postoje programi za to..

je li to "optimizacija"?

koji se vazni elementi za brzinu koda...??
da li je brza rekurzija od poziva vise razlicitih funkcija?
da li postoji strucan naziv za ovakve vrste analiza i gde na netu mogu naci nesto o tome?

marko

Odgovor na temu

tweeester
Ivan Arandjelovic
bg yu

Član broj: 724
Poruke: 882
*.kc.vicert.com

Sajt: www.javasvet.net

Profil

Re: uporedjivanje koda

^{11.07.2003. u 17:35 - pre 252 meseci}

Pravi naziv za to sto tebi treba je "profiling" ili "code profiling" , uradi search na ovu rec pa ces vec naci gomilu stvari

<< tko leti vrijedi, tko ne leti ne vrijedi >>

Odgovor na temu

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*

+6 Profil

Re: uporedjivanje koda

^{11.07.2003. u 18:10 - pre 252 meseci}

tweester ti je dao pravi odgovor, a ja ću samo da dodam: nikad ništa nemoj da "analiziraš", nego uvek meri.

IOCC

Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl

Jabber: filmil@jabber.org
ICQ: 36601391

+3 Profil

Re: uporedjivanje koda

^{11.07.2003. u 18:22 - pre 252 meseci}

Tata, da li bi mogao da podrobnije objasniš ovo tvoje, da kažem, navijanje vode na praktičarsku vodenicu?

Analiza i te kako ima smisla ako treba da se vidi recimo koji je od dva algoritma složeniji. Ako se bira između dve implementacije koje se razlikuju u finesama (a to je ono što mora da se utvrdi merenjem jer metoda gledanja ne daje nikakve nove informacije), onda to obično nije vredno truda.

Hoću da kažem da sam zaključio upravo suprotno od tebe, pa me zanima zašto onda preporučuješ merenje naspram analize.

f

Odgovor na temu

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*

+6 Profil

Re: uporedjivanje koda

^{11.07.2003. u 19:44 - pre 252 meseci}

Iskustvo, Filipe, iskustvo. Analiza te skoro uvek navede na pogrešan zaključak, osim eventualno ako su u pitanju trivijalne stvari - npr neko koristi O(n) algoritam za nešto gde postoji i O(1). Profajliraj, blago meni, pa ćeš da saznaš koji deo koda je kočnica a onda je dalje lako.

IOCC

Odgovor na temu

milanche
San Francisco

Član broj: 2447
Poruke: 1200
*.oak.inreach.net

+1001 Profil

Re: uporedjivanje koda

^{12.07.2003. u 17:40 - pre 252 meseci}

Dragi Tata je potpuno u pravu sto kaze da prednost treba dati merenju, a ne analizi.

Vrlo cesto se desava da superiorni algoritmi na konkretnoj masini ne rade brze nego
neki obicni algoritmi.

Jedan od krupnih razloga je nesto sto se zove 'pipelining' - procesor skladisti unapred po vise narednih instrukcija, ocekujuci da ce one biti i izvrsene. Medjutim, u kodu koji ima previse kondicionalnih skokova (if), cesto dodje do toga da se 'pokvarilo mleko u frizideru, pa mora da se svaki cas skace do dragstora', tj. da uskladistene instrukcije moraju da se izbace te da se skace po programskoj memoriji po nove.

Rezultat - obicni algoritmi koji imaju zgodniji sklop if-ova nego neki mnogo pametniji algoritam ispadaju brzi, sto se nikada ne bi reklo, sudeci po analizi na papiru.

Odgovor na temu

leka
Dejan Lekić
senior software engineer, 3Developers
Ltd.
London, UK

Član broj: 234
Poruke: 2534
*.racasse.se

Sajt: dejan.lekic.org

+2 Profil

Re: uporedjivanje koda

^{18.07.2003. u 14:54 - pre 252 meseci}

U eri ultramodernih kompajlera sa ultramodernim optimizacijama takve stvari su svedene na minimum minimuma, tako da najbolji algoritmi uglavnom daju i najbolje rezultate...

Dejan Lekic
software engineer, MySQL/PgSQL DBA, sysadmin

Odgovor na temu

milanche
San Francisco

Član broj: 2447
Poruke: 1200
*.tivo.com

+1001 Profil

Re: uporedjivanje koda

^{20.07.2003. u 05:38 - pre 252 meseci}

Kad su u pitanju Intelovi procesori, to je uglavnom tacno - kod napisan levom nogom u MMX-u masina sama optimizuje tako da radi bas kao i ultra-trimovan program.

Kad su u pitanju manje popularni/vise specijalizovani cipovi, to itekako vazi. Poslednji primer:
firma Oak Technology koja pravi graficke akceleratore za printere prakticno je bacila u vodu mesece
rada na optimizovanom algoritmu za renderovanje fontova u korist proste, linearne metode, koja se ispostavilo radi priblizno isto brzo, uz manji code footprint.

Izvor informacije: VP of engineering, na intervjuu jednog mog priatelja.

Razlog: upravo to sto sam naveo - pipelining. Procesor je inace dobro dizajniran, u razumnom roku, da bi izasao na trziste i doneo pare koje treba, onda kad treba. Firme kao sto su Intel ciji budzet dozvoljava razvoj run-time optimizatora koda, ili Philips koji pravi 5-pipeline VLIW (very large instruction word) su sve vise retkost.

Odgovor na temu

leka
Dejan Lekić
senior software engineer, 3Developers
Ltd.
London, UK

Član broj: 234
Poruke: 2534
*.telia.com

Sajt: dejan.lekic.org

+2 Profil

Re: uporedjivanje koda

^{20.07.2003. u 12:45 - pre 252 meseci}

milance, bojim se da se nismo dobro razumeli - ja uopšte nigde nisam spomenuo "kod pisan levom rukom" već sam spomenuo "provereno dobre algoritme". Dakle da na primeru objasnim - ne postoji nikakav način da neki dokazano lošiji algoritmi za recimo sortiranje (bubble, insertion) budu brži (GENERALNO, nećemo da uzimamo specijalne slučajeve gde eventualno insertion može biti brži) od quick sort-a (ili eventualno merge-sorta, za neke posebne primene).
Živim u ubeđenju da ovo važi i za sve ostalo.
Kad sam govorio o optimizaciji, rekao sam "era inteligentnih kompajlera", dok ti u svom odgovoru pričaš o "Intelovim procesorima", mora da si hardveraš pa ti je to neka profesionalna deformacija :) . Kompajleri danas zaista jesu inteligentni i znaju da optimizuju kod veooooma dobro. Iz iskustva znam kakve rezultate daju Intel-ov C kompajler za x86 arhitekturu, SUN-ov C kompajler za SPARC i slično. Banalan primer, ali je dobar primer koji objašnjava ono što rekoh u prošlom tekstu.

Na kraju zaključak koji maltene svaki dobar programer zna - ukoliko se ne govori o specijalnim slučajevima gde eventualno neki slabi algoritmi mogu da "pobede" bolje, onda tvoja izjava "Vrlo cesto se desava da superiorni algoritmi na konkretnoj masini ne rade brze nego neki obicni algoritmi" uglavnom nije tačna. "Superiorni" algoritmi skoro UVEK rade brže.

Još nešto... - Jeste da se ja profesionalno ne bavim kompajlerima, ali znam da sam u nekim knjigama koje se bave teorijom dizajna modernih kompajlera video i deo gde se govori o famoznom pajplajning-u . Tako da je isti problem "poznat" današnjim kompajlerima i valjda (to ljudi koji se bave kompajerima) oni mogu sa time da izađu na kraj.

Dejan Lekic
software engineer, MySQL/PgSQL DBA, sysadmin

Odgovor na temu

milanche
San Francisco

Član broj: 2447
Poruke: 1200
*.oak.inreach.net

+1001 Profil

Re: uporedjivanje koda

^{21.07.2003. u 05:37 - pre 252 meseci}

Leko,

nisam hardveras odavno. Ipak, ne pripadam mainstream-u programera koji programe
pisu za komercijalno uigrane platforme (procesor + kompajler), kakvi su Intel-ovi, Sun-ovi i slicni procesori o kojima se godinama brinu najkvalitetniji timovi i razvijaju mnogo toga sto olaksava zivot programerima.

U tom okruzenju i u tom smislu, tvoja opaska zaista stoji - uz optimizovane kompajlere zaista dobri algoritmi tuku one obicnije, polazne algoritme. Intel je cak otisao korak dalje (primer koji sam licno susreo) - prvu (nabacanu, neoptimizovanu) verziju MMX koda, procesor at run-time optimizuje, tako da sve radi isto kao i kad se sedne pa se kod ispegla prema svim pravilima i preporukama.

U okruzenju u kojem najcesce radim (Silicijumska Dolina), firme krecu od nule, razvijaju svoje application-specific procesore sa glavnim ciljem da neki novi standard realizuju pre konkurencije i da nahvataju pocetnu kolicinu kesa. Sasvim regularna stvar koja mi se desavala vise puta je da posle vikenda provedenog jureci bag u mikrokodu otkrijem kompajler bag i da ga vec u ponedeljak ujutru prijavim tools grupi. U takvoj situaciji, u kojoj se zajedno razvija release kod a u isto vreme i kompajler, optimizacija kompajlera mu dodje kao visa matematika.

Uz tu predpostavku, nadam se da moja primedba deluje malo osnovanije.

Odgovor na temu

milanche
San Francisco

Član broj: 2447
Poruke: 1200
*.oak.inreach.net

+1001 Profil

Re: uporedjivanje koda

^{21.07.2003. u 09:28 - pre 252 meseci}

Zaboravih i ovo:

pametna pipelining podrska je gotovo 99% u hardveru. Za ultra pametno dizajniran
cip, (Intel X86, Philips TriMedia, Sun SPARC), pisac kompajlera ima sansu da nesto doda. Za ostale platforme, sve sto kompajler dizajner moze da uradi je da tu i tamo umetne 'nop' da bi izbegao 'race problem', i tu je prica gotova.

Posle toga, sve radi programer - izbegava if-ove i zamenjuje kondicionalne skokove tzv. proracunatim skokovima gde god je to moguce.

Odgovor na temu