Začátky v Javě

[JSH]

Spustal som to na AMD Phenom x4 945 3GHz.

Trefil se

On pro tenhle test výkon procesoru samotný moc neřekne. Hodně záleží na latenci a rychlosti paměti, na velikosti cache a na tom, jak je chytrý prefetcher. Ta latence se pro hodně vrcholů nejspíš schová protože se jede sekvenčně po velkých kusech paměti, ale imo tu rychlost omezí hlavně čtení těch vah.

RAII :
15:29 majo psal, že mezi O2 a O3 nenaměřil významnější rozdíl. Ono O3 nebývá vždycky rychlejší než O2. O3 zapíná optimalizace, které nemusí být vždycky prospěšné. Pokud člověk nehodlá optimalizace nějak extra řešit, tak bývá lepší volba to O2.

BTW co sakra myslíš tím release módem? Co projekt to jiný release mód a společné mají možná tak ty zapnuté optimalizace a ani to není jisté.

[Reklama]

[Jakub Galgonek]

-O3 + release mód. Byl to pouze odhad ... a trefil jsem se jak vidím. I když, z části se divím, typoval sem Intel.

Povedzte Kefalín, čo vy si predstavujete pod takým slovom release mód?

Podle tvého shortestPath.cbp jde o tohle (zkráceno):

<Target title="Release">
    <Option compiler="gcc" />
    <Compiler>
        <Add option="-O2" />
    </Compiler>
    <Linker>
        <Add option="-s" />
    </Linker>
</Target>

Takže majo33 možná na rozdíl od tebe tu binárku nestripnul, ale v tom bych neviděl problém.

AMD jádra obvykle potřebují vyšší frekvenci aby se vyrovnali Intel jádrům ze stejné "třídy".

A i přes toto tvrzení si odmítáš připustit, že mu to v release módu běží stejně rychle jako tobě v debug módu ?

[RAII]

hlupáku ... aspoň si otestuj svoje tvrzení:

Kód: [Vybrat]

<?xml version="1.0" encoding="UTF-8" standalone="yes" ?>
<CodeBlocks_project_file>
<FileVersion major="1" minor="6" />
<Project>
<Option title="shortestPath" />
<Option pch_mode="2" />
<Option compiler="gcc" />
<Build>
<Target title="Debug">
<Option output="bin/Debug/shortestPath" prefix_auto="1" extension_auto="1" />
<Option object_output="obj/Debug/" />
<Option type="1" />
<Option compiler="gcc" />
<Compiler>
<Add option="-g" />
</Compiler>
</Target>
<Target title="Release">
<Option output="bin/Release/shortestPath" prefix_auto="1" extension_auto="1" />
<Option object_output="obj/Release/" />
<Option type="1" />
<Option compiler="gcc" />
<Compiler>
<Add option="-O2" />
</Compiler>
<Linker>
<Add option="-s" />
</Linker>
</Target>
</Build>
<Compiler>
<Add option="-Wall" />
<Add option="-fexceptions" />
</Compiler>
<Unit filename="main.cpp" />
<Extensions>
<code_completion />
<debugger />
</Extensions>
</Project>
</CodeBlocks_project_file>Tento CBP file je vygenerován když mám nastaveny optimalizace -O3. Schválně si to zkus, a použij prosím stejnou verzi IDE, v novější může být bug opraven. [12.11-1.el18]

[Jakub Galgonek]

hlupáku ... aspoň si otestuj svoje tvrzení:

Hele, važ slova!

Tento CBP file je vygenerován když mám nastaveny optimalizace -O3. Schválně si to zkus, a použij prosím stejnou verzi IDE, v novější může být bug opraven. [12.11-1.el18]

Schválně jsem kvůli tobě nainstaloval CodeBlocks a schválně ve verzi 12.11 a žádná taková chyba tam není. Vygeneruju projekt a release je definován jako -O2 pro překladač a -s pro linker. Když pro release nastavím -O3 a uložím projekt (!), tak se to projeví i v CBP souboru. Každopádně to nic nemění na mém původním tvrzení, že CodeBlocks žádné další optimalizační volby už nepřidává!

[majo33]

Na kompilovanie som nepouzil ziadne IDE, ktore by mi nastavilo nejake ine parametre (kompiloval som to z prikazoveho riadku). Zakazanim assertov -DNDEBUG sa da ziskat este tak 5% navyse, ale moze to byt aj chyba merania.
V tom programe viac casu zabera generovanie nahodnych cisel nez samotny vypocet. Generovanie trva cca 4.7 krat dlhsie nez samotny vypocet (plati pre oba jazyky).

[Reklama]

[Filip Jirsák]

Kód: [Vybrat]


            for(int v = 0; v < count; v++)
            {
                int distanceThroughU = minDistance + weight[u * count + v];
               
                if(distanceThroughU < distance[v])
                    distance[v] = distanceThroughU;
               
                if(distance[v] < min)
                {
                    u = v;
                    min = distance[v];
                }
            }


Podle mne je v tom kódu chyba. Původně jsem si říkal, že je to nějaká pekelná optimalizace. Ale dává to špatné výsledky, takže se i přes pozdní hodinu přikláním spíš k tomu, že je to chyba. u by mělo být v rámci for cyklu neměnné, protože se používá pro přístup do pole vah (weight[u * count + v]). Zároveň se ale mění v případě, kdy je nalezena kratší vzdálenost (u = v).

Správně by to myslím mělo být takhle:

Kód: [Vybrat]

            int nextU = u;
            for(int v = 0; v < count; v++)
            {
                int distanceThroughU = minDistance + weight[u * count + v];
               
                if(distanceThroughU < distance[v])
                    distance[v] = distanceThroughU;
               
                if(distance[v] < min)
                {
                    nextU = v;
                    min = distance[v];
                }
            }
            u = nextU;

S touhle opravou to má mnohem větší rozptyl výsledků, někdy je to i o dost rychlejší, než s tou chybou, někdy podstatně pomalejší. Každopádně ale to naplnění vah trvá průměrně tak 5× až 10× déle, než výpočet nejkratší cesty - takže je to spíš test použitého generátoru náhodných čísle než co jiného.

Původně jsem to chtěl tedy přepsat do paralelního zpracování, a to u mi tam pořád překáželo. Takhle už to snad půjde líp :-)

[Jakub Galgonek]

Podle mne je v tom kódu chyba. Původně jsem si říkal, že je to nějaká pekelná optimalizace. Ale dává to špatné výsledky, takže se i přes pozdní hodinu přikláním spíš k tomu, že je to chyba. u by mělo být v rámci for cyklu neměnné, protože se používá pro přístup do pole vah (weight[u * count + v]). Zároveň se ale mění v případě, kdy je nalezena kratší vzdálenost (u = v).

Máš pravdu, díky! Tak to dopadá, když na to nemá člověk moc času a spěchá :-(.

[gamer]

Původně jsem to chtěl tedy přepsat do paralelního zpracování, a to u mi tam pořád překáželo. Takhle už to snad půjde líp :-)

Není třeba znovuvynálézat kolo, tohle už existuje:
http://www.osl.iu.edu/research/pbgl/
Konkrétně pro dijkstru:
http://www.osl.iu.edu/research/pbgl/documentation/dijkstra_shortest_paths.html

[...]

jeste vas to bavi? vite, ze je ten problem irelevantni vzhledem k naproste vetsine aplikaci vsedniho dne?

1. nebezi dostatecne dlouho, aby obsahoval vetsi mnozstvi kolekci a degragmentaci tenured heap
2. ma treba oproti eshopu vyrazne "podmerecne" mnozstvi pametovych operaci (alokovani,zahozeni,kompakce,defragmentace)
3. je to dane i strukturou problemu a tim jak "akademicka" data pouziva a jak s nimi naklada a jake maji naroky na zivotnost a jak casto se nedostanou do tenured heapu a to malo co se tam dostane v naproste vetsine je z kategorie permanent. coz treba oproti minutovym/hodinovym session cache v eshopu je docela rozdil.
4. nedostatecne velikosti dat proti velikosti heapu. naprosta vetsina tech malofiremnich aplikaci ma v databazi nasobne vice dat nez maji k dispozici mista na heapu a jen se v duchu tise modli, aby je provoz nikdy nepotreboval vsechny nebo jejich vyznamnou cast.
... slo by pokracovat, ale zas tak me to nebavi.

[YF]

hlupáku ... aspoň si otestuj svoje tvrzení:

RAII: ty uz prestan urazet lidi a bez se nad sebou nekam nadlouho a hluboce zamyslet - jediny co dovedes je bejt arogantni typek - a ani to nedelas dobre protoze se ztrapnis s kazdym dalsim prizpevkem - tak uz bud tak hodnej - ukonci to trapeni a uz nic nepis

jinak debata kolem O2/O3 az O20 mi prijde naprosto ujeta - jak v dnesni dobe pri pouiziti tuny vrstev ve vsem chcete proboha vubec lpet na jednom jedinem aspektu jako je rychlost provadeni nejakeho algoritmu? obecne tu pletete garbage collectory - pouziti javy demonstrujete na naprosto vytrzenych pouzitich - mereni javy pomoci time ... pokud se nekdo chce zabyvat a porovnavat java platformu a jeji ladeni pak doporucuji skoleni napriklad od tohoto pana Kirk Pepperdine (http://www.kodewerk.com) - projdete si materialy o metodikach testovani a vubec uvazovani nad tim kdy ma vubec cenu neco ladit a jak se s tim vyporadat. Je jasny ze C++ bude vzdycky rychlejsi nez java kdyz nekdo bude potrebovat - ja nechapu o cem se tady kdo chce dohadovat - to proste vyplyva z podstaty veci - ovsem aspekt rychlosti je jeden z MNOHA a je potreba k tomu tak vzdy pristupovat - nekdo tu psal neco o jave & GC & telefonich systemech ze nechce cekat na full gc - proboha co to je za argumenty? podivejte se v cem eriksoni psali firmware do jejich ustreden a jak tam pracuje GC a pak mozna proc to tak pouzili - to je zase nakej pan Joe Armstrong - taky moc zajimavej pan - ja doporucuju vsem v tomhle foru prestat s timdle neuveritelnym hate-threadem ve kterym tu ztrapnujete nase remeslo strasnym zpusobem.

YF

[r]

Kód: [Vybrat]

import java.util.Random;


public class Dijkstra
{
    public static int compute(final int count, int start, int stop, final int weight[])
    {
        boolean[] invalid = new boolean[count];
        int distance[] = new int[count];
       
        for(int i = 0; i < count; i++)
            distance[i] = Integer.MAX_VALUE;
       
        int u = start;
        distance[u] = 0;
       
        while(u != stop)
        {
            invalid[u] = true;
           
            int minDistance = distance[u];
            int min = Integer.MAX_VALUE;
           
            for(int v = 0; v < count; v++)
            {
                if(invalid[v])
                    continue;
               
                int distanceThroughU = minDistance + weight[u * count + v];
               
                if(distanceThroughU < distance[v])
                    distance[v] = distanceThroughU;
               
                if(distance[v] < min)
                {
                    u = v;
                    min = distance[v];
                }
            }
        }
       
        return distance[u];
    }
   
   
    public static void main(String[] args)
    {
        long time = System.currentTimeMillis();
       
        final int count = 5000;
        final Random rand = new Random();
       
       
        int weight[] = new int[count * count];
       
        for(int i = 0; i < count * count; i++)
            weight[i] = rand.nextInt(100) + 1;
       
        int res = compute(count, 0, count - 1, weight);
       
        time = System.currentTimeMillis() - time;
        System.out.println("result: " + res);
        System.out.println("time  : " + time);
    }
}


Da sa to este o malinko zrazit, pretoze vo for cykle sa po kazdej iteracii rata count * count

Kód: [Vybrat]

...
final int count = 5000;
        final int countcount = 25000000;
        final Random rand = new Random();
       
        final int weight[] = new int[countcount];
       
        for(int i = 0; i < countcount; i++)
            weight[i] = rand.nextInt(100) + 1;
...
RAII: kriticke casti kodu sa daju volat cez JNI

[perceptron]

mne sa to po tej uprave java kodu zacykli :-)

mne vyslo:

clang++ -std=c++11 -O3 dijkstra.cpp -o dijkstra-cpp: 319ms

java (1.7.0u51): 392
z toho: ratanie vah: 175
vypocet: 124
ocividne z toho ide 100 ms na reziu (boot jvm)

clang so stdlibc++, ako navrhoval zboj, som na debiane nerozbehal

processor   : 0
vendor_id   : GenuineIntel
cpu family   : 6
model      : 42
model name   : Intel(R) Core(TM) i7-2720QM CPU @ 2.20GHz
stepping   : 7
cpu MHz      : 2266.095
cache size   : 6144 KB
fpu      : yes
fpu_exception   : yes
cpuid level   : 5
wp      : yes
flags      : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 syscall nx rdtscp lm constant_tsc up rep_good nopl pni monitor ssse3 lahf_lm
bogomips   : 4532.19
clflush size   : 64
cache_alignment   : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

[fail]

hlupáku ... aspoň si otestuj svoje tvrzení:

... nekdo tu psal neco o jave & GC & telefonich systemech ze nechce cekat na full gc - proboha co to je za argumenty? podivejte se v cem eriksoni psali firmware do jejich ustreden a jak tam pracuje GC a pak mozna proc to tak pouzili

ericsoni erlang se rozebiral kdysi v minulosti v obdobne nesmyslenm hate vlakne. rozuzleni bylo to, ze struktura navrhu a pouziti erlangu umoznuje pouzit primocarejsi techniky GC, ktere ani v C++ ani v Jave nebudou fungovat bez dodatecnych berli kvuli kterym budou fungovat hur nez ty soucasne pouzivane. erlang jde mimo me, ale jestli to je pravda, tak na to bude urcite nejmin jeden dokument s dostatecne dobrym pagerankem.

[YF]

hlupáku ... aspoň si otestuj svoje tvrzení:

... nekdo tu psal neco o jave & GC & telefonich systemech ze nechce cekat na full gc - proboha co to je za argumenty? podivejte se v cem eriksoni psali firmware do jejich ustreden a jak tam pracuje GC a pak mozna proc to tak pouzili

ericsoni erlang se rozebiral kdysi v minulosti v obdobne nesmyslenm hate vlakne. rozuzleni bylo to, ze struktura navrhu a pouziti erlangu umoznuje pouzit primocarejsi techniky GC, ktere ani v C++ ani v Jave nebudou fungovat bez dodatecnych berli kvuli kterym budou fungovat hur nez ty soucasne pouzivane. erlang jde mimo me, ale jestli to je pravda, tak na to bude urcite nejmin jeden dokument s dostatecne dobrym pagerankem.

a o tom to je - o modelech, myslenkach a patternech za tim - sou to nastroje - abstrakce umoznujici efektivnejsi reseni bez bolehlavu prepouzitelne umoznujici efektivni komunikaci mezi vlastniky prislusnych komponent a modulu - jasne definovane mantinely tak aby nad tim bylo mozno premyslet - a spousta dalsiho - proste neexistuje jediny ultimatni reseni ktery to zvladne - ani jeden nastroj ani jeden jazyk coz je nakonec taky jen nastroj - proste to co z tech nastroju dela funkcni celek je hlavne pristup lidi k nim - a kdyby to vsichni delali tak jak to predvadime ve valne mire tady u nas - tak bysme po sobe dneska asi hazeli po sobe klacky - arogance spojena s neznalosti - to je krutoprisna kombinace ktera nas posouva tak akorat nikam - mezi programatory je skutecne rozdil - a astronomicky - ale to neznamena ze na urovni remesla by tyhle lidi nemeli bejt schopny spolu komunikovat a vzajemne si tvorit rozhrani tak aby mohli vsichni v ramci moznosti efektivne tvorit

[Jakub Galgonek]

Da sa to este o malinko zrazit, pretoze vo for cykle sa po kazdej iteracii rata count * count

S tím by si měl optimalizátor snad poradit sám.