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":[https://github.com/scala/scala/blob/2.12.x/src/library/scala/collection/mutable/FlatHashTable.scala].
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":[http://michael.steindorfer.name/publications/oopsla15.pdf], ale ladí jen detaily a drobnosti, stromy zůstávají. O tom byla celá "tahle přednáška":[http://funkcionalne.cz/2015/09/grim-hardware-realities-of-functional-programming/].
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.
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/wiki/Persistent_data_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 log<sub>32</sub>n. 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":[https://www.youtube.com/watch?v=pNhBQJN44YQ].
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…)
Ano, asymptoticky to platí. Základ logaritmu 32 se často používá jako marketingový trik. Protože log<sup>32</sup>(Int.MaxValue) 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.
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.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":[http://michael.steindorfer.name/publications/oopsla15.pdf], ale ladí jen detaily a drobnosti, stromy zůstávají. O tom byla celá "tahle přednáška":[http://funkcionalne.cz/2015/09/grim-hardware-realities-of-functional-programming/].
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.
Musel jsem si najít, co myslíš tím „perzistentní“: https://en.wikipedia.org/wiki/Persistent_data_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?
/---
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 log<sub>32</sub>n. 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":[https://www.youtube.com/watch?v=pNhBQJN44YQ].
BTW, O(log_32(n)) je prostě O(log(n)), ne?