funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Haldy nejsou tak velké, jak se se zdají být

9. 3. 2014 — k47

Nedávno jsem narazil na zajímavý test, který se snažil nahrubo určit kolik paměti potřebují různé datové struktury na JVM: kolekce z Javy, Scaly, Googlí Guava a kolekce Trove specializované pro primitivní typy. Test probíhal tak, že nastartoval JVM s 1GB heap, vytvořil danou kolekci, začal přidávat jeden element za druhým až do okamžiku, kdy došla paměť a virtuální stroj vyhodil OutOfMemoryError. Potom autoři prohlásili, že daná kolekce s výsledným počtem elementů zabere plus/mínus jeden gigabajt paměti.

To všechno vypadalo celkem rozumně až do okamžiku, kdy jsem si prošel výsledky. Z nich vyplývalo, že do jednoho gigabajtu paměti se vejde Trove TIntArrayList (který ukládá neboxované integery) o délce nejvýše 10485760 elementů. Neboli 40 megabajtů dat.

Tady něco nehraje. Čekal jsem, že to bude desetkrát až dvacetkrát více.

Hned jsem začal vrtat v implementaci Trove kolekcí, zdrojácích testu a měřit velikosti objektů a za chvíli jsem zjistil, že Trove TIntArrayList je implementován polem, které má výchozí kapacitu 10 a když se naplní, alokuje větší pole, překopíruje do něj starý obsah a přidá nová data. Velikost nového pole se rovná staré velikost posunuté o jeden bit doleva. A 10 << 20 je právě 10485760, což znamená, že test narazil na OOM, když TIntArrayList prováděl jednadvacáté zvětšení. V ten okamžik se na haldě nacházelo staré pole délky 10M a snaha alokovat nové o délce 20M selhala. Ale i když sečteme velikosti těchto dvou polí, dostaneme pouhých 120MB dat na 1GB haldě než JVM začne kapitulovat.

Tady pořád něco nehraje.

Nastartoval jsem tedy VisualVM, abych se podíval, co se ve virtuálním stroji doopravdy děje a hned mě to udeřilo do očí: generační garbage collector.

Pokud JVM používá tento GC, rozdělí haldu do několika oblastí: eden, survivor a old a žádná z nich není dost velká na to, aby pojala gigantické pole. A protože data nemůžou přečnívat z jedné oblasti do druhé, není možné alokovat pole větší než nejmenší z těchto regionů, což bude nejspíš survivor, který je tvořen dvěma nezávislými polovinami mezi kterými se kopírují data.

Tato teorie také vysvětluje, proč "fragmentované" kolekce, které nepotřebují velká souvislá pole, mají v testu naměřenou poměrně velkou kapacitu, která je rozhodně větší než by odpovídalo rozdílu mezi boxovanými a primitivními typy.

Nejsnadnější způsob, jak tento problém řešit, když na něj narazíte, je nastavit větší heap a dál se o nic nestarat.

@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články