kodtabla

[ide.ne.irj at freemail.hu]

Thus spake Nemely Z:

> ehhez sajnos elobb definialni kell az optimalitas fogalmat, addig
> semmilyen szamitaselmeleti tetelt (amit Te ugy fogalmaztal meg, hgoy az
> optimalizacio nem algoritmizalhato) nem lehet rahuzni. Te az
> optimalitast mint legrovidebb futasidot (legkisebb fogyasztast vagy
> legkisebb memoria hasznalatot) tekinted, Gabor pedig a legkisebb
> kodolasba befektetett penzt, munkaorat.

Az a kovetkezo lepes, hogy a ketto kozott kompromisszumot kell kotni.
Ha akarod idezhetem magam, tobbszor leirtam.

> volna hogy kezzel optimalizalok a fenti parameterekre. Az, hogy melyik
> terul meg, a konkret termek hatarozza meg, nem pedig az, hogy ki tudja
> meggyozobben eloadni, hogy oneki van igaza.

Most foleg nem ilyesmirol volt szo, mert ez egy elektronikai lista, itt
csak a szakmaba vago reszletek kitargyalasa johet szoba.

> Sajnos meg toled sem lattunk semmilyen definiciot arra, hogy mi az
> optimalitas. Ez nem is veletlen, mivel olyan hogy optimalitas, olyan nem
> onmagaban nem letezik, oda kellene melle tenni azt is, hogy mi szerint
> optimalis, akkor mar lehet teteleket kimondani ra.

De mondtam konkretumot, pl egy algoritmust jelentosen fel tud gyorsitani,
ha a hardverben van barrel shifter. Ennek kihasznalasahoz mashogy kell
megirni a progit, meg C-ben, es barmilyen egyeb magasszintu nyelvben is.
Ez egy konkret pelda, egy DES forrasban van, amit most izzitok be egy
alkalmazasba. Ugyanigy barmely mas proci egyseggel megtortenhet.
Ha a hardver megvan, akkor azt kihasznalva kell az algoritmust lekodolni,
mert a fordito sohasem fog magatol rajonni, ha kirulirom neki aritmetikai
muveletekkel. Ha a hardver nincs meg, akkor emulalja a fordito az egyseget,
ami lassu, ennel a kezzel lekodolt workaround sokkal gyorsabb.
Ez pl egy olyan magasabb szintu optimalizacio, amit csak kezzel, emberi
erovel lehet megcsinalni. Ez az egyik fajta.
A masik pedig olyan egyszeru dolog, hogy a parossag vizsgalathoz shifteljen
egyet vagy es muveletet hajtson vegre. Ez nem fugg semmitol, soronkent
lehet alkalmazni. Nem kell semmit gondolkodni, csak mindig a megfelelo
utasitast bevagni a celhardvertol fuggoen. Erre kepes a gep.

> Az, hogy manapsag a Java programok az uj virtualis gepeknek koszonheton
> nativ C/C++ sebesseggel mukodnek, teny. (Termesztesen mindenki tud
> mutatni olyan C kodot es olyan Java kodot is ami gyorsabb adott esetben,
> most atlagos esetrol beszelunk, tobb szazezer/millio kodsor eseten,
> desktop PC eseten es altalanos uzleti celu programoknal).

En kizartnak tartom, de mindegy... Szeretem az ilyen tenyeket.
A kovetkezo verzioja a virtualis gepnek 10%-al gyorsabb lesz mint az
elozo, tehat akkor az a C proginal is gyorsabb lesz. Sot, lehet hogy
van olyan teszteredmeny is, hogy a gepi kod csak 5%-al gyorsabb mint a C,
tehat a Java osszessegeben 5%-al gyorsabb a gepi kodnal is. Persze...

> Hogy jon ide a nyaktervezes? A nyaktervezes az a grafelmeleti
> sikbarajzolas problemaja (csak itt persze tobb reteg lehet,stb) es 
> (a matematikusok jelenlegi sejtese szerint) nem polinomialis ido alatt
> oldhato csak meg. Na es?
>
> Ki mondta, hogy a mai nyaktervezokbe beepitett autorouter optimalis?
> (akar penzben, akar EMC-ben, akar logikus elrendezesben,stb.)

En ezt allitom a program optimalizalasrol is. NP teljes problema.

> Te most a megallasi problemat probalod rahuzni erre a temara, csak epp
> nem jol. Eloszor is, talan megint definialni kellene, hogy milyen
> parameterre vonatkozo optimalitasrol beszelsz, addig eleg nehez lesz
> barmilyen elmeleti tetellel elohozakodni..

A megallasi axioma uzenete, hogy egy programot egy masik program nem
tud 'megerteni', atlatni. Csak lepesenkent kiprobalhatja annak utasitasait.
A tetel szerint ez alapjan meg az sem dontheto el, hogy egyaltalan meg
fog-e allni a program, az kulonosen nem, hogy milyen gyorsan.
Program helyett gondolhatsz algoritmust is, ugy talan konnyebben ertheto.

> Na most tekintsuk csak a megoldhato feladatok halmazat, es a te
> megoldasodat, amit kezzel optimalizaltal futasidore. Be tudod
> bizonyitani, hogy a te megoldasod optimalis, azaz nincs nala jobb? Mert
> en fogadni mernek,hogy ha raeresztunk a te kododra egy 100 fos
> programozo brigadot, biztos talal x megsporolhato ciklust.

Nem ez a lenyeg. Hanem az, hogy par 10%-ot ra lehet verni a fordito
altal 'optimalizalt' progikra. Olvasd masok irasait is, ez teny!
Hogy meddig erdemes elmenni, kompromisszum kerdese. Nyilvan amig
tobbszoros sebesseg-novekedes erheto el, mindenkeppen, amikor csak par
10%, meggondolando, alatta mar tokmindegy. Ennek a szelere kell eljuttatni
a progit, es kesz.
Az en programjaim tuti nem optimalisak, csak sokkal jobbak mint amit egy
C fordito valaha fog tudni generalni. Megemlitenek olyan aprosagokat,
hogy 24 es 48 bites szamokkal is dolgozom assemblyben, amihez a C-nek
nincsenek adattipusai, nincsenek a librarykben matek fuggvenyek, teljesen
kezelhetetlen a szamara. Ez onmagaban _dupla_ sebesseget jelent!
Akkor is ha szarul irom meg. De raadasul az algoritmus magja majdnem
tokeletesen van lekodolva, ott mar max par %-ot lehetne nyerni.

> es? ki mondta, hogy a 10% cpu ido nyereseg meg fog teruli penzugyileg?
> mondhatsz egy olyan termeket ahol meg fog, mas tud mondani olyat ahol
> nem.. na es?

Egyreszt nem csak 10%-rol vitazunk, sokkal komolyabb problemak vannak.
Masreszt 10% megerheti. Nekem most egy projectben kb ennyi a tartalekom...
Egy masodrendu es egy elsorendu IIR szuro megy egyszerre valos idoben,
ket masodrendu mar nem. Optimalizalas nelkul mar reg mas procit kellett
volna valasztani, igy ez egy hasznalhato kompromisszum.

> Es pl. a powerPC processzor? 32 atlanos celu es 32 lebegopontos
> regisztere van, ami ugyan meg mindig nem 200, de az emberileg egyszerre
> nyomon kovetheto hataron mar boven felul van..
>
> Ja hogy te most csak 8bites mikrovezerlokben gondolkodsz? Pardon.

Ennek a 8 bites szarnak is 32 regisztere van. Ilyenkor mi van?
Ez valoban sokak szamara nem kovetheto, ok programozzanak java-ban vagy
basic-ben, csak ne beszeljenek hulyeseget hogy a java progi gyorsabban
fut mint az assembly...

> Nyilvan igy van. Es? Most epp megint mire optimalizalunk? Mert az
> lemaradt ismetelten..

Kizarolag mindig a sebessegre. Az ar most lenyegtelen, ez nem kozgaz lista.

> Zoli

-- 
Valenta Ferenc <vf at elte.hu>   Visit me at http://ludens.elte.h u/~vf/
"Rogton maga jon, csak elvittek elezni a bardot"