funkcionálně.cz

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

Velikost objektů v Javě - mapy

25. 1. 2013 — k47

V návaznosti na poslední článek, kde jsem psal, jak spočítat velikost objektů v Javě, jsem provedl několik empirických měření, jak jsou na tom mapy.

Test je jednoduchý: kolik paměti zabere mapa, jejíž klíče jsou integery a hodnoty také integery, která obsahuje pět milionů hodnot? Jde o celkem reálný případ, protože tohle se děje vždycky, když chceme zjisťovat četnost nějakých hodnot, které můžeme zredukovat na celé číslo. Dohromady tedy chceme v mapě uložit 10 milionů integerů, které představují 40MB užitečných dat.

Kolik paměti skutečně zaberou reálné mapy ukazuje následující tabulka:

třída 5M dvojic 1 pár implementace
ideální svět 40MB 8B unicorns and rainbows
boxed ints 160MB 32B unicorns with diarrhea
Java HashMap 356MB 71B separate chaining/closed addressing
Java TreeMap 365MB 73B red-black tree
Scala mutable.HashMap 320MB 64B separate chaining/closed addressing
Scala mutable.OpenHashMap 470MB 94B open addressing (double hashing)
Scala immutable.HashMap 560MB 112B hash trie
Scala immutable.TreeMap 353MB 71B red-black tree
colt OpenIntIntMap 130MB 24B open addressing (double hashing)

Jak je vidět režie je značná a rozdíly drastické.

Javovské HashMap a TreeMap a Scalovské mutable.HashMap a immutable.TreeMap zabírají přibližně stejně místa. Není se čemu divit, protože jsou implementovány stejně: černo-červenými stromy a hash-tabulkou se zřetězenými záznamy.

Scalovská OpenHashMap potřebuje tolik paměti jenom proto, že její implementace není příliš šetrná k alokacím (např. vnitřně používá Option, které by se dalo inlinovat na proměnnou + příznak jestli je nastavená; jenom to by mapu zeštíhlilo o 16 bajtů na záznam). K tomu si připočtěte fakt, že když se hash tabulka přeplní, zvětší se rovnou na čtyřnásobek původní velikosti, která bude většinu času prázdná a máte jasného požírače paměti.

Dále se musíme pozastavit nad tím, o kolik víc paměti spotřebuje immutable.HashMap ve srovnání s immutable.TreeMap i když TreeMap toho "umí víc" (jedná se o řazenou mapu). Abychom pochopili důvod, musíme se podívat, jak jsou tyto struktury implementovány. TreeMap používá dobře známé červeno-černé binární stromy, zatímco HashMap využívá hash trie (prefixový strom) popsaný v paperech Phila Bagwella

Rozdíl je v tom, že binární strom pro každý uzel alokuje jeden objekt, který obsahuje pár referencí. To má za následek poměrně snesitelné požadavky na paměť, ale přístupová doba odpovídá log(n), protože program musí projít strom do hloubky a hledání dále zpomaluje špatná paměťová lokalita.

Naproti tomu hash trie je velice plochý strom (každý uzel má 32 větví) a v každé úrovni se hledá pomocí jedné pětice bitů hashe klíče (5 bitů odpovídá právě 32 elementům). To má za následek velice rychlou přístupovou dobu, která se dá pro všechny rozumné velikosti map považovat za konstantní a velice dobrou paměťovou lokalitu (nemusím tolik skákat po lianách pointerů, ale celé pole mi pěkně sedí v cache procesoru). Ale na druhou stranu musím alokovat pole s 32 referencemi i když mám v daném listu jenom jeden element. Právě tyto pole se podepsaly na překvapivě vysoké spotřebě paměti a vysoké alokaci a aktivitě GC v průbehu testu.

Zcela nepřekvapivě nejméně paměti zabírá implementace z knihovny Colt, která je specializována přímo pro primitivní int.


Odkazy:

http://b010.blogspot.cz/2009/05/speed-comparison-of-1-javas-built-in.html

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