Efficient Immutable Collections [pdf]
michael.steindorfer.name
michael.steindorfer.name
Underlying most of them is CHAMP - a compressed hash array map trie. Essentially it's a trie over the hash of the objects inserted in the map. It's compressed using a clever technique that involves bitmaps.
A made a toy implementation of it to get a sense of how it works. There are some accompanying notes that you might find useful: https://github.com/norswap/triemap
We introduce CHAMP (Compressed Hash-Array Mapped Prefix-tree), an evolutionary improvement over HAMTs. The new design increases the overall performance of immutable sets and maps. Furthermore, its resulting general purpose design increases cache locality and features a canonical representation."
If you just want to know the difference between CHAMP and HAMT, then Google gets you that information pretty swiftly. Maybe you were looking for https://blog.acolyer.org/2015/11/27/hamt which discusses HAMT and then discusses the improvements CHAMP brings to the table.
It doesn't make it a bad thesis, but also doesn't answer the questions asked, which is presumably why they were asked.
You can also have a look at the JVMLS'16 talk (https://www.youtube.com/watch?v=pUXeNAeyY34) for a high-level overview of the work that is covered in my thesis.
Let's say that I were to use a vector of coordinates as the key to something in a map. Would CHAMP still vastly outperform HAMT?
To answer your questions about using vectors of coordinates of keys: it depends on the design implementation of the vector's hash code, regardless if you use HAMT or CHAMP.
Using collections as keys in other collections is in general a performance sensitive subject. The available HAMT implementations in Clojure and Scala fail to deliver here. The case study in Chapter 3.7 nests hash-sets into hash-sets (i.e., Set.Immutable<Set.Immutable<K>> sets). The CHAMP implementation yields minimal speedups of ~10x over Clojure and Scala due to the way it calculates and incrementally updates the collection's hash code.
All the children are "compressed" into a single array. To be able to index a child quickly, it suffices to count the number of bit set below the bit corresponding to the child (something that can be done with some masking and a intrinsic bit count operation that maps to an ASM instruction).
This is a bit simplified. In reality each node distinguishes between its children that are actual key-value map entries and those that are nodes.
Additionally, entries are not stored in an extra "Entry" object, but instead occupy two slot in the storage array.
Nevertheless that is your principle: each node is sparse and only allocates storage for the children that are actually present (at the cost of maintaining two bitmaps: one for children entries and one for children nodes).
This is in particular the case when compared to Clojure's PersistentHashMap. Clojure reserves two array slots per entry to either store a) two pointers inline (i.e., key and value tuple), or b) a single reference to a sub-trie in the second slot. At runtime Clojure checks if the first slot is equal to 'null' for distinguishing cases a)/b) and doing the correct type casts at runtime. The thesis visualizes this in chapter 3, page 42.
IMHO required reading if you're doing any heavy FP work.
https://www.classes.cs.uchicago.edu/archive/2017/spring/2230...
"Speedups Compared to Clojure’s Maps: In every runtime measurement CHAMP is better than Clojure. CHAMP improves by a median 72 % for Lookup, 24 % for Insert, and 32 % for Delete. At iteration and equality checking, CHAMP significantly outperforms Clojure. Iteration (Key) improves by a median 83 %, and Iteration (Entry) by 73 %. Further, CHAMP improves on Equality (Distinct) by a median 96 %, and scores several magnitudes better at Equality (Derived). Speedups Compared to Clojure’s Sets: The speedups of CHAMP for sets are similar to maps across the board, with exception of insertion and deletion where it scores even better."
Interesting indeed!
In reality other things matter.
If qsort only provided a constant ratio time improvement over bubble sort in the average case, then it wouldn't have been so popular.
However, it is still a meaningful incremental improvement over Clojure's implementation for iteration and equality checks, among others.
I wonder why the improvement wasn't adopted yet by the Clojure and Scala communities.
The CHAMP data structure was already picked up by the ClojureScript community (https://github.com/bendyworks/lean-map), but still requires some work to be upstreamed to Clojure I guess.
I personally (I'm the author of the thesis linked above) plan to work together with the Scala folks at Lightbend for the collections overhaul that's planned for Scala 2.13 (see https://github.com/scala/collection-strawman).