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á­vaz­nosti na po­slední článek, kde jsem psal, jak spo­čí­tat ve­li­kost ob­jektů v Javě, jsem pro­vedl ně­ko­lik em­pi­ric­kých měření, jak jsou na tom mapy.

Test je jed­no­du­chý: kolik paměti zabere mapa, jejíž klíče jsou in­te­gery a hod­noty také in­te­gery, která ob­sa­huje pět mi­li­onů hodnot? Jde o celkem reálný případ, pro­tože tohle se děje vždycky, když chceme zjis­ťo­vat čet­nost ně­ja­kých hodnot, které můžeme zre­du­ko­vat na celé číslo. Do­hro­mady tedy chceme v mapě uložit 10 mi­li­onů in­te­gerů, které před­sta­vují 40MB uži­teč­ných dat.

Kolik paměti sku­tečně za­be­rou reálné mapy uka­zuje ná­sle­du­jící ta­bulka:

třída 5M dvojic 1 pár im­ple­men­tace
ide­ální svět 40MB 8B uni­corns and ra­in­bows
boxed ints 160MB 32B uni­corns with di­arrhea
Java Ha­shMap 356MB 71B se­pa­rate cha­i­ning/closed ad­d­res­sing
Java Tre­e­Map 365MB 73B red-black tree
Scala mu­table.Ha­shMap 320MB 64B se­pa­rate cha­i­ning/closed ad­d­res­sing
Scala mu­table.Ope­nHa­shMap 470MB 94B open ad­d­res­sing (double ha­shing)
Scala im­mu­table.Ha­shMap 560MB 112B hash trie
Scala im­mu­table.Tre­e­Map 353MB 71B red-black tree
colt Ope­nIn­tIntMap 130MB 24B open ad­d­res­sing (double ha­shing)

Jak je vidět režie je značná a roz­díly dras­tické.

Ja­vov­ské Ha­shMapTre­e­Map a Sca­lov­ské mu­table.Ha­shMapim­mu­table.Tre­e­Map za­bí­rají při­bližně stejně místa. Není se čemu divit, pro­tože jsou im­ple­men­to­vány stejně: černo-čer­ve­nými stromy a hash-ta­bul­kou se zře­tě­ze­nými zá­znamy.

Sca­lov­ská Ope­nHa­shMap po­tře­buje tolik paměti jenom proto, že její im­ple­men­tace není příliš šetrná k alo­ka­cím (např. vnitřně po­u­žívá Option, které by se dalo in­li­no­vat na pro­měn­nou + pří­znak jestli je na­sta­vená; jenom to by mapu zeštíhlilo o 16 bajtů na záznam). K tomu si při­počtěte fakt, že když se hash ta­bulka pře­plní, zvětší se rovnou na čtyř­ná­so­bek pů­vodní ve­li­kosti, která bude vět­šinu času prázdná a máte jas­ného po­ží­rače paměti.

Dále se musíme po­za­sta­vit nad tím, o kolik víc paměti spo­tře­buje im­mu­table.Ha­shMap ve srov­nání s im­mu­table.Tre­e­Map i když Tre­e­Map toho „umí víc“ (jedná se o řa­ze­nou mapu). Abychom po­cho­pili důvod, musíme se po­dí­vat, jak jsou tyto struk­tury im­ple­men­to­vány. Tre­e­Map po­u­žívá dobře známé čer­veno-černé bi­nární stromy, za­tímco Ha­shMap vy­u­žívá hash trie (pre­fi­xový strom) po­psaný v pa­pe­rech Phila Bagwella

Rozdíl je v tom, že bi­nární strom pro každý uzel alo­kuje jeden objekt, který ob­sa­huje pár re­fe­rencí. To má za ná­sle­dek po­měrně sne­si­telné po­ža­davky na paměť, ale pří­stu­pová doba od­po­vídá log(n), pro­tože pro­gram musí projít strom do hloubky a hle­dání dále zpo­ma­luje špatná pa­mě­ťová lo­ka­lita.

Na­proti 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ů od­po­vídá právě 32 ele­men­tům). To má za ná­sle­dek velice rych­lou pří­stu­po­vou dobu, která se dá pro všechny ro­zumné ve­li­kosti map po­va­žo­vat za kon­stantní a velice dobrou pa­mě­ťo­vou lo­ka­litu (ne­mu­sím tolik skákat po li­a­nách poin­terů, ale celé pole mi pěkně sedí v cache pro­ce­soru). Ale na druhou stranu musím alo­ko­vat pole s 32 re­fe­ren­cemi i když mám v daném listu jenom jeden ele­ment. Právě tyto pole se po­de­psaly na pře­kva­pivě vysoké spo­třebě paměti a vysoké alo­kaci a ak­ti­vitě GC v prů­behu testu.

Zcela ne­pře­kva­pivě nejméně paměti zabírá im­ple­men­tace z knihovny Colt, která je spe­ci­a­li­zo­vána přímo pro pri­mi­tivní int.


Odkazy:

Speed Com­pa­ri­son of: (1) Java's built-in Ha­shMap, (2) Trove's TIn­tIn­tHa­shMap, and (3) Colt's Ope­nIn­tIn­tHa­shMap

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