Velikost objektů v Javě – mapy

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.Tre­eMap 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/…uilt-in.html

Flattr this!

This entry was posted in Java, JVM, Paměť, Scala. Bookmark the permalink.

6 Responses to Velikost objektů v Javě – mapy

  1. v6ak says:

    Vím, že je to trošku starší článek, ale přidám jeden postřeh: „Scala mutable.HashMap“ zabírá podstatně méně místa než „Scala immutable.HashMap“. Jestli to dobře chápu, je to tím, že mutable.HashMap používá strom s menším větvením.

    Bez bližšího pohledu bych to čekal vyrovnaně nebo trošku ve prospěch immutable varianty. Immutable varianta může využít faktu, že ví, že se v ní nebude nic měnit. A tedy může udělat nějaké optimalizace, například nemusí alokovat tak velkou hashtabulku pro případ dalšího vkládání nebo v některých speciálních případech (např. po volání filter) může teoreticky kousky stromu sdílet s někým jiným. (I když… to by se asi u HashMapy nevyplatilo implementovat, spíš u TreeMapy.)

    Dá se z toho tedy vyvodit, že:

    • Když dochází paměť, lze nahradit immutable.HashMap za mutable.HashMap. Zaplatím za to možná ztrátou výkonu (menší větvení znamená méně náhodných skoků po paměti; na druhou stranu ale možná nebude fungovat tak dobře cache) a samozřejmě určitými riziky z hlediska kvality kódu.
    • Alternativně je možné mít nějaký wrapper na mutable Map, který z ní udělá immutable (pokud k té mutable instanci nemá referenci nějaký „záškodník“). Ale je to další overhead.
    • Dokud je dost paměti, preferovat immutable, není-li potřeba mutable.
    • Nebo tu je implementace immutable.Map s charakteristikami blízkými mutable.Map?
    • s.c.m.HashMap je implementovaná jako plochá hash tabulka.

      s.c.i.HashMap interně vypadá jako HAMT s větvením 32. Interní uzly nealokují plné pole délky 32, ale jen tak dlouhé, aby se do něj vešli všichni potomci + jedna 32b bitmapa. Přesto má stále poměrně velkou režii, protože skoro všechny uzly interních HAMT stromů jsou velice malé (nejčastěji mají jen 2 nebo 3 potomky), každé tohle malé pole musí mít vlastní ±16B hlavičku a to se postupně nastřádá. Jde o důsledek dobré hashovací funkce, které elementy rovnoměrně rozloží.

      Persistentní datové struktury však mají jeden zásadní problém: Aby byly efektivní, musí být implementované pomocí stromů a stromy znamenají paměťovou režii, nahánění pointerů, datové závislosti a neideální využití cache. Existuje jeden paper, který popisuje vylepšení pro standardní immutable HAMT hashmapu, ale ladí jen detaily a drobnosti, stromy zůstávají. O tom byla celá tahle přednáška.

      Nějakou dobu jsem nad tím přemýšlel, a došel jsem k tomu, že je možné napsat efektivnější implementaci persistetních map a vektorů, když obětujeme plnou persistenci a bude stačit jenom částečná. Výsledek je po všech stránkách efektivnější – časově, prostorově a chová se lépe k hardwaru – ale má jen částečnou persistenci (a navíc implementace na JVM chce trochu představivosti). Začal jsem o tom psát článek, který by se tady (při troše dobré vůle) někdy mohl objevit.

      • v6ak says:

        Díky za vysvětlení. Pořád ale nechápu, proč došlo k takovéto volbě. Právě u ploché tabulky bych čekal, že případné kolize budou méně vadit u read-only přístupu, kdy nedochází k přelévání kolidujících prvků při zápisu.

        Musel jsem si najít, co myslíš tím „perzistentní“: https://en.wikipedia.org/…ta_structure .

        No, řekl bych, že perzistentní může být jakákoli immutable datová struktura, jen je otázka za jakou cenu. V nejhorším případě to zkopíruju celé (což se zmiňuje i na té Wikipedii). Otázka spíš je, jestli je ta struktura perzistentní efektivním způsobem. Ale tady bych měl pochyby i o HashMapě:

        U spojového seznamu je to jasné – zefektivňuje operace drop a prepend (za určitých okolností – dropnout ≥ ½ všech prvků nebude efektivní). U množiny/mapy sežazené podle hodnot/klíčů ve stromu taky – můžu snadno vybrat souvislý podstrom. (Byť si nejsem 100% jist, zda to lze nějak efektivně ve Scalových kolekcích – asi se tak nestane po použití metody filter.) Ale u HashMapy? Kdy to tam využijeme?

        • U neměnných hashmap projeví třeba tak, že když mám něco jako

          val oldMap: immutable.Map[Int, String] = reallyBigMap()
          val newMap = map.updated(47, "forty seven")

          nová mapa sdílí naprostou většinu struktury s tou starou. Jedinou odlišností je jedna cesta od kořene interního stromu k listu obsahujícímu klíč 47. Díky tomu jsou operace jako přidání nebo mazání jednotlivých klíčů efektivní, co se rychlosti a místa týče. Asymptoticky jedou v čase log32n. Konstantní faktory jsou trochu divoké, ale to je cena za funkcionální programování.

          Operace filter, map a další, které pracují s celou mapou vedou k vytvoření nové kolekce.

          Daniel Spiewak má dobrou přednášku na tohle téma.

          • v6ak says:

            Díky, toto použití jsem si neuvědomil. Byť mi teda nepřijde, že bych zrovna tuto operaci používal nějak často. (Ale to možná i proto, že jsem si neuvědomil, že to vlastně není až tak drahá operace…)

            BTW, O(log32(n)) je prostě O(log(n)), ne?

          • Ano, asymptoticky to platí. Základ logaritmu 32 se často používá jako marketingový trik. Protože log32(Int.Max­Value) je menší než 7, o operacích s touhle složitostí se říká, že mají efektivně konstantní složitost. Technicky jsou logaritmické, ale v praxi je to jen větší konstanta.

Leave a Reply

Your email address will not be published. Required fields are marked *