Paměťová a výpočetní náročnost JVM vs .NET

[dustin]

Jo, hodnotové typy by se hodily, o tom žádná. Pár let to bohužel ještě potrvá (java 10?), ale dělá se na nich.

[Reklama]

[JSH]

To jsi na úrovni optimalizací, které tě až tak netrápí. Hlavně ta dnešní logika cache bude asi dost složitá.

Pokud mám problém s využitím procesorové cache, budu řešit efektivnější využití procesorové cache, a ne vytváření pole objektů tak, aby všechny objekty byly v paměti za sebou (už jenom proto, že do té cache se moc objektů nevejde).

Teda pánové. Já věděl, že je to s Javisty špatné, ale až takhle? To nevíte ani to, že přečtení pointeru tahá do cache 64B(8X tolik)? A že ta nejdůležitější a nejzákladnější zásada pro efektivní využití cache je naskládat objekty za sebe a neskákat zbytečně po pointerech?

[Kolemjdoucí]

To je pole referencí, ne?

V Javě je to pole objektů, Java nerozlišuje objekt a referenci.

Je to pole referencí a kdo bude tvrdit něco jiného tak ukazuje že Javě naprosto nerozumí! Objekty v Javě vznikají výhradně zavoláním konstruktoru (ať už pomocí new nebo reflexí) a reference na ně je možno přiřadit do libovolného prvku v tom poli (klidně i do více prvků tu samou referenci), nad tím kde v paměti JVM ty objekty naalokuje ale programátor v Javě nemá kontrolu.

Efektivnější využití procesorové cache?

Pokud mám problém s využitím procesorové cache, budu řešit efektivnější využití procesorové cache, a ne vytváření pole objektů tak, aby všechny objekty byly v paměti za sebou (už jenom proto, že do té cache se moc objektů nevejde).

Ono ale při problémech s využitím procesorové cache je naprosto zásadní jak jsou data v paměti uložena! A co se týká velikostí cache dnešních CPU tak si aktualizujte znalosti, vejde se toho do nich docela dost.

Naimplementujte si třeba velkou matici intů v jednorozměrném poli (kde budou všechny řádky uložené jeden za druhým) a pak si změřte kolik trvá když budete procházet prvky po řádcích a kolik po sloupcích. Když budete přistupovat do toho pole postupně (aby zabírala cache) bude to mnohem rychlejší než když v něm budete skákat tak že každý další přístup znemožní použití aktuálního obsahu cache. Srovnejte to třeba i s maticí intů implementovanou jako pole polí - tam nebudete mít v Javě kontrolu nad tím kde se jednotlivá pole v paměti naalokují a zase bude výkon nižší než při sekvenčním procházení jednoho velkého pole. Přemýšlet o cache se dnes prostě z hlediska výkonu na reálném hardware vyplácí!

[Filip Jirsák]

Ano, potíž je ovšem v tom, že pro dvojici (int, bool) nebo (UserId, Salary) už žádnou knihovnu nenajdete - to si budete muset napsat kolekci sám (a i tak budete zbytečně alokovat na heapu UserId a Salary).

Ne, v tom žádná potíž není, protože to nikdy nebudu potřebovat. A i kdyby náhodou někdy bylo potřeba optimalizovat takový kód na použití procesorové cache, bude to stejně takové práce, že proti tomu je napsání jedné specifické kolekce brnkačka. Ostatně vy v C# také jako první budete muset udělat to, že opustíte obecná řešení v obecných knihovnách, protože ta obecnost optimalizaci brání.

[Filip Jirsák]

A že ta nejdůležitější a nejzákladnější zásada pro efektivní využití cache je naskládat objekty za sebe a neskákat zbytečně po pointerech?

Kdybyste nereagoval na komentář, kde jsem tohle psal, možná by to bylo i vtipné.

[Reklama]

[Filip Jirsák]

Je to pole referencí a kdo bude tvrdit něco jiného tak ukazuje že Javě naprosto nerozumí!

Ještě jednou, v Javě se pojem „reference na objekt“ nepoužívá, protože se k objektu jinak než přes referenci nedostanete, takže se říká jenom „objekt“.

Ono ale při problémech s využitím procesorové cache je naprosto zásadní jak jsou data v paměti uložena!

Právě proto jsem psal, že budu řešit, jak mají být data uložena, a ne to, jak vypadá nějaké pole.

Naimplementujte si třeba velkou matici intů v jednorozměrném poli

Typická webová aplikace je plná velkých matic intů.

Přemýšlet o cache se dnes prostě z hlediska výkonu na reálném hardware vyplácí!

K reálnému hardware potřebujete ještě reálný software. A takového moc není, napsaného v Javě, který by pracoval s velkými maticemi intů a řešil problémy s procesorovou cache. A pokud takový je, jeho autoři snad vědí, jak mají optimalizovat.

Každopádně je velmi zábavná argumentace, že důvod, proč není moc webhostingů podporujících WAR, je ten, že se webhosteři bojí, že by tam měli plno aplikací pracujících s velkými maticemi intů, které budou špatně používat procesorovou cache.

[Radek Miček]

Ano, potíž je ovšem v tom, že pro dvojici (int, bool) nebo (UserId, Salary) už žádnou knihovnu nenajdete - to si budete muset napsat kolekci sám (a i tak budete zbytečně alokovat na heapu UserId a Salary).

Ostatně vy v C# také jako první budete muset udělat to, že opustíte obecná řešení v obecných knihovnách, protože ta obecnost optimalizaci brání.

Právě, že ne.

A není to jen o cachích. Je to i o práci GC: pro seznam 1000 dvojic (UserId, SalaryId) vy v Javě alokujete na heapu minimálně 3002 objektů, já v C# pouze 2 (instanci třídy List a instanci pole, samotné dvojice mohou být hodnotové typy = žádná alokace na heapu a žádná práce pro GC).

A je tu ještě další věc: Tím, že vy navrhujete používat kolekce mimo standardní knihovnu riskujete, že např. různí programátoři použití různé implementace - např. jeden použije jodd.util.collection.IntArrayList a druhý com.google.common.primitives.Ints.IntArrayAsList - a pak mezi nimi budete muset převádět. Pokud máte kvalitní implementaci ve standardní knihovně, je toto riziko nižší, neboť nemáte tolik důvodů používat třídu mimo standardní knihovnu.

Jak již psal dustin výše, naštěstí se Java dočká uživatelsky definovaných hodnotových typů i specializace generik - otázkou ovšem je kdy (navíc přechod na tyto nové featury nebude okamžitý).

[JSH]

Ono ale při problémech s využitím procesorové cache je naprosto zásadní jak jsou data v paměti uložena!

Právě proto jsem psal, že budu řešit, jak mají být data uložena, a ne to, jak vypadá nějaké pole.

Právě že to je stále jedno a to samé. Pro efektivní využití cache bohatě stačí aby jazyk zbytečně nevkládal zbytečné skákání po pointerech. Koukněte na std::vector z C++. Ten pro běžné velikosti dat výkonnostně pomlátí teoreticky podstatně efektivnější kontejnery, prostě proto, že ukládá data za sebe do pole. A přitom je to naprosto generický kód, kde jako programátor nemusím vůbec nic řešit.

Tím, že Java nemá hodnotové typy a všechno je reference, úplně brutálně mrhá tím nejomezenějším zdrojem dnešních PC - velikostí cache a propustností sběrnice.

[Filip Jirsák]

Ano, potíž je ovšem v tom, že pro dvojici (int, bool) nebo (UserId, Salary) už žádnou knihovnu nenajdete - to si budete muset napsat kolekci sám (a i tak budete zbytečně alokovat na heapu UserId a Salary).

Ostatně vy v C# také jako první budete muset udělat to, že opustíte obecná řešení v obecných knihovnách, protože ta obecnost optimalizaci brání.

Právě, že ne.

Ale jistě že ano. Protože až to budete optimalizovat, první, co musíte udělat, je zamyslet se nad tím, jestli náhodou tisíciprvkový seznam dvojic UserId a Salary, nad kterým provádíte dlouhé výpočty, není nesmysl.

[Filip Jirsák]

Pro efektivní využití cache bohatě stačí aby jazyk zbytečně nevkládal zbytečné skákání po pointerech.

Jasně. Takže libovolná implementace radix tree, spojového seznamu nebo HTML parseru bude efektivně využívat cache procesoru, pokud bude napsaná v C++.

Víte, proč výsledná rychlost programu obecně nezávisí na zvoleném programovacím jazyce? Protože Java programátoři nemají přístup k nízkoúrovňovým věcem a neznají detaily fungování JVM, takže tohle neřeší; zatímco C++ programátoři si myslí, že používají jazyk, který optimalizuje sám od sebe, takže to taky neřeší.

Tím, že Java nemá hodnotové typy a všechno je reference, úplně brutálně mrhá tím nejomezenějším zdrojem dnešních PC - velikostí cache a propustností sběrnice.

Vzhledem k tomu, že to na výkon programů nemá žádný vliv, tak je to jedno.

[dustin]

Typická webová aplikace je plná velkých matic intů.

Ne, ale typická byznys aplikace je plná ArrayList<Integer>, které všude možně prochází ve smyčce (nebo streamem). Proto přímo autoři javy uznávají, že hlavně kvůli efektivitě využití CPU keší je v takovém případě vhodné místo objektů vyžadujících neustálé odskoky z referencí na objekty použít přímo hodnoty a dělají na implementaci do javy. Navíc možnost obalit primitivní typ významem a nechat kompilátor, aby to rovnou hlídal, je zatraceně užitečná (ID uživatele se nemá co míchat s ID článku, jenže jsou obojí inty)

http://cr.openjdk.java.net/~jrose/values/values-0.html
http://www.beyondjava.net/blog/java-8-types-revamping-javas-type-system/
http://openjdk.java.net/projects/valhalla/

Proč je dobré myslet na CPU keše - objem dat na zpracování neustále roste (např. u webů především evidence přístupů, jejichž zpracování má přímou vazbu na prodej inzerentům = byznys) a je jedině dobře, když poroste i rychlost JVM. Rychlost CPU už nijak moc neroste a paralelní zpracování na více jádrech by vyžadovalo podstatně větší úpravy aplikací, než využití hodnotových typů, až budou do javy přidané.

[JSH]

Ano, potíž je ovšem v tom, že pro dvojici (int, bool) nebo (UserId, Salary) už žádnou knihovnu nenajdete - to si budete muset napsat kolekci sám (a i tak budete zbytečně alokovat na heapu UserId a Salary).

Ostatně vy v C# také jako první budete muset udělat to, že opustíte obecná řešení v obecných knihovnách, protože ta obecnost optimalizaci brání.

Právě, že ne.

Ale jistě že ano. Protože až to budete optimalizovat, první, co musíte udělat, je zamyslet se nad tím, jestli náhodou tisíciprvkový seznam dvojic UserId a Salary, nad kterým provádíte dlouhé výpočty, není nesmysl.

Nepíšete každý o něčem trochu jiném? Samozřejmě že se bude muset zamyslet. Ale pokud ten seznam dává smysl, tak je v C# hotov, protože ho má uložený v paměti efektivně i když použije standardní kontejner.

[Pavel Tisnovsky]

Na masivní degradaci výkonu stačí i kolekce obsahující pouhé tisíce prvků. Přístup Javy totiž mrhá cachí a komplikuje práci prefetcheru.

Napsat špatný program lze v jakémkoli jazyce. Pokaždé přijdete s něčím novým, nicméně ještě jste nepřišel s ničím, co by dokazovalo vaše původní tvrzení, že absence uživatelských hodnotových typů v Javě způsobuje výrazně větší paměťové nároky Java aplikací.

Jak už jsem se opravil, měl jsem na mysli absenci uživatelsky def. hodnotových typů + specializace.

Příkladem je seznam čísel, když v Javě použijete generický ArrayList pro uložení 1000 intů. Předpokládejme, že aplikace běží nad HotSpotem a na 64 bitové architektuře. Pro takový seznam se alokuje minimálně 1002 objektů. Každý objekt obsahuje hlavičku (mark word 8 bajtů + klass pointer 8 bajtů; dohromady 16 bajtů). Instance ArrayList se bude skládat z hlavičky, pole, jenž obsahuje minimálně 1000 referencí, a nějakých dalších dat (minimálně 16 bajtů (hlavička) + 8 bajtů (reference na pole) + 8016 bajtů (pole referencí + hlavička) + velikost dalších dat). Pro každý int se vytvoří objekt, který AFAIK zabere min. 20 bajtů (nevím, zda JVM má nějakou minimální velikost objektů; pokud ano, může to být více). Tj. dohromady to zabere minimálně 8040 + 20 * 1000 = 28032 bajtů.

Analogická věc v .NET Core zabere zhruba 4032 bajtů + velikost dalších dat ve třídě List. Na rozdíl od Javy, kde se alokovalo 1002 objektů se zde alokují pouze 2 objekty (instance generické třídy List a pole).

Výše jsou uvedeny pouze odhady, které vycházejí z aktulních implementací - do budoucna se to může měnit.

Ty vypocty sedi, ale otazka zni, proc je pouzit ArrayList? Docela bych rekl, ze je to dost umely priklad ne? Pole intu neni v mode? Btw i kdyby znela odpoved "ale ja potrebuju insert/delete/append", tak v ArrayListu se budou delat  ty same operace, co by se udelaly s arraycopy.

Re: pole objektu je pole referenci, ma to i vyhody, obecne dela GC v Jave "dobre" kdyz jsou objekty male, naopak "humongous" objekty se s GC dost perou (jdou primo do old generation atd.).

[Radek Miček]

Ano, potíž je ovšem v tom, že pro dvojici (int, bool) nebo (UserId, Salary) už žádnou knihovnu nenajdete - to si budete muset napsat kolekci sám (a i tak budete zbytečně alokovat na heapu UserId a Salary).

Ostatně vy v C# také jako první budete muset udělat to, že opustíte obecná řešení v obecných knihovnách, protože ta obecnost optimalizaci brání.

Právě, že ne.

Ale jistě že ano. Protože až to budete optimalizovat, první, co musíte udělat, je zamyslet se nad tím, jestli náhodou tisíciprvkový seznam dvojic UserId a Salary, nad kterým provádíte dlouhé výpočty, není nesmysl.

Situací, kdy potřebujete pracovat s dvojicemi id a číslo je celá řada. Např. obyčejný e-shop chce nabízet produkty, které by se zákazníkovi mohly líbit - tj. pro každého zákazníka tam může mít seznam (id produktu, skóre) a z něj chce vždy vybrat např. 5 nejoblíbenějších produktů (s nejvyšším skóre), které zákazníkovi nebyly ukázány více než 4x (na to mj. potřebuje i mapu, id produktu -> kolikrát byl ukázán; pro níž byste v Javě opět nemohl použít standardní kolekci, pokud vám jde o alokaci paměti a výkon).

BTW, pokud se v C# rozhodnu takovéhle věci cachovat, tak jich nacachuji několikanásobně více než v Javě (protože zabírají několikanásobně méně paměti).

[JSH]

Jasně. Takže libovolná implementace radix tree, spojového seznamu nebo HTML parseru bude efektivně využívat cache procesoru, pokud bude napsaná v C++.

Samozřejmě že nebude. To je taky důvod, proč std::vector v dnešní době pomlátí std::list i když by podle asymptotické složitosti neměl.

Víte, proč výsledná rychlost programu obecně nezávisí na zvoleném programovacím jazyce? Protože Java programátoři nemají přístup k nízkoúrovňovým věcem a neznají detaily fungování JVM, takže tohle neřeší; zatímco C++ programátoři si myslí, že používají jazyk, který optimalizuje sám od sebe, takže to taky neřeší.

Takže to, že se dá prasit v každém jazyce a spousta lidí to dělá nějak vyplývá, že je to OK?

Vzhledem k tomu, že to na výkon programů nemá žádný vliv, tak je to jedno.

Samozřejmě že to má vliv. Ale není to na první pohled vidět, protože ten vliv je rozprostřený po celém programu. Profiler neukáže, že to někde drhne, protože to drhne +- všude.
Pokud to nemá žádný vliv, tak proč se v současné době tolik řeší Data-Oriented-Design?