Názory k článku
Fraktály v počítačové grafice X

V odstavci 3, bod 2 mate obracene nerovnitko :)

Diky za upozorneni, ta chybka nastala pri prevodu do HTML.

Takové optimalizace, jako zapamatování hodnoty výpočtu x*x, které je potřeba na dalším řádku programu přece každý kompilátor musí umět.

Ve floatech a doublech to neni tak jiste, protoze to (alespon na platforme x8x) odporuje IEEE. A treba gcc na to ma specialni option. Vystup do asm je tusim volbou -S, takze je to mozne vyzkouset.

Jestli to ve floatech a doublech odporuje IEEE opravdu nevím. Co jsem ale chtěl říct je, že dnešní kompilery dokážou jednoduché věci optimalizovat líp, než člověk. A tak místo přemýšlení nad takovými detaily je lepší spustit gcc s parametrem -O

Mimochodem — víte, že ta neoptimalizovaná Juliova množina je rychlejší, než ta upravená?

Průměrné hodnoty (ze tří pokusů) naměřené programem time.

cx=-0,1; cy=0,7; maxiter=100000:

verze	čas
1. verze	28,5s
2. verze	30,6s
1. verze, gcc -O	13,9s
2. verze, gcc -O	16,2s

Pravda, gcc, msvc, Intelacky cc a spol. to uz dokazi zoptimalizovat dobre. Horsi je to napriklad s takovym Borlandim bcc, ktery i pri zapnuti optimalizaci vytrvale provadi o jedno nasobeni vic :-) Ale je pravda, ze Borlandi meli vzdycky mizerny prekladac, ktery obsahuje navic spoustu chyb (switch a bitove pole apod.)

S tim IEEE se to ma tak, ze vysledky vsech vyrazu by mely odpovidat typum operandu, tj. kdyz se neco pocita v doublech, vysledek by mel byt taky double. Matematicky koprocesor vsak pocita na osmdesati bitech a ne na pouhych 64, jak odpovida doublum, proto se pri plne optimalizaci toto narizeni obchazi a pocita se s vetsi presnosti - a zrovna u vypoctu Juliovych mnozin (tj. iteraci) se to projevi. To obchazeni spociva v tom, ze se vysledky ponechaji na zasobniku matematickeho koprocesoru a neukladaji se zpet do pameti (presne toto dela gcc pri optimalizaci, takze vse se provadi na sesti urovnich zasobniku).

Ten rozdilny cas je zajimavy, koukal jsem se do vysledneho assembleru (jak ho vyprodukuje gcc) a nic podobneho by se nemelo projevit. Zkusim to jeste proverit nazivo, tj. u realneho vypoctu. Prekladal jste pro i386 nebo pod neco vyssiho?

Nedalo mi to a vypocet jsem vyzkousel na Pentiu M 1,6 GHz. Parametry vypoctu:
width=800
height=600
cx=0.0
cy=0.9
maxiter=1000

Neoptimalizovana verze:
Test 1 (puvodni kod)
in: 49896 (pocet pixelu uvnitr mnoziny - pro kontrolu vypoctu)
out: 430104 (pocet pixelu vne mnoziny)
total: 480000
time 1: 69

Test 2 (upravena iteracni smycka)
in: 49896
out: 430104
total: 480000
time 2: 58

V neoptimalizovane verzi (preklad pro i386) je upravena smycka o vic nez 10 procent rychlejsi.

Optimalizovana verze (-O9 -march=pentium)
Test 1 (puvodni kod)
in: 49896
out: 430104
total: 480000
time 1: 43

Test 2 (upravena iteracni smycka)
in: 49896
out: 430104
total: 480000
time 2: 44

Po optimalizaci se casy srovnaly, dokonce je ta upravena smycka pomalejsi :-o

Optimalizovana verze (-O9 -funroll-all-loops -march=pentium)
Test 1
in: 49896
out: 430104
total: 480000
time 1: 44

Test 2
in: 49896
out: 430104
total: 480000
time 2: 44

Tady je prekladac donucen k tomu, aby smycku rozbalil a preskladal kod. Casy se (cca) vyrovnaly, asi by to chtelo vice iteraci (ale rozdil je stejne pod jednim procentem, tim se nema cenu zabyvat).


Pro pobaveni jsem kod jeste prepsal do Javy a vysledky me DOST prekvapily (spis je nekde hacek, jinak si to neumim vysvetlit):

Beh jako klient (java -client FractalSpeed)
Test 1
in: 49896
out: 430104
total: 480000
Time1: 59

Test 2
in: 49896
out: 430104
total: 480000
Time2: 54

Ty casy celkem odpovidaji tem ceckovskym (a je videt, ze u vypoctu se Java cecka dost drzi, ty kecy o pomalosti patri minulosti).

Beh jake server (java -server FractalSpeed)
Test 1
in: 49896
out: 430104
total: 480000
Time1: 1

Test 2
in: 49896
out: 430104
total: 480000
Time2: 1

Ty casy si v tomto pripade opravdu nedokazu nijak vysvetlit (nejake kesovani predchoziho behu?). Opravdu to hned, tj. po cca jedne sekunde, po spusteni skoncilo, vysledky (pocet pixelu vne a uvnitr mnoziny) jsou pritom dobre.

Co ja vim, tak pro moderni procesory je dulezite nepristupovat do pameti, kdyz to neni potreba. Plati na 10% pro cteni a na 90% pro zapis. Procesor ma nekolik front a FPU je take plne cache registru atd., takze ono predpocitani si a ULOZENI druhe mocniny muze byt silne kontraproduktivni. Zvlaste pokud se pouziji nepekne optimalizace zahravajici si s presnosti operandu - protoze FPU pak musi zjistovat, co je skutecne v pameti ulozeno.

A co se Javy tyka, tak v dobe inteligentnich JIT kompilatoru se ji obecne ve vypocetnim vykonu muze rovnat jedine program zkompilovany primo pro dany HW. Je to zkratka kompilator, ktery kompiluje maximalne efektivne prave pro ten procesor, na kterem to prave bezi a jeste si nepekne vypomaha profilovanim a dynamickym prekompilovavanim (pokud se pusti hodne dlouha vicemene periodicka uloha, kupodivu se jeji vykon s casem zvysuje - kompilator zjisti, ze se nejaka smycka vola moc casto tak provede hlubsi unroll). Overeno jiz pred lety na programech na FFT nebo syntezu reci. Dokud se nealokuje pamet nebo neprevesuji reference, vyrovna se slusne napsana Java velice dobre napsanemu C. Tedy az do chvile nez se vzbudi garbage collector, pak clovek teprve pochopi co znamena "Java is not real time" :-)

Kazdopadne ten vysledek u serverove verze je skutecne podezrely. Opravdu delala vse co mela a mezi spustenimi bylo JVM vypnute? Protoze takovehle zrychleni se podle mne nedosahne ani s asociativni cache. Predpokladam, ze vsechny verze pouze pocitaji a nevykresluji.

Je pravda, ze ja jsem se o architekturu modernich procesoru prestal zajimat uz od Pentia - o nem jsem jeste prelouskal par clanku venovanych optimalizacim, ale potom jsem si uvedomil, ze nebudu mit cas a chut provadet rucni optimalizaci pro jednotlive pipeliny (je to taky zbytecne, protoze kazda nova generace procesoru je v tomto odlisna). Od te doby jsem prakticky na assembler nesahl :-|

Pravda je, ze pokud prekladac cecka preklada podle normy, mel by vysledek kazdeho vyrazu prevest na dany datovy typ, v nasem pripade z extended na doubly, coz opravdu muze vypocet zpomalit (dalsi vysledky jsem uvedl nize).

Ano, obecne vim, jak funguje JIT (samozrejme ne do hloubky, ale unroll-loops apod. je mi jasne), ale stejne byl ten vysledek pro "java -server" nejaky divny. Posilam vysledky dosazene na jinem (lepsim) stroji, ale zvedl jsem pritom pocet iteraci na desetinasobek:

c-neoptimalizovane (gcc)
time 1: 187.000
time 2: 151.000

c-optimalizovane (gcc -O3 -march=pentium)
time 1: 143.000
time 2: 143.000

c-optimalizovane (gcc -O3 -funroll-all-loops -march=pentium)
time 1: 145.000
time 2: 144.000
[^ kupodivu pomalejsi nez predchozi]

c-optimalizovane (gcc -O3 -funroll-all-loops -ffast-math -march=pentium)
time 1: 0.000
time 2: 0.000
[^ tady je chyba ve vypoctu, evidentne vnitrni smycku vynechalo]

java server
Time1: 1
Time2: 1
[vysledek je ok, ale ten cas opravdu nechapu]

java client
Time1: 183
Time2: 148
[zhruba na polovine cesty mezi optimalizovanym a neoptimalizovanym gcc]

primlouval bych se, aby se obrazky po kliknuti zobrazily v nejakym big huge rozliseni :-D (aspon tak 1280x960). Dekuji.

neni problem... od pristiho dilu/roku :-)

Kde je odkaz na program ?

trochu iniciativy :-P

Vis jak blbe se pastuje cesky text z html ? Navic to z neznamych duvodu neobsahuje konce radku ...

ty konce radku, to je nejaka chyba ve firefoxu, protoze konqueror je tam normalne vklada...

Programek (resp. programky) budou v cele sve krase :-) uvedeny v dalsim pokracovani tohoto serialu. Pri "copy and paste" by to konce radku sekat nemelo, ty uryvky zdrojaku jsem daval do znacek

 a 

, s tim by problemy byt (doufam) nemely (ale clovek nikdy nevi). Treba FF to zvlada bez problemu.

Ale sekl jsem se ve vyse uvedene odpovedi :-(, misto prazdnych radku tam ma byt <pre> a </pre>

Ja MAM firefox. 1.0.7.

Sorry, chtel jsem rict FF 1.0.6 to zvlada. Ale pred chvili jsem to zkousel na FF 1.0.6 pod Windows, a tam to dela presne ty problemy, ktere jste popsal - konce radku se nahradi mezerou (ASCII 32). To je zajimave, v HTML je ten zdrojak napsany dobre, pouzity jsou tagy <code> a </code> (ty vznikly z puvodnich pre-cek).

Jenze tagy code nejsou ekvivalentem pre - tedy dokud nemas v css neco jako '.urs .urs-code code {padding:.5em .7em;display:block;white-space:pre;border:1px solid #BBB}' jako root ... a mozna prave v tom je problem. Na obrazovce je to spravne, v selection uz ne.

Taky me to po me predchozi odpovedi napadlo, protoze jsem si az potom vsiml, ze v Rootovske strance chybi tagy pro konce radku :-). S timto vsak nemuzu nic udelat, muj puvodni XHTML kod (s "pre" a samozrejme pouze s CR) je automaticky prevaden redakcnim systemem, ktery pouziva "code" a samozrejme nejake CSS k tomu, aby to bylo podsviceno bile a pripadne se zobrazovaly scrollbary. Asi zbyva bud pockat do zitrka na dalsi pokracovani :-) nebo ve zdrojaku XHTML, ktery Root posila hledat napriklad retezec "//--" (tim zacinaji hlavicky vsech mych funkci).