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

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 zjišť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řída5M dvojic1 párimplementace
ideální svět40MB8Bint[]
boxed ints160MB32BInteger[]
Java HashMap356MB71Bseparate chaining/closed addressing
Java TreeMap365MB73Bred-black tree
Scala mutable.HashMap320MB64Bseparate chaining/closed addressing
Scala mutable.OpenHashMap470MB94Bopen addressing (double hashing)
Scala immutable.HashMap560MB112Bhash trie
Scala immutable.TreeMap353MB71Bred-black tree
colt OpenIntIntMap130MB24Bopen 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 liáná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ůběhu testu.

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


Odkazy:

Speed Comparison of: (1) Java's built-in HashMap, (2) Trove's TIntIntHashMap, and (3) Colt's OpenIntIntHashMap

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