Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Sta ce se brze izvrsiti?

[es] :: Art of Programming :: Sta ce se brze izvrsiti?

Strane: 1 2

[ Pregleda: 8404 | Odgovora: 26 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

fearless

Član broj: 74584
Poruke: 156
212.62.59.*

Sajt: www.phearless.org


Profil

icon Sta ce se brze izvrsiti?12.02.2006. u 23:14 - pre 220 meseci
Bas smo raspravljali na ircu

<h4z4rd> sta ce se brze izvest od obvoga dvoje
<h4z4rd> a=(b>c)?b:c;
<h4z4rd> ili
<h4z4rd> (b>c)?(a=b):(a=c);
<h4z4rd> bets????

Naravno, ja i oni koji su bili tamo prisutni znamo, a sta je vase misljenje (sa objasnjenjem naravno)?

P.S. Bez varanja, samo mozak


[Ovu poruku je menjao fearless dana 13.02.2006. u 00:17 GMT+1]
Phearless - Serbian/Croatian Security Magazine: www.phearless.org
 
Odgovor na temu

#Ninja#
Tuzla

Član broj: 28925
Poruke: 259
*.pppoe884.bih.net.ba.



+1 Profil

icon Re: Sta ce se brze izvrsiti?13.02.2006. u 12:12 - pre 220 meseci
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.
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: Sta ce se brze izvrsiti?15.02.2006. u 22:12 - pre 220 meseci
(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.
 
Odgovor na temu

fearless

Član broj: 74584
Poruke: 156
212.62.59.*

Sajt: www.phearless.org


Profil

icon Re: Sta ce se brze izvrsiti?19.02.2006. u 15:18 - pre 220 meseci
Da, obojica ste u pravu ;)

Ako neko ima nesto slicno neka postuje.
Phearless - Serbian/Croatian Security Magazine: www.phearless.org
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: Sta ce se brze izvrsiti?19.02.2006. u 16:03 - pre 220 meseci
Evo nesto o cemu smo pricali na jednom drugom forumu.
Code:
opcija A
for ( long i = 0 ; i < 1000000L ; i++ ) {
  for ( long j = 0; j < 1000000L ; j++ ) {
     a[ j ][ i ] = some_calculation();
  }
}

opcija B
for ( long i = 0 ; i < 1000000L ; i++ ) {
  for ( long j = 0; j < 1000000L ; j++ ) {
     a[ i ][ j ] = some_calculation();
  }
}

Dali ima razlike? Objasni.
 
Odgovor na temu

klichko

Član broj: 84010
Poruke: 55
..mtsns-ns.customer.sbb.co.yu.



+6 Profil

icon Re: Sta ce se brze izvrsiti?19.02.2006. u 20:11 - pre 220 meseci
Dobices nesto ovog oblika:
Code:

A:
1 6 ...
2 7 ...
3 8 ...
4 9 ...
5 10 ...
.  .
.  .
.  .

B:
1 2 3 4 5 ...
6 7 8 9 10 ...
.
.
.


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]

 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.navman.com.



+3 Profil

icon Re: Sta ce se brze izvrsiti?19.02.2006. u 21:20 - pre 220 meseci
Citat:
fearless: Bas smo raspravljali na ircu

<h4z4rd> sta ce se brze izvest od obvoga dvoje
<h4z4rd> a=(b>c)?b:c;
<h4z4rd> ili
<h4z4rd> (b>c)?(a=b):(a=c);
<h4z4rd> bets????

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

Citat:
Naravno, ja i oni koji su bili tamo prisutni znamo, a sta je vase misljenje (sa objasnjenjem naravno)?


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]
 
Odgovor na temu

klichko

Član broj: 84010
Poruke: 55
..mtsns-ns.customer.sbb.co.yu.



+6 Profil

icon Re: Sta ce se brze izvrsiti?19.02.2006. u 21:48 - pre 220 meseci
U pravu si nisam obratio paznju na naslov topica, inace slazem se sa obrazlozenjem.

 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: Sta ce se brze izvrsiti?20.02.2006. u 17:12 - pre 220 meseci
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 )?
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.navman.com.



+3 Profil

icon Re: Sta ce se brze izvrsiti?20.02.2006. u 21:06 - pre 220 meseci
Citat:
NrmMythNisam bas siguran da ce ti kompajler moci bas tako to optimizirati

Hoce, hoce, probano!

Citat:
jel odakle on zna da ti bas takav sporiji oblik nisi zelio?

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

Citat:
Sta ako u petljama ima jos nekih funkcija koje ovise o odredjenom izvrsavanju para ( i, j )?

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:
Code:
 for( i=0; i < N; i++ )
   for( j=0; j < N; j++ ) {
     C[i][j] = 0;
     for( k=0; k < N; k++ )
       C[i][j] += A[k][j] * B[i][k];
   }


kompajler pretvori u

Code:

 for( ii=0; ii < N; ii += ib )
   for( kk=0; kk < N; kk += kb )
     for( j=0; j < N; j+= 2 )
       for( i=ii; i < ii+ib; i += 2 ) {
         if( kk==0 )
           acc00 = acc01 = acc10 = acc11 = 0;
         else {
           acc00 = C[i+0][j+0];
           acc01 = C[i+0][j+1];
           acc10 = C[i+1][j+0];
           acc11 = C[i+1][j+1];
         }
         for( k=kk; k < kk+kb; k++ ) {
           acc00 += A[k][j+0] * B[i+0][k];
           acc01 += A[k][j+1] * B[i+0][k];
           acc10 += A[k][j+0] * B[i+1][k];
           acc11 += A[k][j+1] * B[i+1][k];
         }
         C[i+0][j+0] = acc00;
         C[i+0][j+1] = acc01;
         C[i+1][j+0] = acc10;
         C[i+1][j+1] = acc11;
       }

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]
 
Odgovor na temu

_owl_

Član broj: 318
Poruke: 1043
*.vdial.verat.net.



+3 Profil

icon Re: Sta ce se brze izvrsiti?20.02.2006. u 21:07 - pre 220 meseci
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??
Owl
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: Sta ce se brze izvrsiti?21.02.2006. u 14:08 - pre 220 meseci
Odlican link srki. Bas cu se pozabaviti tim tekstom kasnije.
 
Odgovor na temu

chupcko
Negde
Beograd

Član broj: 5560
Poruke: 1141

Sajt: www.google.com


+63 Profil

icon Re: Sta ce se brze izvrsiti?27.02.2006. u 11:52 - pre 220 meseci
Recimo kada ne bi bilo optimizacije, i sve se to prevelo striktno, kod bi licio na ovo:

a=b>c?b:c
Code:

   load b
   sub c
   ifgt l1
   load c
   goto l2
l1:
   load b
l2:
   store a


b>c?a=b:a=c
Code:

  load b
  sub c
  ifgt l1
  load b
  store a
  goto l2
l1:
  load c
  store a
l2:


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 ...

CHUPCKO
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.jetstream.xtra.co.nz.



+3 Profil

icon Re: Sta ce se brze izvrsiti?27.02.2006. u 12:11 - pre 220 meseci
Citat:
chupcko: Naravno kada se u igru umesaju optimizacije ...


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

Citat:
Mogu da kazem da ovako sagledano vreme izvrsavanja je isto (prodjite kroz slucajeve i brojite instrukcije :) ).

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]
 
Odgovor na temu

chupcko
Negde
Beograd

Član broj: 5560
Poruke: 1141

Sajt: www.google.com


+63 Profil

icon Re: Sta ce se brze izvrsiti?27.02.2006. u 12:46 - pre 220 meseci
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 :))).

CHUPCKO
 
Odgovor na temu

rivan
Ivan Radovanović

Član broj: 1901
Poruke: 71
*.smin.sezampro.yu.

ICQ: 212235650


Profil

icon Re: Sta ce se brze izvrsiti?27.02.2006. u 23:59 - pre 220 meseci
Prilicno neprecizno pitanje
Citat:

<h4z4rd> sta ce se brze izvest od obvoga dvoje
<h4z4rd> a=(b>c)?b:c;
<h4z4rd> ili
<h4z4rd> (b>c)?(a=b):(a=c);
<h4z4rd> bets????


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
 
Odgovor na temu

Mali Misha
Mihajlo Anđelković
NBGD

Član broj: 79396
Poruke: 379
*.powernet.bg.

ICQ: 195487525
Sajt: cpptea.com


+1 Profil

icon Re: Sta ce se brze izvrsiti?28.02.2006. u 19:09 - pre 220 meseci
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
Code:
    for (i = 0 ; i < 100 ; i++ ) {
        for (j = 0; j < 100 ; j++ ) {
            a[ i ][ j ] = 5;
        }
    }
i
    for (i = 0 ; i < 100 ; i++ ) {
        for (j = 0; j < 100 ; j++ ) {
            a[ j ][ i ] = 5;
        }
    }

bi bilo ekvivalentno poredjenju
Code:
    for (i = 0 ; i < 100 ; i++ ) {
        for (j = 0; j < 100 ; j++ ) {
            a[ i ][ j ] = 5;
        }
    }
i
    for (j = 0 ; j < 100 ; j++ ) {
        for (i = 0; i < 100 ; i++ ) {
            a[ i ][ j ] = 5;
        }
    }

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?
Ipak se ++uje.
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.jetstream.xtra.co.nz.



+3 Profil

icon Re: Sta ce se brze izvrsiti?28.02.2006. u 23:31 - pre 220 meseci
Citat:
Mali Misha
Konkretno kod mene je sporije radila druga petlja i to za 41%.

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.
 
Odgovor na temu

Časlav Ilić
Braunšvajg, Nemačka

Član broj: 4945
Poruke: 565
*.lstm.uni-erlangen.de.



+27 Profil

icon Re: Sta ce se brze izvrsiti?01.03.2006. u 13:38 - pre 220 meseci
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]
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.jetstream.xtra.co.nz.



+3 Profil

icon Re: Sta ce se brze izvrsiti?01.03.2006. u 14:48 - pre 220 meseci
Citat:
Časlav Ilić:Osnovno je da je u ovim posebnim slučajevima mašina poznata, a prvi prioritet je da se proračun izvršava brzo.


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:
Code:

 for( i=0; i < N; i++ )
   for( j=0; j < N; j++ )
     foo(A[i,j]);


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...

Citat:
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.

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.

Citat:
Š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.


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

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


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]
 
Odgovor na temu

[es] :: Art of Programming :: Sta ce se brze izvrsiti?

Strane: 1 2

[ Pregleda: 8404 | Odgovora: 26 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.