4 ms·

It's all in the README above. But basically each node can have up to 32 (2^5) children. Instead of allocating an array of 32 elements in each node, you have a 3

It's all in the README above. But basically each node can have up to 32 (2^5) children. Instead of allocating an array of 32 elements in each node, you have a 32-bits bitmap where the nth bit is set only if the corresponding children is present. 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).

wyager 9y ago
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.
- loopingoptimism 9y ago
  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.

wyager 9y ago

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.

loopingoptimism 9y ago
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.