0xDEADBEEF

[RSS]
««« »»»

Heterogenní persistentní kolekce

5. 9. 2017

Efficient Immutable Collections, Michael Steindorfer

Tohle je něco podle mého gusta, tour de force diplomová práce (thesis, co to je vlastně česky?), která zkoumá všechny možné postupy, jak implementovat paměťově efektivní kolekce v prostředí JVM. A když říkám všechny, myslím skutečně všechny. Autor Michael Steindorfer se nezalekne žádného problému a nezastaví se před ničím.


Začalo to Bagwellem inspirovanými HAMT – hash array mapped tries - efektivní metodou jak reprezentovat persistentí funkcionální hashmapy jako velice široké a mělké stromy, které našly uplatnění ve standardní knihovně Scaly a Clojure.

Ale u toho to neskončilo a Steindorfer začal postupně prezentovat sérii zlepšení.

První z nich byl CHAMP (Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections), který drobnou změnou interní struktury snížil spotřebu paměti, rychlost iterace a kontrolu rovnosti dvou kolekcí.

Jednou ze změn je kanonizace, kdy kolekce obsahující stejná data mají vždy stejnou reprezentaci. To obecně neplatí, když přidávám a mažu prvky. Pokud je kolekce vždy kanonická, jsem si jistý, že když se liší jejich struktura, jde o dvě rozdílné kolekce a nemusím kontrolovat nic dalšího. Pokud je struktura stejná, kolekce můžou být stejné, ale abych to potvrdil, musím je rekurzivně porovnávat do hloubky.

Autor se pak začal zabývat specializací (Code Specialization for Memory Efficient Hash Tries), tedy generováním Java tříd, které neobsahují odkaz na pole (jak je běžné v implementaci HAMT), ale heterogenní pole klíčů/hodnot a podstromů (respektive specializovaných primitivních hodnot) je inlinováno přímo do těla třídy jako její atributy. To značně sníží paměťové nároky, protože není třeba uchovávat hlavičku vnitřního pole, které je většinou velice malé.

Problém spočívá v kombinatorické explozi počtu tříd. V naivním případě je potřeba vygenerovat jednu třídu pro každou možnou podobu struktury uzlu. Autor k tomu přistoupil pragmaticky. Většina stromů je malá, obsahuje nejčastěji dva nebo tři potomky a u těchto malých stromů specializace přinese největší redukci místa. Proto stačí vygenerovat specializace jen pro tyto případy a získat tak největší prospěch s nejmenšími náklady.

Logickým vyústěním byla jeho PhD práce (Efficient Immutable Collections), která kombinuje všechny do té doby publikované články a rozvíjí je o krok dál, směrem k efektivní reprezentaci multimap.

Ukazuje se, že stejné techniky inline bitmap, které jsou použité v HAMT k rozlišení případů prázdný slot/klíč+hodnota/podstrom, lze rozšířit pro diskriminaci mezi libovolným množstvím heterogenních případů, tedy například mapování klíč→hodnota/klíč→množina hodnot a tak efektivně reprezentovat multimapy.

Autor také krátce prezentoval své výsledky.

Relevantní čtení:

píše k47 (@kaja47, k47)