Hlavní navigace

Vlákno názorů k článku Fraktály v počítačové grafice X od Ondrej Skutka - Takové optimalizace, jako zapamatování hodnoty výpočtu x*x, které...

  • Článek je starý, nové názory již nelze přidávat.
  • 28. 12. 2005 12:51

    Ondrej Skutka
    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.
  • 29. 12. 2005 11:19

    Pavel Tisnovsky (neregistrovaný)
    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.
  • 29. 12. 2005 12:46

    Ondrej Skutka

    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. verze28,5s
    2. verze30,6s
    1. verze, gcc -O13,9s
    2. verze, gcc -O16,2s
  • 1. 1. 2006 14:04

    Pavel Tišnovský (neregistrovaný)
    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?
  • 2. 1. 2006 9:10

    Pavel Tišnovský
    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.
  • 2. 1. 2006 19:37

    Karel (neregistrovaný)
    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.
  • 3. 1. 2006 9:10

    Pavel Tišnovský
    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]