0xDEADBEEF

[RSS]
««« »»»

Heterogenní persistentní kolekce

5. 9. 2017

Ef­fi­ci­ent Im­mu­table Collecti­ons, Mi­chael Stein­dor­fer

Tohle je něco podle mého gusta, tour de force di­plo­mová práce (thesis, co to je vlastně česky?), která zkoumá všechny možné po­stupy, jak im­ple­men­to­vat pa­mě­ťově efek­tivní ko­lekce v pro­středí JVM. A když říkám všechny, myslím sku­tečně všechny. Autor Mi­chael Stein­dor­fer se ne­za­lekne žád­ného pro­blému a ne­za­staví se před ničím.


Začalo to Bagwellem in­spi­ro­va­nými HAMT – hash array mapped tries – efek­tivní me­to­dou jak re­pre­zen­to­vat per­si­s­tentí funk­ci­o­nální ha­shmapy jako velice široké a mělké stromy, které našly uplat­nění ve stan­dardní knihovně Scaly a Clo­jure.

Ale u toho to ne­skon­čilo a Stein­dor­fer začal po­stupně pre­zen­to­vat sérii zlep­šení.

První z nich byl CHAMP (Op­ti­mi­zing Hash-Array Mapped Tries for Fast and Lean Im­mu­table JVM Collecti­ons), který drob­nou změnou in­terní struk­tury snížil spo­třebu paměti, rych­lost ite­race a kon­t­rolu rov­nosti dvou ko­lekcí.

Jednou ze změn je ka­no­ni­zace, kdy ko­lekce ob­sa­hu­jící stejná data mají vždy stej­nou re­pre­zen­taci. To obecně ne­platí, když při­dá­vám a mažu prvky. Pokud je ko­lekce vždy ka­no­nická, jsem si jistý, že když se liší jejich struk­tura, jde o dvě roz­dílné ko­lekce a ne­mu­sím kon­t­ro­lo­vat nic dal­šího. Pokud je struk­tura stejná, ko­lekce můžou být stejné, ale abych to po­tvr­dil, musím je re­kur­zivně po­rov­ná­vat do hloubky.

Autor se pak začal za­bý­vat spe­ci­a­li­zací (Code Spe­ci­a­li­zation for Memory Ef­fi­ci­ent Hash Tries), tedy ge­ne­ro­vá­ním Java tříd, které ne­ob­sa­hují odkaz na pole (jak je běžné v im­ple­men­taci HAMT), ale he­te­ro­genní pole klíčů/hodnot a pod­stromů (re­spek­tive spe­ci­a­li­zo­va­ných pri­mi­tiv­ních hodnot) je in­li­no­váno přímo do těla třídy jako její atri­buty. To značně sníží pa­mě­ťové nároky, pro­tože není třeba ucho­vá­vat hla­vičku vnitř­ního pole, které je vět­ši­nou velice malé.

Pro­blém spo­čívá v kom­bi­na­to­rické ex­plozi počtu tříd. V na­iv­ním pří­padě je po­třeba vy­ge­ne­ro­vat jednu třídu pro každou možnou podobu struk­tury uzlu. Autor k tomu při­stou­pil prag­ma­ticky. Vět­šina stromů je malá, ob­sa­huje nej­čas­těji dva nebo tři po­tomky a u těchto malých stromů spe­ci­a­li­zace při­nese nej­větší re­dukci místa. Proto stačí vy­ge­ne­ro­vat spe­ci­a­li­zace jen pro tyto pří­pady a získat tak nej­větší pro­spěch s nejmen­šími ná­klady.

Lo­gic­kým vy­ús­tě­ním byla jeho PhD práce (Ef­fi­ci­ent Im­mu­table Collecti­ons), která kom­bi­nuje všechny do té doby pu­b­li­ko­vané články a roz­víjí je o krok dál, směrem k efek­tivní re­pre­zen­taci mul­ti­map.

Uka­zuje se, že stejné tech­niky inline bitmap, které jsou po­u­žité v HAMT k roz­li­šení pří­padů prázdný slot/klíč+hod­nota/pod­strom, lze roz­ší­řit pro dis­kri­mi­naci mezi li­bo­vol­ným množ­stvím he­te­ro­gen­ních pří­padů, tedy na­pří­klad ma­po­vání klíč→hod­nota/klíč→mno­žina hodnot a tak efek­tivně re­pre­zen­to­vat mul­ti­mapy.

Autor také krátce pre­zen­to­val své vý­sledky.

Re­le­vantní čtení:

píše k47 (@kaja47, k47)