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

Ne­dávno jsem na­ra­zil na za­jí­mavý test, který se snažil na­hrubo určit kolik paměti po­tře­bují různé datové struk­tury na JVM: ko­lekce z Javy, Scaly, Googlí Guavako­lekce Trove spe­ci­a­li­zo­vané pro pri­mi­tivní typy. Test pro­bí­hal tak, že na­star­to­val JVM s 1GB heap, vy­tvo­řil danou ko­lekci, začal při­dá­vat jeden ele­ment za druhým až do oka­mžiku, kdy došla paměť a vir­tu­ální stroj vy­ho­dil Ou­tO­f­Me­mo­ryError. Potom autoři pro­hlá­sili, že daná ko­lekce s vý­sled­ným počtem ele­mentů zabere plus/mínus jeden gi­ga­bajt paměti.

To všechno vy­pa­dalo celkem ro­zumně až do oka­mžiku, kdy jsem si prošel vý­sledky. Z nich vy­plý­valo, že do jed­noho gi­ga­bajtu paměti se vejde Trove TIn­tArra­y­List (který ukládá ne­bo­xo­vané in­te­gery) o délce nej­výše 10485760 ele­mentů. Neboli 40 me­ga­bajtů dat.

Tady něco ne­hraje. Čekal jsem, že to bude de­setkrát až dva­cet­krát více.

Hned jsem začal vrtat v im­ple­men­taci Trove ko­lekcí, zdro­já­cích testu a měřit ve­li­kosti ob­jektů a za chvíli jsem zjis­til, že Trove TIn­tArra­y­List je im­ple­men­to­ván polem, které má vý­chozí ka­pa­citu 10 a když se naplní, alo­kuje větší pole, pře­ko­pí­ruje do něj starý obsah a přidá nová data. Ve­li­kost nového pole se rovná staré ve­li­kost po­su­nuté o jeden bit doleva. A 10 << 20 je právě 10485760, což zna­mená, že test na­ra­zil na OOM, když TIn­tArra­y­List pro­vá­děl jed­n­a­dva­cáté zvět­šení. V ten oka­mžik se na haldě na­chá­zelo staré pole délky 10M a snaha alo­ko­vat nové o délce 20M se­lhala. Ale i když se­čteme ve­li­kosti těchto dvou polí, do­sta­neme pou­hých 120MB dat na 1GB haldě než JVM začne ka­pi­tu­lo­vat.

Tady pořád něco ne­hraje.

Na­star­to­val jsem tedy Vi­su­alVM, abych se po­dí­val, co se ve vir­tu­ál­ním stroji do­o­pravdy děje a hned mě to ude­řilo do očí: ge­ne­rační gar­bage collec­tor.

Pokud JVM po­u­žívá tento GC, roz­dělí haldu do ně­ko­lika ob­lastí: eden, sur­vi­vorold a žádná z nich není dost velká na to, aby pojala gi­gan­tické pole. A pro­tože data ne­mů­žou pře­ční­vat z jedné ob­lasti do druhé, není možné alo­ko­vat pole větší než nejmenší z těchto re­gi­onů, což bude nej­spíš sur­vi­vor, který je tvořen dvěma ne­zá­vis­lými po­lo­vi­nami mezi kte­rými se ko­pí­rují data.

Tato teorie také vy­svět­luje, proč „frag­men­to­vané“ ko­lekce, které ne­po­tře­bují velká sou­vislá pole, mají v testu na­mě­ře­nou po­měrně velkou ka­pa­citu, která je roz­hodně větší než by od­po­ví­dalo roz­dílu mezi bo­xo­va­nými a pri­mi­tiv­ními typy.

Nej­snad­nější způsob, jak tento pro­blém řešit, když na něj na­ra­zíte, je na­sta­vit větší heap a dál se o nic ne­sta­rat.

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