Názory k článku Monitorování procesů a správa paměti v JDK6 a JDK7 (2)
-
Filip Jirsák (neregistrovaný)
Nejčastější použití StringBufferu/stringBuilderu je pravděpodobně spojování řetězců. Proč v JDK není třída optimalizovaná pro tuhle operaci, a nepoužívá se pro spojování řetězců (i operátory + a +=) právě taková třída? Pro pouhé spojování řetězců přece není nutné obsah řetězců neustále kopírovat a postupně rozšiřovat buffer. Stačí si zapamatovat posloupnost řetězců a na konec (při volání toString()) najednou vytvořit buffer požadované délky a do něj obsahy zkopírovat najednou – jak to dělá např. jodd.util.StringBand.
-
kuka (neregistrovaný)
Ono v JDK neni rada dalsich mozna sikovnych veci. Skutecne zavazne problemy zpusobuje pouze spojovani v cyklu, coz by takova trida stejne neresila.
Na druhe strane ukladani retezcu muze byt dost pametove neusporne - extremem je priklad v clanku, kdy se pridavaji jen cisla a mezera. Konkretne StringBand by obsahoval obrovske pole, pro cisla by navic vznikly jejich String reprezentace (a String je velice pametove "drahy" objekt). Proste pro kazdy ucel se hodi neco trochu jineho, StringBuilder je podle mne pro spojovani rozumny kompromis, ktery nikomu nezpusobi prusvih. Pokud je pro to duvod, neni problem si naprogramovat neco na miru.
-
Pavel TišnovskýZlatý podporovatelMate pravdu, ten priklad v clanku je dovedeny do extremu, ale podobny problem se Stringy uz jsme resili nekolikrat. Napriklad v databazi Hypersonic (dnes HSQLDB) existuji tridy, ktere dokazi cele databazove schema vyexportovat do textoveho souboru jako SQL-skripy obsahujici prikazy typu CREATE TABLE a nekdy i data, tj. INSERT INTO.
Ovsem predevsim ve starsich verzich se tyto prikazy skladaly do Stringu, ktere se potom exportovaly. I u nepatrne vetsich databazi trvaly exporty silene dlouho a pritom po nepatrne uprave retezcovych operatoru + a += za StringBuilder je urychleni znatelne na prvni pohled (hlavne to samozrejme oceni zakaznici ;-)
-
kuka (neregistrovaný)
Tak to jiste, ja urcite nijak neobhajuju spojovani retezcu operatorem +. Je s podivem, jak casto je to k videni, vezmeme-li v uvahu, ze to byva rozebirano tak na desate strance kazde ucebnice javy. Vzhledem k tomu, ze nastroje na kontrolu kodu uz dnes umeji vyskyt takovych veci detekovat, melo by se to asi v novem kodu uz vyskytovat spis vyjimecne. Jen jsem chtel upozornit, ze uz pouziti StringBuilderu je co do slozitosti oproti naivni implementaci takovym posunem, ze je jen zridka (cimz netvrdim ze nikdy) nutne pouzivat sofistikovanejsi reseni a ze ta se navic mohou v nekterych scenarich ukazat jako horsi.
-
Maaartin (neregistrovaný)
To ja bych to i obhajoval, muselo by to ovsem vypada takto
public static String createString()
{
StringBuilder str = "";
for (int i = 0; i < LOOP_COUNT; i++)
{
str += i + " ";
}
return str.toString();
}
Jak krasne prehledne a soucasne efektivne by se dalo psat, kdyby + a += fungovaly i pro StringBuilder. Byla by to si malickost udelat, kdyz uz se to udelalo pro String. Kdykoliv je lehci napsat horsi variantu, tak to dopada spatne. -
vyjde nám, že se pro získání takto krátkého řetězce musí v paměti přesunout celkem 478858990 znaků, tj. cca 912 MB!
Před pár lety jsem obdobnou situaci řešil v C programu, kam ale byla bota zanesena přímo původním autorem (nebyla skrytá v implementaci funkcí/metod druhé strany). Z přílohy e-mailu se vypouštěly znaky konce řádek (každý ~72. znak) tím stylem, že se (celý! to je zásadní) zbytek bufferu posunul o ten jeden byte níže a tak dále až ke konci pole. Úžasná kvadratická složitost, údajně cca 3/4 hodiny 100% vytížení procesoru a odhadem 0,5 TB přesunuté paměti (=> 2 * 0,5 TB kopií). :)
-
Pavel TišnovskýZlatý podporovatel
Neco podobneho jsem videl i u nekterych textovych editoru (radeji nebudu jmenovat), ktere pri vlozeni noveho znaku na uplny zacatek textu posunuly _cely_ text fyzicky v pameti o jeden bajt nahoru (doprava).
-
Pavel TišnovskýZlatý podporovatel
Zaprve je tato cinnost zbytecna, protoze existuji mnohem lepsi datove struktury, jak reprezentovat textovy soubor v pameti.
Zadruhe, coz se nezda, je presun pole bajtu o jediny bajt nahoru velmi pomaly postup, protoze se presunuje odzadu, coz znici prakticky cely obsah vyrovnavaci pameti a vsechny k ni pridruzene vymazlene algoritmy na nacitani dat dopredu atd.
-
JVM != GCC -O3 (neregistrovaný)
Ad "Druhou nevýhodou – i když méně závažnou – je to, že v mnoha případech může být neustálá změna hodnoty počitadla referencí výpočetně náročná, zejména kvůli nutnosti jeho synchronizace mezi všemi vlákny, které úloha používá (a navíc s vláknem či více vlákny samotného správce paměti), protože zvýšení počitadla o jedničku, snížení počitadla o jedničku a současný test na jeho nulovou hodnotu nebývají na současných procesorech atomické operace."
Vyjdeme-li z předpokladu, že x86-64 je jeden ze současných procesorů, pak bez studování manuálů bych to viděl takhle:
lock add qword ptr [rbx], 1
xor rax, rax
mov rdx, -1 ;-1 znamena ze uz se objekt uvolnuje
lock sub qword ptr [rbx], 1
cmpxchg8b [rbx], rdx
test rax, rax
jz UvolniObjektSice by se s cmpxchg dala udělat podivná konstrukce s testem na 1, ale není třeba.
Jde o úlohu s minimální výpočetní náročností. Jiná otázka je, jak ji kdo naimplementuje.
-
Hm, co ta race condition (mezi sub a cmpxchg může něco přijít) ? Naštěstí se dá snadno opravit (lock dec a ihned test na flags).
Ale je pravda, že většina moderních procesorů něco takového má, sparc třeba až od 64 bitů, ale přece.
Blbé je, že zrovna x86/x86_64 implementace je extrémně pomalá kvůli lockování sběrnice. Ostatní procesory používají obvykle load_exclusive a store_exclusive, která jen pasivně zkontroluje, zda mu lock někdo neshodil. Kód je pak delší, ale při srovnání s obyčejným increment stejně rychlý. To už je ale lehce OT.
-
JVM != GCC -O3 (neregistrovaný)
cmpxchg provede zápis v případě, že je na [rbx] nula, původní hodnota se vrátí v rax. Takže jestli dojde k přerušení kódu mezi sub a cmpxchg, a někdo změní reference counter, tak nebude platit podmínka pro jz.
lock dec a pak skok podle flags by byla race condition. Navíc jsou dec a inc pomalejší než sub a add. dec a inc nastavují méně příznaků, takže procesor musí čekat - proto se ++ překládá jako add ,1
Zamčení sběrnice je sice pomalé, ale když se nedělá často... protože když se taguje adresa, tak se to musí někde jinde zaplatit testem při přístupu k adrese, jestli náhodou není tagovaná.
Ale spíš bych u příkladu s grafem článku vyzdvihl, že jde o problém způsobený Javou. Dejme tomu, že z nějakého důvodu často přiřazuju referenci na objekt grafu a měním reference counter - nevyhnutelně dělá JVM, protože Java je tak navržená. Místo toho by bylo lepší mít vedle grafu ješět seznam objektů grafu a dokud objekt reprezentující část grafu z grafu nevyřadím, tak mu neměním reference counter. Akorát zavolám _AddRef a _Release při přidání a odebrání do/z grafu/uvolnění grafu z paměti - takle by to šlo udělat např. v C, C++ a Object Pascalu - všude, kde jsou pointery a dají se kopírovat bez volání metod (v C++ bez smartpointerů a v Pascalu s Move, nebo s přetypováním interface na pointer).
-
"měním reference counter - nevyhnutelně dělá JVM, protože Java je tak navržená."
Není pravda, Java je navržená tak, aby reference counting nepoužívala, viz článek.OT: Ten přístup v Pascalu je dost WTF: http://programujte.com/?akce=diskuze&kam=vlakno&tema=12533-muze-byt-instance-rozhrani-necim-jinym-nez-tobject-em-#100529
-
Ještě na to koukám, a je pravda, že ten update na -1 to zachrání. Nicméně, ten lock dec (či lock sub, z hlediska funkčnosti je to jedno) race condition (taky) nemá a je o jeden hodně drahý lock rychlejší.
K té druhé části - já bych řekl, že jde o problém způsobený dnešní komplikovanou architekturou SW. V případě reference count GC se dají použít další work-aroundy jako weak reference či grupování referencí, případně na aplikační úrovni, kdy destruktor "hlavního" objektu zničí cross reference své vnitřní reprezentace. Ale speciálně v případě modelování business objektů reálného světa, k čemuž se Java používá asi nejvíc, se těm cyklům dá vyhnout hodně špatně. Takže proto padla volba na sofistikovaný GC, který má holt i nějaké (velké) nevýhody.
-
To sice taky může být jeden z důvodů, ale z velké části je to IMHO jinde. Ono je to prostě více práce (zvlášť jsou-li tu nějaké komplikovanější závislosti) a někdy se to nevyplatí. Je to trochu jako tvrdit, že to jde z kopce, když máme paměťové cache, protože to lidé neumí optimalizovat ručně.
Navíc nelze jednoznačně tvrdit, že s GC to je pomalejší - dost to závisí na kvalitách GC a na tom, co tam chcete provozovat. Samozřejmě, většinou lze důkladnou ruční optimalizací dosáhnout vyššího výkonu, ale "na to jsou Cčkoví 'programátoři' příliš líní a neschopní". (Prostě podle 20/80 se to většinou hluboce nevyplatí.)
-
JVM != GCC -O3 (neregistrovaný)
Samozřejmě, nelze předpokládat, že programátor v C je automaticky dobrý programátor. Pointerová aritmetika dokáže zvýšit výkon, ale musí se to umět a vědět kdy. Jenomže, základ je v tom, jaký algoritmus dokáže programátor vymyslet/zvolit. A když vymyslí něco, co je pomalejší než naivní řešení s GC, tak je to s GC rychlejší. Což mi připomíná místní diskuze, zda se vyplatí jít studovat VŠ, kde člověka naučí myslet:)
No, a nakonec do toho vstoupí i ekonomické hledisko, protože se to musí nějak zaplatit.
Ohledně optimalizace, důkladnou optimalizaci má dělat překladač. Programátor by měl mít dobré návyky už při psaní kódu, které překladači pomohou. Např. kolik z programátorů ví, který z následujících dvou příkladů je rychlejší a proč? Stačí bez použití SIMD. Mimochodem, příklad není OT, protože to vychází i pro bytecode.
int count;
...int sum=0;
zda
for (int i=0; i<count; i++)
sum += hodnoty[i];anebo
i=count;
do {
i--;
sum += hodnoty[i];
} while (i);Nemluvě o tom, kolik programátorů nezná pravidla predikce skoků, ani kdy použít ternární operátor a kdy skok. Protože když to napíšou proti nim, tak JVM může být rychlejší. Ale to už se dostávám do další odpovědi.
-
Roman (neregistrovaný)
Jediné, čo mi napadá je to, že v 2. prípade sa test na opustenie cyklu robí jednoduchým testom na nulu, kdežto v prvom prípade ide o porovnanie dvoch hodnôt. Ostatné operácie sú si zrejme rovnocenné.
V 2. príklade ale MUSÍ byť zabezpečené, že bude count>0, inak môže dôjsť k nepríjemnému "Access violation". -
Porovnání s nulou (druhý případ) je rychlejší. Ale řešení bych viděl spíše v tom, že se navrhnou takové prostředky, které toto umožní přenechat kompilátoru nebo běhovému prostředí. Stejně tak to umožní na multicore paralelizovat. Vzpomínám si na něco takového v .NETu, co jsem viděl.
Ale ostatně i toto by mohla JITka (nebo dokonce i statický kompilátor) optimalizovat. Udělá průzkum, že tělo cyklu nemá další vedlejší efekty kromě zvyšování sum, a že sčítání je komutativní, takže to může udělat v opačném pořadí.
-
JVM != GCC -O3 (neregistrovaný)
Takže poslední příspěvek dne:
Mimo OPascal, se for cyklus obvykle přeloží pomocí dvou skoků:
cmp rcx, [poceiteraci]
jge koneccyklutelocyklu
add rcx, 1
jmp zacatekcyklu-cmpUvedený do-while bude vypadat následovně:
telocyklu
sub rcx, 1
jnz telocykluTakže je potřeba méně instrukcí a méně položek v Branch Target Bufferu, které mohu dál v cyklu využít. U bytecode je díky zásobníku rozdíl v počtu instrukcí větší než u x86.
Ohledně paralelizace, např. pro count=100000 nemá na x86-64 smysl používat více vláken pro uvedený příklad [oficiální stanovisko MS/Intel k nové knihovně concurrency].
Protože bylo použité pole, a ne pointerová aritmetika, např. GCC s autovektorizací by mohlo použít SIMD instrukce.
V bytecode se s tím bude pracovat po položkách, takže JIT uvidí práci se zásobníkem. AFAIK, mu to nedojde - projeví se výhoda GCC, že jasněji vidí, co měl programátor na mysli.
Ad přenechání práce, např. OpenMP pro výpočetně náročnější smyčky.
Pěkný víkend všem!
-
ded kenedy (neregistrovaný)
<cite>Mimo OPascal, se for cyklus obvykle přeloží pomocí dvou skoků...</cite>
mas to z overenych zdroju? treba GCC i s -O0 to prelozi jenom s jednim skokem a s -O1 z toho vyleze presne kod ktery popisujes:
movl $0, %edx movl $0, %eax .L4: addl -4000(%ebp,%edx,4), %eax addl $1, %edx cmpl $1000, %edx jne .L4
takze resit for/while neni nic nez predcasna optimalizace a vlastne pitomost.
-
Zásobník u bytecode - myslíš operand stack? Nemyslím si, že by JIT byla tak tupá a překládala operace s operand stackem doslova. Ale možná se mýlím.
K paralelizaci: ano, sčítání je jednoduché, ale existují složitější operace, které se začne vyplácet paralelizovat dříve. Je zase pravda, že tam by případná optimalizace byla již náročnější, protože najít algoritmicky důkaz komutativity není až tak jednoduché.
-
Tento zdroják:
public class Foo{ public static void main(String...args){ for(int i=0; i<10; i++){ System.out.println("."); } } }Se přeloží takto:
public static void main(java.lang.String[]); Code: 0: iconst_0 // na operand stack přidej nulu 1: istore_1 // vem položku z operand stacku a ulož ji do proměnné č. 1 2: iload_1 // do operand stacku dej hodnotu proměnné 1 3: bipush 10 // do operand stacku dej 10 5: if_icmpge 22 // pokud první hodnota je větší než druhá (i>10), skoč na 22 8: getstatic #2; //Field java/lang/System.out:Ljava/io/PrintStream; 11: ldc #3; //String . 13: invokevirtual #4; //Method java/io/PrintStream.println:(Ljava/lang/String;)V 16: iinc 1, 1 // zvyš proměnnou č. 1 o jedničku (i++) 19: goto 2 // skoč na 2 22: return
Udělat překlad ze stack-oriented kódu do register-oriented kódu je IMHO celkem hračka pro JIT (i když nějaký čas to zabere a Dalvik je asi proto register-oriented). A jinak je to taky pomocí dvou skoků a nevím, co by se na tom dalo ještě nějak rozumně optimalizovat, kromě posledního přičtení, což je celkem směšná optimalizace.
-
JVM != GCC -O3 (neregistrovaný)
Překlad stack-oriented do register-oriented není problém, když se instrukce jako třeba anewarray nebo monitorenter přeloží s call/int. Pokud to ale má být optimalizovaný kód, tak už to hračka není - viz třeba http://www.cis.nctu.edu.tw/~wuuyang/papers/bytecode2X86.BRIEF.pdf
Jinak, dejme tomu, že se nebude počítat suma, ale třeba tohle:
counter1 = counter2 = counter3 = 0;
for(int i=0; i<n; i++){
if (values[i] < threshold1) counter1++;
if (values[i] > threshold2) counter2++;
if (values[i] == threshold3) counter3++;
}Když to bude celočíselná aritmetika, tak se to dá v x86 přepsat slušně bez skoků. S floating-point už ale skoky narostou. Pointa je v tom, ušetřit skoky na řízení vykonání počtu iterací cyklu, abych skoky mohl použít uvnitř cyklu - to dělá to urychlení.
-
Odkazovaný článek bude asi dobrý jen pro obecnější věci, přecejen datum vysázení (Čt 3. březen 2005, 17:34:28 CE) z něj nedělají něco aktuálního.
Dovolím si jednu citaci faktu, který lze pro dnešní situaci snadno vyvrátit pomocí přepínače -XX:+PrintCompilation: "In our current implementation, all the standard Java packages remain in bytecode form and all user packages are translated into X86 assembly code."
-
U JIT vs. AOT dost záleží na způsobu použití. A pokud je hlavním cílem rychlost startu (nebo rychlost ihned po startu) nebo malý memory footprint (např. pro spuštění aplikace Eclipse na stroji s malou pamětí nebo pro běh J2ME aplikací na mobilu*), pak AOT má smysl. Pokud chceme server, tak spíše překousneme delší dobu startu, přikoupíme něco málo RAM a použijeme radši JIT (a přepínač -server, je-li potřeba**), ať to běhá svižně.
*) Využívá Sony Ericsson na hloupých mobilech.
**) Např. na 64b strojích s HotSpotem v této chvíli potřeba není, protože je to jediná možnost. Ale na druhou stranu, do budoucna se hodí, bylo by nepříjemné, kdyby nějaký update Javy, který by přidal podporu pro 64b client, takto zpomalil server. Ale myslím, že je možné tento přepínač i někde vydefaultit.
-
Maaartin (neregistrovaný)
Hezky... ale ja to kdysi davno meril a vyslo mi to naopak (a ne nevyrazne). Zduvodneni co jsem si vymyslel: Ta smycka dolu je sama o sobe rychlejsi, ale pak tam mame jeste pristup do pameti. Pri smycce nahoru funguje prefetching, procesor preventivne natahne dalsi cache line, pri smycce dolu ne. Je to uz peknych par let, uz si ani nevzpomenu co to bylo za procak a dokonce ani jazyk (ale skoro jiste bud Java nebo C++).
-
JVM != GCC -O3 (neregistrovaný)
Pointa je v tom, že tělo cyklu může být složitější, a že řízením takového cyklu zaberu méně místa v BTB procesoru. Za chvíli napíšu ještě jeden shrnující komentář s příkladem.
Součet prvků pole by pak s prefetchingem zjednodušeně mohl vypadat takhle:
lea rax, pole
xor rdx, rdx
mov rcx, polecountskok:
add rdx, qword ptr [rax]
add rax, sizeofalignedprvekpolesub rcx, 1
jnz skok -
Pavel TišnovskýZlatý podporovatel
Maji se ty reseni porovnat pro nejaky idealni stroj, kde je RAM skutecne random-access (pristup ke kazde bunce za stejny casovy interval) nebo s prihlednutim k tomu, ze dneska je mezi CPU a RAM jeste aspon dvouurovnova cache?
-
Pavel TišnovskýZlatý podporovatel
sice trosku OT, ale toto je presne ten typ problemu, kde by se nemusely psat smycky vubec, ale dalo by se pouzit nejake apply(), reduce() apod. - proste by se primo reklo, CO ma algoritmus delat (spocitat sumu) a ne otrocky psalo, JAK to ma udelat (laskave vybirej postupne jednotlive hodnoty a scitej).
Protoze skutecna implementace by zalezena na prekladaci a runtime, treba by pouzil MMX, vektorove instrukce atd.
-
Nemohl jsem si nevzpomenout na jeden článek: http://scribblethink.org/Computer/javaCbenchmark.html
Pravda, je sice trošku starší, ale odpovídá na určité mýty ohledně výkonu, GC a JIT. Zvlášť doporučuji si přečíst část "Garbage collection- is it worse...or better?" (včetně "The cost of missing the cache").
Myslím, že sice konkrétní čísla a poměry z toho článku budou dnes již značně outdated, nicméně obecné principy se až tolik nezměnily. Jedna z věcí, které už (díky escape analysis) nebudou aktuální, je "For example, programs written with the thread-safe Vector class are necessarily slower (on a single processor at least) than those written with the equivalent thread-unsafe ArrayList class.". EScape analysis totiž dovede odstranit synchronizaci, není-li potřeba.
-
JVM != GCC -O3 (neregistrovaný)
Např. v "Garbage collection- is it worse...or better?" píšou
a) the allocator looks for an empty slot of the right size, then returns you a pointer. b) This pointer is pointing to some fairly random place.
With GC, a) the allocator doesn't need to look for memory, it knows where it is, b) the memory it returns is adjacent to the last bit of memory you requested.
To by musel být správce paměti, s prominutím, blbec, anebo pod tlakem jiných požadavků. Paměť se totiž dá spravovat např. ve formě seznamu volných bloků různých velikosti, takže alokátor udělá pop nad seznamem.
Ad synchronizace, není-li synchronizace potřeba, proč ji tam budu psát? Jenomže psaní rychlých paralelních programů je daleko náročnější než používání pointerů. Tady by byl dobrý příklad celočíselný semafor napsaný v Javě s tím, že se pak člověk podívá na všechny vrstvy, které leží vespod (nad kterými je semafor v Javě implementovaný).
Jiná principíálně zajímavá věc je, proč je Java údajně rychlejší než C. Řada věcí JVM je psána ručně v assembleru. Zářným příkladem je system.arraycopy. Takže je pak poněkud zavádějící tvrdit, že je Java rychlejší:)
Viz
http://java.sun.com/performance/reference/whitepapers/6_performance.html#2
http://www.martinrinehart.com/articles/repz.htmlBenchmarky, jak je Java rychlejší než C, jsou známá věc, i pro jejich nedostatky. Např. viz http://www.ibm.com/developerworks/java/library/j-jtp02225.html#2.0
Když JVM překládá bytecode do strojového kódu, má k tomu méně informací než GCC z C kódu. Proto GCC vždy vygeneruje rychlejší kód toho, co se v C chtělo. Jenomže se to zaměňuje s tím, co si člověk dělající benchmark poručil přeložit.
-
K synchronizaci: To ale znamená mít variantu se synchronizací a variantu bez synchronizace a vždy volit tu správnou.
K rychlosti: hlaví je, že je problematické obecně tvrdit, co je rychlejší.
Když JVM překládá bytecode do native code, může využít i aktuální stav (a zkompilovat to jen pro něj), čímž může například inlineovat i virtuální metody. U GCC je to nemyslitelné.
-
JVM != GCC -O3 (neregistrovaný)
Synchronizovat se musí:) Ale jak říkám, tohle je náročné vymyslet, aby to vždy fungovalo správně.
Jj, JVM dělá runtime profiling, a pak např. loop unrolling, nebo mění podmínky skoků. Ale ještě jsem neviděl, že by Java byla alespoň jednou rychlejší než C, pokud tomu Céčkař skutečně rozuměl. Myslím runtime, ne dobu vývoje programu.
Trik s runtime profilingem je ještě v tom, že se program vlastně naučí na nějaká data. Jenomže pokud to jde, tak ta data nejsou náhodná a tudíž pro ně lze zapsat větvení C programu odpovídajícím způsobem. Pokud se ovšem programátor zabýval analýzou vstupních dat. A pokud jsou data skutečně náhodná, podle Intelu a AMD se na ně má používat cmov, což v Javě nemá ekvivalent. Bytecode místo toho skáče a dělá zmatek v tabulce predikce skoků procesoru.
Jo, a virtuální metody jsou dobrý příklad, jak lze zpomalit kód, když se používají nadměrně.
-
Celé je to víceméně o tom, že v C to musí optimalizovat programátor, zatímco v Javě se o to stará většinou JIT. A pokud programátor v C má optimalizovat, tak to ještě více zvýší dobu vývoje, cenu práce a ("zadaří"-li se) chyby.
Samozřejmě, ne vždy je Java vhodná. Mám-li aplikaci, která se má rychle spustit a má být ihned plně připravena, pak asi nezvolím Javu nebo použiju její AOT implementaci. Na serveru mi o něco delší start nevadí a nevýhody jsou obvykle zastíněny výhodami. -
Pavel TišnovskýZlatý podporovatel
jj, a jde to opakovat jeste o level niz, protoze cecko nema vsechny vyjadrovaci schopnosti pro popis operaci CPU, tak dobry programator dokaze prekonat ceckovy kod v assembleru (i kdyz je to rok od roku omnoho slozitejsi, jak se CPU stavaji vice bloated a prekladace lepsi).
-
JVM != GCC -O3 (neregistrovaný)
To ano, virtuální metody mají své plus. Jen je dobré si při návrhu uvědomit i jejich cenu.
Procesor má tzv. Branch Target Buffer a několik posledních skoků si poznačí, jestli se skočilo. Když se potom snaží vykonávat instrukce dopředu a narazí na známý skok, tak se podívá do BTB a odhadne, další instrukci, kterou zkusí udělat dopředu. Pokud se v odhadu netrefí, tak předem vypočítané zahodí a tím se zdržuje. Či-li, pokud jsou na vstupu dostatečně náhodná data, tak procesor často tipne špatně.
Dejme tomu, že máme for cyklus s řídící proměnnou i. Pak je kód
add i,1
cmp i, [pocet]
jl zacatekcykluProtože i nejsou data, tak je podmíněný skok predikovatelný a procesor nezahazuje dopředu vykonané instrukce (až na poslední iteraci cyklu). Proto když se použije cmov, tak tam není cyklus a BTB je volná na predikovatelné podmínky.
AFAIK Intel měl, asi ještě i má, 2 bity na skok. Takže na dostatečně náhodných datech bude nepořádek oscilace mezi 01 a 10.
Ovšem, to už jsme značně OT:)
-
ondra.novacisko.cz (neregistrovaný)
Přemýšlím, jak souvisí predikce skoků s voláním virtuálních metod.
Volání virtuální metody se většinou realizuje pomocí
[code]
call [ecx]
[/code]Tahle instrukce se dá celkem jednoduše provést v superskalárním režimu, za předpokladu, že se obsah na ecx neměnní, což u tabulek virtuálních funkcí nehrozí. Jediná režie tady je pouze v ukládání návratové adresy do zásobníků.
Inlinování virtuální funkcí je pěkná věc, za předpokladu, že těch kombinací co se kam inlinuje je málo. Jakmile ale dojde docházet v JVM cache na tyhle fragmenty, začne mít C++ zase převahu.
-
Maaartin (neregistrovaný)
> Volání virtuální metody se většinou realizuje pomocí...
Tohle je nejobecnejsi ale tez nejpomalejsi varianta. Kdyz to jde, tak JIT virtualni volani uplne eliminuje, pripadne (kdyz jsou 2 moznosti) ho zmeni zmeni na jednoduchy podmineny skok. Kdyz je vice moznosti a jedna z nich vede, pak se to dela tez (kdyz se uhodne, jde to rychle, kdyz ne, tak smula).
> Tahle instrukce se dá celkem jednoduše provést v superskalárním režimu, za předpokladu, že se obsah na ecx neměnní, což u tabulek virtuálních funkcí nehrozí.
Ted uz duvod nevim, ale tohle je pomaly a kazdy se tomu snazi vyhnout.
-
YF (neregistrovaný)
me by jenom zajimalo - o co ti sakra de - pokud dostane clovek dost casu a dostatecnou motivaci optimalizovat do absolutnich detailu tak bych to chapal - nedovedu si ale predstavit v dnesni dobe miliard knihoven cloudu a distribuovanejch systemu ze se budu zabyvat superoptimalizaci na urovni metod - tyhle priklady patri do akademickyho sveta - jsou pekny ale je to tak na to aby si clovek honil triko na rootu v diskuzich - takova je realita - od optimalizaci takovychdle casti kodu necht je tu kompiler a specialisti v tomto oboru - znalost toho co je pod tim je samozrejme vzdy plus ale tezko to v dnesni dobe vyzadovat - protoze pak se ti lehce stane ze zapomenes ze mas vic jader a l2 cache ze jo ...
-
> takže alokátor udělá pop nad seznamem.
Alokator s nejakou slozitosti najde blok vhodne nebo vetsi velikosti, pripadne ho rozdeli a zbytek zatridi zpet. Je to proste netrivialne vic nez posun pointeru a vraceni predchozi hodnoty.Ad synchronizace - proc ji vubec resit, kdyz to muze rozhodnout JIT. Nemyslim to ted doslova a dogmaticky, ale obecne - proc resit veci ktere automat dokaze rozhodnout dostatecne dobre, rychleji a levneji?
Rychlost javy oproti C (a opet obecne jednoho proti druhemu). Me je prece jedno, diky cemu to je rychlejsi a zda je ta optimalizace napsana v asm. Dulezite je, ze kdyz to napisu v jave, tak jsem musel resit petinu veci a je to dostatecne rychle.
> Když JVM překládá bytecode do strojového kódu, má k tomu méně informací než GCC z C kódu
Spis bych rekl - C muzete napsat tak, ze konkretni verze GCC provede pro konkretni CPU konkretni optimalizaci. To se mozna hodi pro psani ovladace gfx nebo 10GB sitovky, ale obecne takovy pristup povazuju za zcestny. JIT ma oproti GCC info o tom, jak to zrovna ted v tom programu bezi, na jake to je architekture, jake implementace rozhrani jsou pritomny, jak tam behaji thready atd. Proto muze delat optimalizace na uplne jine urovni nez GCC a muze je udelat vzdy a vsude. Az za dva roky vyjde uplne novy cpu, ktery bude mit uplne jine casy zpracovani instrukci, skoku atd., tak vy pujdete, prepisete svuj kod v C, prelozite, rozeslete. Java programator se na to nejspis vykasle, protoze se to casem projevi v JIT a bude to fungovat na vsech programech dostatecne dobre.Dale musim rict, ze jakmile zacne nekdo mluvit o tom, ze nekde usetril jmp, tak saham po revolveru (rozumej zacnu byt ostrazity). Uz jsem mnohokrat narazil na pripad, ze nekdo usetril par taktu ve vnitrnim cyklu, ale jaksi mu unikl celkovy design aplikace. Pak se mu to vola 100x misto aby to zavolal jednou, ale je stastny, ze to dal na 95 taktu misto 100. Me se mnohokrat potvrdilo, ze to co stravim designem se mi mnohokrat vrati v tom, ze muj v podstate tupy a trivialni kod bude chutnat optimalizatorum na vsemoznych urovnich, nebude v nem tolik chyb a ve vysledku bude levny a pritom dost rychly pro dany ucel. Kolikrat mi pripada, ze s tema objektama a virtualkama vylozene provokuju, ale ono to holt funguje.
-
JVM != GCC -O3 (neregistrovaný)
Ad alokator, ale co potom fragmentace paměti?
Ad synchronizace, souhlasím s tím, že je automat dokáže rozhodnout levněji.
Ad rychlost, ano, vývoj v Javě je levnější a méně náročný. Pokud je ovšem daná úloha řešitelná v Javě. Např. díky rychlosti/pomalosti výpočtu a paměťovým nárokům.
Ad překlad, to jest úsměvné:) Zejména ta pasáž o časech instrukcí. Bez urážky, ale instrukce mají nějakou datovou závislost - např. rozdíl v rychlosti mezi
sub rax, 1
jnza
dec rax
jnzTakže argumentace časy je zde zcestná. Navíc argumentace časy naznačuje i zmatek v pochopení rozdílu mezi x86-64 a VLIW jako IA-64 (proč se tam překompilovává).
Ad přepisování kódu v C, malý kvíz. Jaké jsou nutné kroky pro spuštění 32-bitového programu, např. pro Wokna, tj. psaného pro protected-mode, na 64-bitovém procesoru? Buď ho spustím v compatibility mode, anebo překompiluju pro long-mode.
Nějaké přepisování je totiž vyjímka, a obvykle kvůli použití něčeho specifického. A nebo prasárny v kódu, kdy se přetypovával pointer na 32-bitový int. A že nemusel.
Ad revolver, vžyť já se taky nehodlám zastávat člověka, který odflákne analýzu a návrh programu.
-
Ad fragmentace - ted nejak nerozumim. Fragmentace je problem tradicnich alokatoru, ktere ji musi nejak resit a to je zpomaluje. JVM to zmakne jako vedlejsi efekt pri GC.
Ad preklad - slo mi obecne o pristup. Bud napisu hustej C kod, ktery se presne dle mych predstav prelozi konkretni verzi GCC pro konkretni cpu a tam to bude silene rychly (sem tam se usetri par taktu (provokace)). Pak to ale musim prelozit pro kazdy cpu zvlast, pripadne ten kod upravovat.
Nebo to napisu "tradicne" bez ohledu na specialitky te ktere platformy, ten kod bude jednodussi a citelnejsi. V tom pripade bych ale rekl, ze GCC ma radove stejne mnozstvi informaci jako java pri prekladu do bytecodu a nasledny JIT.Ja nejsem odbornik na specialitky toho ktereho cpu, v asm jsem psal naposled pred 15 lety, takze mi ted zbyva ten druhy pristup. Kdyz jsem si delal testy pro konkretni problemy ktere jsem resil, tak jsem zjistil, ze proste nezvladnu v C napsat jednoznacne rychlejsi program, natoz aby to vyvazilo narocnejsi vyvoj. Proto usuzuju, ze to GCC nema vic informaci, ktere muze vyuzit k optimalizaci.
-
ondra.novacisko.cz (neregistrovaný)
Co takové C++ a šablony? Tam už je prostor pro optimalizaci více. Třeba při spojení dvou nesourodých objektů může dojít k větší optimalizaci, než zvládne bytecode.
Samozřejmě, JIT s optimalizací a s dostatečnou cache pro přeložený kód může dosáhnout stejně dobré optimalizace i dynamicky a v tom je jeho síla.
Jenže předpokladem je právě ta cache.
-
ondra.novacisko.cz (neregistrovaný)
Nechci nikomu brát vítr z plachet, ale jakýkoliv LOCK způsobí serializaci instrukcí a synchronizaci jader, takže ve výsledku ta instrukce trvá zhruba 10x pomaleji, než když instrukce bez locku.
Proto třeba já u objektu s počítanými referencemi mám vždy navýběr, zda se bude počítat s MT pointerem nebo ST pointerem. I v MT prostředí hodně používám ST pointery, pokud objekty neopustí dané vlákno, nebo mám zaručeno, že jiné vlákno v danou chvíli s nimi nebude pracovat.
Třeba sdílení stringů mám také pomocí ST pointeru a je vyloženě zakázáno předávat řetězce do jiných vláken jen pomocí proměnné. Musí se na to zavolat metoda "isolate()", která vytvoří kopii řetězce pro jiné vlákno... což bývá často rychlejší, než pracovat s LOCKy.
Zlaté pravidlo MT programování zní... sdílejte co nejméně. Například správce paměti mám per thread, aby se maximalizovala propustnost.
-
ondra.novacisko.cz (neregistrovaný)
On to bohužel není jen LOCK. na NUMA a jiných architekturách (nCube) hodně sebere synchronizace pamětí, pokud každý procesor má k jedné paměti blíže než k ostatním. K efektivnímu MT programování opravdu nema cenu řešit zamykání na nejnižších úrovních, ale co možná nejvíc držet data odděleně a škálovat práci na vyšších celcích s klasickými mutexy a semafory.
-
JVM != GCC -O3 (neregistrovaný)
Tak ještě na závěr malé shrnutí.
1. Proč jsem sem psal něco s assemblerem. Nešlo o proovokaci, ani o výplod přeoptimalizovaného mozku:) Prostě jsem se jenom pozastavil nad ocitovaným blokem z článku, že přičítání/odčítání může být náročná operace.
A protože většinou JVM stejně běží na x86, tak jsem použil x86 instrukce, abych ukázal, že to tak být nemusí. Že je to v JVM implementováno jinak, to už je jiný topic.
2. Moderní procesory, a opět viz fakt, že JVM nejčastěji běží na x86, se snaží vykonávat kód dopředu. K tomu potřebují předpovídat skoky, jak už je vysvětleno někde v komentářích. Eliminace skoků, případně využití předvídatelných skoků proti cmov instrukcím/setbl konstrukcím ternárního operátoru pro 32bitů, je klíčem k rychlosti - viz způsob optimalizace ICC např. oproti GCC|MSVC. U bytecode se můžeme bavit jen o skocích, ale i tam to má (alespoň teoreticky) smysl.
Takže závěrečný příklad z praxe. Dostal se mi do ruky Deep-First Search napsaný v Javě se zbytečnými skoky. Když jsem ho doslova přepsal do C, tak bylo většinou rychlejší. Ale na některých datech, když cca méně než 20% uzlů vstupního grafu byly listy, tak byla Java rychlejší. Tady to má souvislost s jedním z komentářů, kde padnul názor, že je lepší psát tupý kód, který chutná překladači provádějícímu optimalizace.
A jak to pokračovalo dál? JVM evidentně dělalo runtime profiling a přepisovalo skoky podle naučené pravděpodobnosti. Jenomže tu se mohlo naučit jenom u těch cca méně než 20%. Takže Java se zbytečnými skoky začala po nějaké době dávat téměř stejné výsledky jako Java bez těch zbytečných skoků.
Když jsem vzal C program a odstranil všechny skoky, tj. podmínky, které tam nemusely být, tak Java na některých datech stále porážela C. Chápu, že něco takového vede některé lidi k úvaze, že JIT je lepší než GCC -O3.
Jenomže, když jsem využil znalost Branch Target Buffer procesoru a přidal podmínku, která tam nemusela být, tak už byl program z C vždy rychlejší než Java. Ve většině případů to urychlení bylo větší než 10x. (Ano, BFS běží ještě rychleji díky absenci rekurze.)
Plus, na řadě dat Javě došla paměť - a měla jí dost.
Takže závěr může znít: čas vynaložený na optimalizaci v Javě snadno může být ztraceným časem, protože JVM si to stejně udělá po svém. Optimalizace v C vhodnou konstrukcí cyklů a podmínek se určitě vyplatí, ale chce to znalosti, které každý nemá.
Je to "levnější vývoj v Javě" vs. "efektivnějíš kód z C".
Má smysl vědět, co JVM dělá, aby program neběžel zbytečně příliš dlouho. Ale pokud je nutné mít efektivní program, pak je prvním krokem k optimalizaci změna jazyka a tím pádem i překladače.
-
Vpodstatě závěr je to, co jsme tu už říkali - jde jen o to, co potřebujeme. Pro ruční optimalizace je samozřejmě výhodnější jít blíže k procesoru. A někteří hardwaráři by se na to ještě dívali s pohledem "Co to je? Vždyť by bylo mnohem efektivnější si navrhnout vlastní hardware!" Ale nejdůležitější je moct si říct "Mohl jsem to sice napsat v těchto ohledech (cena, následná údržba, rychlost, ...) lépe, ale zase by se to jinde projevilo (cena, následná údržba, rychlost, ...) a nevyplatilo by se to."
Jinak článek by mě taky zajímal. Zvlášť to zrychlení pomocí zbytečné podmínky,
-
JVM != GCC -O3 (neregistrovaný)
V podstatě šlo o to, že se buď udělal call, nebo ret. K tomu rozhodnutí se dospělo. Takže nebylo nutné přidávat "zbytečný" extra test. Jenomže ten extra test mohl zavolat ret dřív, pokud už to bylo jasné. Takže se ušetřily jednak instrukce a jednak se instruction pointer často pohyboval v blízkosti skoků. On je tam totiž ještě limit na délku kódu, ve kterém se udržuje historie skoků - tohle mi přišlo líp popsané v manuálu od AMD než od Intelu.
-
ded kenedy (neregistrovaný)
Jenomže, když jsem využil znalost Branch Target Buffer procesoru a přidal podmínku, která tam nemusela být, tak už byl program z C vždy rychlejší než Java. Ve většině případů to urychlení bylo větší než 10x. (Ano, BFS běží ještě rychleji díky absenci rekurze.)
tak takhle by se teda opravdu programovat nemelo. staci, abys program spustil na necem, kde bude branch prediction udelana jinak (novejsi nebo starsi verze cpu), zkusil program prekompilovat jinde (SPARC, ARM, ...) nebo pouzil jiny prekladac a vsechny tvoje optimalizace nejenze budou k nicemu, ale muzou byt hrube kontrapudiktivni.
Optimalizace v C vhodnou konstrukcí cyklů a podmínek se určitě vyplatí, ale chce to znalosti, které každý nemá.
to je pravda... o par postu vys tu jeden expert tvrdil, ze for cyklus se preklada pomoci dvou skoku a pritom ten smejd gcc si to skompiloval posvem jenom s jednim skokem.
-
JVM != GCC -O3 (neregistrovaný)
Jak bylo uvedeno někde výše, podmínka je zbytečná v tom smyslu, že pokud tam nebude, tak program bude fungovat taky.
Takže druhé možné přídavné jméno téhle podmínky je spekulativní. Když se vykoná, ušetří se čas vykonává následujících instrukcí, ze kterých se její efektivita zaplatí i na procesoru bez branch prediction.
ČLÁNKY DO MAILU