Re: Odpověď: Re: Sou?et v C - neni pro PICjiny kompilator?

[Ales Prochaska]

>> To neni tak uplne pravda. Vlastne to neni vubec pravda. Jednak neni
>> zadny principialni duvod, proc by melo C generovat rychlejsi kod nez
>> ostatni prekladace, naopak "diky" jeho omezene a nejasne syntaxi je
>> nekdy problem rozpoznat jak to vlastne programator minil a prislusne
>> to optimalizovat.

> Neberte to prosim jako flame ale nemate pravdu.
> Nechapu co chcete rici omezenou syntaxi ale sila jazyka C je mimo jine
> i v tom ze Vam umozni napsat takove "parasarny" ktere Vam rada jinych
> jazyku proste nepovoli ;-)
> Kolik jinych jazyku Vam napriklad umozni "napovedet" kompilatoru aby
> dal nekterou promenou do registru a ne na zasobnik. Kde jinde muzete
> delat takove psi kusy s pointerovou aritmetikou. Proste spoustu
> optimalizaci si muzete delat rucne a nespolehat se jen na kompilator.

Ty argumenty jsou celkem logicke, takze zatim zadne flame :-). Moje
namitka je ovsem v tom, ze zminena sila C je i jeho slabinou. Vezmu
jeden priklad: v C se tvrdi neco jako ze for(A;B;C){D} je ekvivalentni
A;x:if(B){D;C;goto x} nebo tak nejak. Takhle obecna formulace, vlastne
temer na urovni assemblerskeho makra mi dovoluje udelat spoustu veci,
ktere se velmi obtizne optimalizuji (ja jim rikam prasarny).

Prekladac, ma-li alespon trochu optimalizovat, musi rozlisovat hned
celou skalu pripadu: od nejjednodussiho (jde o cyklus s jednou ridici
promennou, statickou podminkou zavislou pouze na teto promenne a
prikazem tuto promennou jednoduse inkrementujicim), pres cykly vice
promennych, vynechane podminky, dynamicke vyrazy az po zcela obecny
pripad, na kterem nejde optimalizovat vubec nic. Jeste navic musi
zjistit, jestli se ridici promenna cyklu (muze byt i jisty problem ji
vubec rozpoznat) v tele cyklu meni a jak (i to muze byt problem
rozpoznat). Pak musi kazdy typ prikazu optimalizovat zvlast, coz je
nesmirne pracne a zadny autor prekladace neni schopen vsechny pripady
dotahnout do konce, dokonce ani na 100 % rozpoznat ten prvni.

Pro srovnani treba Ada (asi tu v ni nikdo neprogramuje, tak se snad
nikoho nedotknu) dovoluje jedinou variantu: for A in ROZSAH loop
PRIKAZY end loop; A se z definice jevi v tele cyklu jako konstanta.
Pak je jiste, ze vyraz zavisi jen na teto jedne promenne (a je z
definice staticky), promennou mi nikdo v tele cyklu nepremasti (pokud
ano, pozna se to uz pri prekladu), takze si muzu krasne optimalizovat.
A nejen to, prekladac vi o vsech vyrazech v tele cyklu, zda musi byt
provadeny presne v naznacenem poradi (coz snadno pozna diky tomu, ze i
ostatni jazykove konstrukce jsou podobne prisne) a muze cyklus
rozdelit treba na ctyri jine, ktere se budou provadet paralelne na
ctyrech procesorech viceprocesoroveho systemu.

Uf, to jsem se rozkecal. Ale chtel jsem tim ukazat, ze cim je jazyk
prisnejsi, tim vic informaci o problemu programator musi (a vlastne
vubec muze) prekladaci dodat a tim lepe je dokaze optimalizovat.


>> Ale hlavne rychlost pri programovani v ASM je dana tim, ze clovek voli
>> jiz samotny algoritmus (napriklad prohledavani pole) uz primo
>> optimalizovany pro ASM, coz zatim ani nejlepsi prekladace vyssich
>> jazyku nedokazou.

> Volba algoritmu je vzdy dulezita a to bez ohledu na to jestli pisu
> v ASM nebo C. Viz napr. ono prohledavani pole (prvni vyskyt daneho
> prvku). Vetsina lidi to napise nasledovne (nebo podobne, dulezity je
> algoritmus nikoli jazyk!):

> int i = 0;
> while (i<pole.length) {
>     if (pole[i] == hledany_prvek) break;
>     i++;
> }
> if (i == pole.length) => prvek nenalezen
> else => i - pozice prvku

> Problem je v tom ze v tele cyklu while se provadeji dva testy
> kontroluje se rozsah pole (i<pole.length) a soucasne rovnost prvku.

> Lepe to lze napsat tak, ze pouzijeme pole o jeden prvek delsi
> a hledany prvek umistime na konec. Pak nemusime kontrolovat rozsah
> indexovani protoze prvek vzdy najdeme a tim se cyklus ukonci.

> while (pole[i] != hledany_prvek) i++;

> Pote pouze zkontrolujeme jestli jsme nasli prave ten posledni
> prvek protoze pak jsme vlastne nenasli nic ;-)

> I kdyz ten prvni priklad napisete superoptimalne v asm a druhy
> prelozite napr. v C tak ten druhy bude vzdy rychlejsi (za
> predpokladu ze to pole nebude mit extreme malo prvku) ;-))

> S pozdravem,

> Jakub Slajs

S touto myslenkou 100% souhlasim. Rychlost programu dela v prvni rade
predevsim spravna volba algoritmu, jeho implementace je az druhorada,
i kdyz muze byt take celekm dulezita.

Ales Prochaska