www.elektronik.si Seznam forumov www.elektronik.si
Forum o elektrotehniki in računalništvu
 
 PomočPomoč  IščiIšči  Seznam članovSeznam članov  SkupineSkupine  StatisticsStatistika  AlbumAlbum  DatotekeFilemanager DokumentacijaDocDB LinksPovezave   Registriraj seRegistriraj se 
  PravilaPravila  LinksBolha  PriponkePriponke  KoledarKoledar  ZapiskiZapiski Tvoj profilTvoj profil Prijava za pregled zasebnih sporočilPrijava za pregled zasebnih sporočil PrijavaPrijava 

Optimizacija algoritma / zanke
Pojdi na stran 1, 2, 3  Naslednja
 
Objavi novo temo   Odgovori na to temo   Printer-friendly version    www.elektronik.si Seznam forumov -> Programiranje embedded sistemov
Poglej prejšnjo temo :: Poglej naslednjo temo  
Avtor Sporočilo
alessio
Član
Član



Pridružen-a: Pon 04 Dec 2006 8:39
Prispevkov: 363
Aktiv.: 1.61
Kraj: Ljubljana

PrispevekObjavljeno: Pon Okt 27, 2008 10:47 pm    Naslov sporočila:  Optimizacija algoritma / zanke Odgovori s citatom

Testiram neke DSP algoritme za ARM MCU-je. Težavo imam pri razumevanju optimizatorja prevajalnika.
Problem lahko prikažem z naslednjim primerom, ki je namenoma zelo poenostavljen:

Koda:
int mult_int(int a, int b);

int main(void)
{
   int i;

   int volatile c;

   for(i = 0; i < 9999; i++)
   {
      c = mult_int(i, 10);
   }

   return 1;
}


int mult_int(int a, int b)
{
   return a * b;
}


Brez vklopljene optimizacije je vse tako kot pričakujem. Pri vklopljeni optimizaciji pa mi tako realview kot tudi arm-gcc prevajalnik odstranita for zanko.

Ima kdo idejo zakaj je temu tako?
Nazaj na vrh
Skrit Poglej uporabnikov profil Pošlji zasebno sporočilo
Glitch
Član
Član



Pridružen-a: Pet 07 Apr 2006 11:40
Prispevkov: 1477
Aktiv.: 6.32

PrispevekObjavljeno: Tor Okt 28, 2008 12:03 am    Naslov sporočila:   Odgovori s citatom

Ampak izracun za c je pa vseeno pustil? Ce je to res, je zato, ker je pogruntal, da je le zadnji rezultat relevanten in prav ima.

Ponavadi je volatile spremenljivka, ki je neposredno povezana z zanko in to je i. Poskusi dodati volatile pred i.

_________________
Answers: $1, Short: $5, Correct: $25, dumb looks are still free.
Nazaj na vrh
Skrit Poglej uporabnikov profil Pošlji zasebno sporočilo Pošlji E-sporočilo
Glitch
Član
Član



Pridružen-a: Pet 07 Apr 2006 11:40
Prispevkov: 1477
Aktiv.: 6.32

PrispevekObjavljeno: Pet Okt 31, 2008 5:29 pm    Naslov sporočila:   Odgovori s citatom

Ali si poskusil rešiti težavo?
_________________
Answers: $1, Short: $5, Correct: $25, dumb looks are still free.
Nazaj na vrh
Skrit Poglej uporabnikov profil Pošlji zasebno sporočilo Pošlji E-sporočilo
gregoral
Član
Član



Pridružen-a: Pet 24 Nov 2006 9:42
Prispevkov: 688
Aktiv.: 3.04
Kraj: Ljubljana

PrispevekObjavljeno: Tor Avg 11, 2009 3:18 pm    Naslov sporočila:  Volatile Odgovori s citatom

Sicer sem pri odgovoru zeeelo pozen, ampak vseeno.

Dodal bi komentar glede namembnosti ključne besede volatile.

Le ta pove prevajalniku, da lahko vrednost ki se nahaja v njej spremeni "zunanji" dejavnik. Kar je lahko interrupt rutina, lahko DMA prenos, če imamo pa več "procesov", pa tudi drug proces.

V primeru:
Koda:
   for(...)
   {
      c = mult_int(i, 10);
   }

se spremenljivki c samo prireja vrednost, torej pri izvajanju ni pomembno kakšna vrednost je v c preden se izvede mult_int.

Če pa bi imeli:
Koda:
   for(...)
   {
      c = mult_int(c, 10);
   }

je pa zelo pomembno dejstvo ali je c volatile, saj se med dvema klicema mult_int vrednost c lahko spremeni (interrupt recimo).

Volatile je torej navodilo prevajalniku, da med izvajanjem zanke ne sme imeti začasne vrednosti c kar v registru procesorja, ki bi jo na koncu zanke (ali funkcije) zapisal nazaj na pravo lokacijo v pomnilnik.

Zakaj prevajalnik začasno shranjuje vrednosti v registrih?
Prevajalniki upoštevajo dejstvo, da je dostop do "pomnilnika" vedno precej počasnejši kot dostop do registra, zato zelo radi začasno shranjujejo vrednosti v registrih, nato pa jih zapišejo nazaj v pomnilnik.

Prevajalnik namreč ne ve kakšen tip pomnilnika se nahaja na določenem naslovu. Tam je lahko ram, eprom, flash, ali pa register kake druge naprave.
Pri prevajanju torej ni znano kolilko ciklov (časa) bo trajal dostop do lokacije v "pomnilniku", znano je le da bo dostop trajal dlje, kot če bi imeli vrednost začasno kar v registru.

@Glitch:
Citiram:
Ponavadi je volatile spremenljivka, ki je neposredno povezana z zanko in to je i. Poskusi dodati volatile pred i.

Ni ravno priporočljivo, da bi se vrednost i, ki je začasen števec v zanki spreminjala z zunanjimi vplivi. Saj recimo interrupt rutina ne more vedeti, kdaj se izvaja točno ta del kode.

LP,
Gregor


Nazadnje urejal/a gregoral Tor Avg 11, 2009 9:13 pm; skupaj popravljeno 1 krat
Nazaj na vrh
Odsoten Poglej uporabnikov profil Pošlji zasebno sporočilo
alessio
Član
Član



Pridružen-a: Pon 04 Dec 2006 8:39
Prispevkov: 363
Aktiv.: 1.61
Kraj: Ljubljana

PrispevekObjavljeno: Tor Avg 11, 2009 4:29 pm    Naslov sporočila:  Re: Volatile Odgovori s citatom

gregoral je napisal/a:
Sicer sem pri odgovoru zeeelo pozen, ampak vseeno.

Hvala za tvoje misli, vsekakor bolje pozno kot nikoli... Wink

gregoral je napisal/a:

Dodal bi komentar glede namembnosti ključne besede volatile.

Le ta pove prevajalniku, da lahko vrednost ki se nahaja v njej spremeni "zunanji" dejavnik. Kar je lahko interrupt rutina, lahko DMA prenos, če imamo pa več "procesov", pa tudi drug proces.

OK, se strinjam. Poleg tega se volatile sploh v embedded svetu tudi uporablja
za manipulacijo HW registrov MCU-ja.

Recimo, tipičen primer definicije HW registra v include datotekah je nakaj v tem smislu:
Koda:

#define IOPIN          (*((volatile unsigned long *) 0xE0028000))


Citiram:

V primeru:
Koda:
   for(...)
   {
      c = mult_int(i, 10);
   }

se spremenljivki c samo prireja vrednost, torej pri izvajanju ni pomembno kakšna vrednost je v c preden se izvede mult_int.


Je pa pomembno dejstvo, da je c definiran kot volatile.
Če si predstavljaš, da bi bil to lahko data register od recimo UART periferije,
in bi rad dejansko vpisal izračunane vrednosti v ta register, potem si v težavah, če ti prevajalnik eliminira for zanko... Spremenljivka c je nekje v RAM-u,
prav tako pa je v bistvu HW register MCU-ja nekje v RAM-u. Vsaj kar se prevajalnika tiče...

Zanimivo in hkrati presunljivo je branje naslednjega dokumenta na to temo:
Volatiles are miscompiled...
Sicer je potrebno kakšno trditev vzeti z rezervo, vsekakor pa človek postane
mnogo bolj previden o pravilnosti prevajalnika!

Aja, drugač pa mi še vedno ni jasno zakaj mi prevajalnik eliminira tisto for zanko. Confused

~Aleš

_________________
Question is more important than the answer.(Plato)
Nazaj na vrh
Skrit Poglej uporabnikov profil Pošlji zasebno sporočilo
Sokrat
Član
Član



Pridružen-a: Čet 25 Avg 2005 11:00
Prispevkov: 5584
Aktiv.: 23.57

PrispevekObjavljeno: Tor Avg 11, 2009 5:07 pm    Naslov sporočila:  Re: Volatile Odgovori s citatom

alessio je napisal/a:
Aja, drugač pa mi še vedno ni jasno zakaj mi prevajalnik eliminira tisto for zanko. Confused


Hoces reci, da jo se vedno odoptimizira stran potem, ko si dodal volatile direktivo za i ?

_________________
Ka ti bo pa torba ce si kupu kolo ?
Nazaj na vrh
Skrit Poglej uporabnikov profil Pošlji zasebno sporočilo
Glitch
Član
Član



Pridružen-a: Pet 07 Apr 2006 11:40
Prispevkov: 1477
Aktiv.: 6.32

PrispevekObjavljeno: Tor Avg 11, 2009 5:46 pm    Naslov sporočila:   Odgovori s citatom

Jahm... ni videti, da bi probal dati i kot volatile.

Torej, si dal i volatile, ki je neposredno povezan z zanko?

_________________
Answers: $1, Short: $5, Correct: $25, dumb looks are still free.
Nazaj na vrh
Skrit Poglej uporabnikov profil Pošlji zasebno sporočilo Pošlji E-sporočilo
alessio
Član
Član



Pridružen-a: Pon 04 Dec 2006 8:39
Prispevkov: 363
Aktiv.: 1.61
Kraj: Ljubljana

PrispevekObjavljeno: Tor Avg 11, 2009 7:52 pm    Naslov sporočila:   Odgovori s citatom

Glitch, sorry, sem ti pozabil odgovorit oz. spregledal takrat tvoj reply.

Ja, sem deklariral i tudi kot volatile. Optimizacija level 2 pa je še vedno
preskočila funkcijo mult_int, je pa 10000x inkrementirala i.

Sicer, ah, silly me...
Sedaj po skoraj enem letu sem takoj našel razlog za "nepravilno" prevajanje.
Prevajalnik je dejansko dovolj pameten in uvidi, da je int volatile c na stacku
in je tako dejansko hudo trapasto pisat vanj nekaj, kar ni nikjer uporabljeno.
Se pravi, bistveno je to, da je c na stacku!

Če int volatile c prestavimo ven iz funkcije in tako postane globalna spremenljivka,
potem pa že ima pomen refreshat njegovo vrednost. In to prevajalnik tudi preverjeno
prevede in predvidi klic funkcije mult_int in vpiše novo vrednost v c.

Gregor, Glitch, Sokrat, hvala za spodbudo. Another mistery solved. Dancing

~Aleš

_________________
Question is more important than the answer.(Plato)
Nazaj na vrh
Skrit Poglej uporabnikov profil Pošlji zasebno sporočilo
Sokrat
Član
Član



Pridružen-a: Čet 25 Avg 2005 11:00
Prispevkov: 5584
Aktiv.: 23.57

PrispevekObjavljeno: Tor Avg 11, 2009 8:01 pm    Naslov sporočila:   Odgovori s citatom

Ja, samo to je pa res napacno delovanje, kakrsno je opisano v tistem clanku. Ce je i volatile, bi moral v vsaki iteraciji for zanke prebrati vrednost i, saj je od nje odvisna vrednost mult_int(), od vrednosti te pa rezultat c. Ce bi torej i prevajalnik pravilno obravnaval, potem ne bi smelo priti do napake, ki jo ti vidis.

Zgolj iz radovednosti: kateri predvajalnik (ce je gcc, katera verzija ?) pa uporabljas ? Zanimivo bi bilo videti, ce je korelacija med tezavami iz clanka in tvojim problemom zaradi verzije prevajalnika.

_________________
Ka ti bo pa torba ce si kupu kolo ?
Nazaj na vrh
Skrit Poglej uporabnikov profil Pošlji zasebno sporočilo
alessio
Član
Član



Pridružen-a: Pon 04 Dec 2006 8:39
Prispevkov: 363
Aktiv.: 1.61
Kraj: Ljubljana

PrispevekObjavljeno: Tor Avg 11, 2009 8:20 pm    Naslov sporočila:   Odgovori s citatom

Sokrat, ne temo tistega članka je bila pred časom vroča razprava
na comp.arch.embedded. Nekatere eminence so članek hladnokrvno raztrgale.
Kot sem rekel, kakšno reč je potrebno vzeti z rezervo, je pa vsekakor zelo interesantno branje.

Sedaj ko razmišljam o tistem mojem izmišljenemu primeru,
se mi zdi logično, da je prevajalnik pri optimizaciji prevedel kodo,
tako kot jo je. Je pa dejansko vprašanje, če se je delal mal preveč "pametnega".
Bi se res moral poglobit in naštudirat sequence pointe in C standard...

Sicer pa sem danes prevajal z Keil-om 3.40.

Sledeči program
Koda:

int mult_int(int a, int b);


int main(void)
{
   int volatile i;

   int volatile c;

   for(i = 0; i < 9999; i++)
   {
      c = mult_int(i, 10);
   }

   for(;;)
      ;

   return 1;
}

int mult_int(int a, int b)
{
   return a * b;
}


je z optimizacijo "level 2" in "optimize for speed" preveden v sledeče,
pripet samo relevantni del okoli for zanke:

Koda:

     9:    for(i = 0; i < 9999; i++)
    10:    {
    11:       c = mult_int(i, 10);
    12:    }
    13: 
0x000001BC  E3A0100F  MOV       R1,#0x0000000F
0x000001C0  E3A00000  MOV       R0,#0x00000000
0x000001C4  E2811C27  ADD       R1,R1,#0x00002700
0x000001C8  E2800001  ADD       R0,R0,#0x00000001
0x000001CC  E1500001  CMP       R0,R1
0x000001D0  BAFFFFFC  BLT       0x000001C8
    14:    for(;;)
0x000001D4  EAFFFFFE  B         0x000001D4


Jasno se vidi, da funkcija mult_int ni klicana in c ni refresh-an.
Je pa 10000x inkrementiran i. Wink

_________________
Question is more important than the answer.(Plato)
Nazaj na vrh
Skrit Poglej uporabnikov profil Pošlji zasebno sporočilo
alessio
Član
Član



Pridružen-a: Pon 04 Dec 2006 8:39
Prispevkov: 363
Aktiv.: 1.61
Kraj: Ljubljana

PrispevekObjavljeno: Tor Avg 11, 2009 8:26 pm    Naslov sporočila:   Odgovori s citatom

Keil v 3.40 pri optimizaciji level 2 in 3 ne kliče funkcije in prireja vrednosti c-ju.
Level 0 in 1 pa ja. Enaka zgodba je z the latest and greatest v. 3.70 (ARM-ov C compiler 4.0.0.524).

Z GCC-jem sem imel takrat sicer enake izkušnje.

_________________
Question is more important than the answer.(Plato)
Nazaj na vrh
Skrit Poglej uporabnikov profil Pošlji zasebno sporočilo
Sokrat
Član
Član



Pridružen-a: Čet 25 Avg 2005 11:00
Prispevkov: 5584
Aktiv.: 23.57

PrispevekObjavljeno: Tor Avg 11, 2009 8:42 pm    Naslov sporočila:   Odgovori s citatom

alessio je napisal/a:
Sokrat, ne temo tistega članka je bila pred časom vroča razprava
na comp.arch.embedded. Nekatere eminence so članek hladnokrvno raztrgale.
Kot sem rekel, kakšno reč je potrebno vzeti z rezervo, je pa vsekakor zelo interesantno branje.


Bom razdelil odgovor, kr sem se zaletel v Wall of text Mr. Green

"Eminence" so vredne pickin dim, ce ni argumentov. Ce je kdo uzaljen, je to njegov problem, jih pa razumem vsaj toliko da ce so svoj cas in svoje delo vlozili zastonj, so nekoliko bolj emocionalni, namesto da bi bili racionalni. Ampak to ne poskrbi da problemi kar izginejo ... Jaz lahko povem iz lastnih izkusenj kako bugast je GCC. Vse spremembe pridejo najprej (smiselno) v IA32/x86 branch, pa se tam je toliko neumnosti, da je kar cudno, da sploh kaj deluje na koncu. Takoj ko gres na malo bolj eksoticno arhitekturo (moje izkusnje so z VAXi in gcc-vax, pisanje driverjev in druge kernel-mode kode, ki pac zahteva interakcijo s hardverom in tukaj gre direktno za enake stvari, v katere si se ti zaletel), je pa to kot ena loterija: nekdo je popravil generator kode, da izpljune kodo za tvojo zblj arhitekturo, ampak prevajalnik je pa delala skupina ljudi, ki ima v glavi samo x86 (lahko bi rekel: poklicni defekt). Kombinacija bruha iz sebe na kupe necesa, kar vecino casa deluje prav, vsake toliko pa ne ...

Glede clanka: ce se spravis namerno iskati napake na dolocenem podrocju, kjer je znano, da napake obstajajo, bos prisel do visokih procentaz napak. Tukaj ne gre za to, da bi nekdo zelel spljuvati delo nekoga drugega (saj lahko konec koncev vsak sam preveri ali res dela take napake, ker so zraven primeri, zadeva je pa povsem ponovljiva ...), ampak da opozori na tezave, ki se pojavljajo. Uzaljene primadone tukaj niso relevanten dejavnik - jih razumem, ampak ne upostevam.

Ja, seveda ne pomenijo tiste stevilke iz clanka da bo denimo en povprecen program narobe preveden denimo v 9% primerov (ce je tam slucajno tako povprecje). Je pa mozno, da pride na specificnem delu do napake, da potem (berz pregleda assembly listinga) izgubljas zivce s tem, ker stvari ne delujejo tako, kakor bi morale.

Zdaj sem pa povedal svoje in bom lahko v miru prebral ostanek tvojega sporocila, kjer je videti, da si opisal to tezavo Mr. Green

_________________
Ka ti bo pa torba ce si kupu kolo ?
Nazaj na vrh
Skrit Poglej uporabnikov profil Pošlji zasebno sporočilo
gregoral
Član
Član



Pridružen-a: Pet 24 Nov 2006 9:42
Prispevkov: 688
Aktiv.: 3.04
Kraj: Ljubljana

PrispevekObjavljeno: Tor Avg 11, 2009 9:09 pm    Naslov sporočila:  volatile troubles Odgovori s citatom

Zdravo, vsem!

Kot vidim sem sprožil val zanimanja Smile, vidim tudi da si medtem že rešil težavo, a vseeno bom postal to kar sem napisal pred 3 urami, potem sem bil pa nujno zadržan in nisem pravočasno postal.

Zakaj ti prevajalnik briše tisto zanko?

V tvojem primeru je spremenljivka c deklarirana znotraj funkcije main. Sicer je res označena kot volatile, ampak volatile je namenjen globalnim spremenljivkam.

V primeru HW registra (IOPIN) imaš v deklaraciji tudi naveden naslov kjer se nahaja, v primeru spremenljivke c pa ne, torej ti naslov spremenljivke c določi sam prevajalnik.

Morda sicer nič od tega ne vpliva na odločitev o odstranitvi for zanke.

Ja zelo verjetno zato, ker na isto lokacijo vpisuješ vrednosti v zanki in po končani zanki bo vrednost v c enaka mult_int(9998, 10), ne glede na to kakšne vrednosti ima prej.

Optimizacija je možna samo zato, ker funkcija mult_int ne dostopa do ničesar drugega kot do parametrov a in b, ter vrne rezultat.

Se pa strinjam, da če je spremenljivka volatile, da je čudno da ti odstrani for zanko.

Si morda poizkusil tudi s kakšno funkcijo ki dostopa tudi do kakšne globalne spremenljivke?

Recimo takole:
Koda:

int volatile c;
int volatile g;

int mult_int(int a, int b)
{
   return a * b * g;
}

int main(void)
{
   int i;

   g = 1;

   for(i = 0; i < 9999; i++)
   {
      c = mult_int(i, 10);
   }

   return 1;
}


LP, Gregor
Nazaj na vrh
Odsoten Poglej uporabnikov profil Pošlji zasebno sporočilo
Glitch
Član
Član



Pridružen-a: Pet 07 Apr 2006 11:40
Prispevkov: 1477
Aktiv.: 6.32

PrispevekObjavljeno: Tor Avg 11, 2009 9:25 pm    Naslov sporočila:   Odgovori s citatom

[brisano... prehitro je bilo] Smile

Tako torej (povzetek):

Lokalne spremenljivke nimajo nobene uporabne vrednosti, ce se jih ne uporabi in prevajalnik jih optimizira oz. odstrani kar je prav. Volatile gor, dol, levo, desno, ...
Ce za for zanko spremenljivko c dejansko uporabis, jo prevajalnik ne bo odstranil in je volatile popolnoma nepotreben (ker to ni namen te besede). Bo pa optimiziral for zanko, ce bo i brez volatile (kar je dejansko namen uporabe).

_________________
Answers: $1, Short: $5, Correct: $25, dumb looks are still free.
Nazaj na vrh
Skrit Poglej uporabnikov profil Pošlji zasebno sporočilo Pošlji E-sporočilo
alessio
Član
Član



Pridružen-a: Pon 04 Dec 2006 8:39
Prispevkov: 363
Aktiv.: 1.61
Kraj: Ljubljana

PrispevekObjavljeno: Tor Avg 11, 2009 9:40 pm    Naslov sporočila:   Odgovori s citatom

Glitch je napisal/a:

c se kasneje nikjer ne uporabi in volatile ne pripomore k resitvi problema. Optimizacija dela prav.

Iz vidika samega namena sicer trapastega primera, optimizacija dela prav.
Se pa vsaj nama s Sokratom postavlja vprašanje, ali c prevajalnik
res legitimno eliminira refresh spremenljivke c, ki je deklarirana kot volatile...
Citiram:

Razen v primeru, ce je spremenljivka c deklarirana kot globalna spemenljivka. V tem primeru naj bi (pogojnik, ker v casu tipkanja ne morem preveriti svoje trditve), naj bi zadeva delovala in optimizacija cja ne sme odstranit. Tako kot je napisal gregoral.

Verjetno si spregleda moj en moj post zgoraj. Sem že prišel do teh ugotovitev.

_________________
Question is more important than the answer.(Plato)
Nazaj na vrh
Skrit Poglej uporabnikov profil Pošlji zasebno sporočilo
Pokaži sporočila:   
Objavi novo temo   Odgovori na to temo   Printer-friendly version    www.elektronik.si Seznam forumov -> Programiranje embedded sistemov Časovni pas GMT + 2 uri, srednjeevropski - poletni čas
Pojdi na stran 1, 2, 3  Naslednja
Stran 1 od 3

 
Pojdi na:  
Ne, ne moreš dodajati novih tem v tem forumu
Ne, ne moreš odgovarjati na teme v tem forumu
Ne, ne moreš urejati svojih prispevkov v tem forumu
Ne, ne moreš brisati svojih prispevkov v tem forumu
Ne ne moreš glasovati v anketi v tem forumu
Ne, ne moreš pripeti datotek v tem forumu
Ne, ne moreš povleči datotek v tem forumu

Uptime: 492 dni


Powered by phpBB © 2001, 2005 phpBB Group