News for hackers. Stuff that matters.
Re:Efficient Immutable Collections [pdf] by wyager on Monday August 14, 2017 @12:47PM (#15010154)
I'm pretty sure that's exactly like a HAMT except that HAMTs only use one bitmap. I'm not sure why the CHAMP is referred to as "compressed", then, since HAMTs are compressed using the same bitmap technique with a slightly different node structure.
Re:Efficient Immutable Collections [pdf] by loopingoptimism on Wednesday August 16, 2017 @09:28AM (#15027238)
In principle both HAMT and CHAMP compress sparse associative arrays by construction. However, the bitmap encoding of CHAMP results in a better compression for map data structures, enabled by permuting the elements that are stored in the node's array.

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.