Názory k článku
Monitorování procesů a správa paměti v JDK6 a JDK7 (2)

Nejčastější použití StringBufferu/strin­gBuilderu 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.Strin­gBand.

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.

Mate 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 ;-)

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.

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í). :)

Zapomněl jsem uvést velikost vstupu (ačkoli jde zpětně odvodit z uvedených nároků): 9 MB.

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).

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.

Ty algoritmy bývají většinou tak vymazlené, že umí i načítání odzadu (a často i stride). :-)

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 UvolniObjekt

Sice 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.

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

OK, Java nemá reference counter jako COM Woken - když byl dán příklad s Pascalem.

Ad Pascal, to spíš dotyčný rozhraní úplně nerozuměl. Jinak by měl procedure foo(const x:iinterface), anebo neměl x.Free, a zkusil použít GetInterface/Qu­eryInterface u potomků IUnknown.

No spíš (jsem) to pochopil a snažil se ověřit správné pochopení na co nejabsurdnějším příkladě. Přijde mi to dost WTF. Ale to už OTujeme.

A jo, teď koukám na nick:) Tak jsem tam ještě dopsal jednu poznámku, ať to tady není OT.

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.

No, já osobně GC vidím v prvé řadě jako workaround reality, že mnoho lidí, prohlašujících se za programátory, by mělo obrovský problém napsat větší aplikaci a korektně v ní používat pointery - pokud by ji vůbec napsali:)

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í.)

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.

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".

Pro jednoduchost příkladu se předpokládá, že count>0, jinak by se cyklu předřadil if.

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í.

Takže poslední příspěvek dne:

Mimo OPascal, se for cyklus obvykle přeloží pomocí dvou skoků:

cmp rcx, [poceiteraci]
jge koneccyklu

telocyklu

add rcx, 1
jmp zacatekcyklu-cmp

Uvedený do-while bude vypadat následovně:

telocyklu

sub rcx, 1
jnz telocyklu

Takž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!

<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.

<cite>Mimo OPascal, se for cyklus obvykle přeloží pomocí dvou skoků...</cite>

Oops, záměna for () s while () {}.

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é.

Ad JIT, tím myslím, že javac to do bytecode napíše doslova, protože jinou možnost díky instrukcím bytecode nemá.

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.

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:+PrintCompi­lation: "In our current implementation, all the standard Java packages remain in bytecode form and all user packages are translated into X86 assembly code."

Spis bych rekl ze clanek je dobry na nic. Kde je naka myslenka, kde jsou vysledky? Staticka kompilace Javy existuje uz hodne dlouho, a mnohem lepsi. Oni nejsou ani v jednom pripade lepsi nez JIT, casto jsou 10x horsi.

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.

Ja nikde nepsal, ze AOT je na nic. Ten clanek je na nic, bo mele o AOT bez toho aby mel novou myslenku ci dobry vysledky.

Aha, špatně jsem pochopil "Oni nejsou ani v jednom pripade lepsi nez JIT, casto jsou 10x horsi.".

No, trošku málo jsem si to přečetl. Tam nejde o implementaci JIT, ale o implementaci AOT kompilátoru.

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++).

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, polecount

skok:

add rdx, qword ptr [rax]
add rax, sizeofaligned­prvekpole

sub rcx, 1
jnz skok

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?

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.

AFAIK, tohle jde de-facto s OpenMP a ConcurrencyRuntime.

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.

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.html

Benchmarky, 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é.

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.

Jj, je to tak. V C lze hlavní část optimalizace přesunout na programátora. Který, pokud to umí, dokáže naprogramovat lepší kód než automat. A pochopitelně je to dražší.

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).

Mohl bych se ještě zeptat, jak vypadá ten nepořádek v predikci skoků?
Jinak virtuální metody jsou důležité při redukci opakovaného kódu.

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 zacatekcyklu

Protož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:)

> 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.

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.

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
jnz

a

dec rax
jnz

Takž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.

Přesně tak, LOCK je opravdu hodně pomalý, i na moderních procesorech (Nehalem) to znamená 20–30 taktů navíc, u NetBurstu to bylo dokonce myslím přes 80.

To ani nemusí být žádná zvláštní architektura, stačí když má každý procesor (každé jádro) svoji cache a více se jich snaží přistupovat ke stejné řádce (cache-line bouncing). Dokonce ani nemusí přístupovat ke stejným datům, tam je potřeba dát pozor i na to, aby ta data nebyla moc blízko u sebe. :-)

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.

Nechcete o tom napsat clanek? Zajimaly by me detajly, jak presne vypadal kod...

Přidávám se...

I já o tom popřemýšlím:)

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,

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.

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.

A jak jinak by byla branch-prediction udělaná? Že by dokázala předpovídat více skoků a přesněji? Konkrétní detaily ať si udělá překladač. Já mu jenom vycházím vstříc znalostí obecně platných principů.

Njn s GCC, viz můj komentář tamtéž.

nechapes. nektere procesory nemusi mit branch prediction vubec, jine mohou mit udelanou primitivni predikci na zaklade toho jestli se jedna o skok dopredu nebo zpet. a kdyz tam budes cpat zbytecne podminky tak na nich ten vykon pujde do haje.

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.