5 ms·

This is really cool work by Michael, a collection of configurable data structures. Underlying most of them is CHAMP - a compressed hash array map trie. Essenti

This is really cool work by Michael, a collection of configurable data structures. 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 https://github.com/norswap/triemap

wyager 9y ago
Could you expand a bit on the differences between CHAMPs and HAMTs? Most of the info I see about CHAMPs makes them seem very similar, but with a slightly different node structure.
- drawnwren 9y ago
  From the bottom of the Capsule github page [1]: " HAMTs already feature efficient lookup, insert, and delete operations, however due to their tree-based nature their memory footprints and the runtime performance of iteration and equality checking lag behind array-based counterparts. 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." 1 - https://github.com/usethesource/capsule https://github.com/usethesource/capsule
  - wyager 9y ago
    That doesn't answer any of my questions, and they don't have any citation in that block of text. Real details could be in any of the 8 papers linked, or none at all.
    - TheRealPomax 9y ago
      That doesn't feel like a problem? As a PhD thesis, the cited works should cover the subjects, but there is no requirement for the citations to be direct, or even useful to the general public who want to "learn more" =) 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 https://blog.acolyer.org/2015/11/27/hamt which discusses HAMT and then discusses the improvements CHAMP brings to the table.
      - vidarh 9y ago
        > That doesn't feel like a problem? It doesn't make it a bad thesis, but also doesn't answer the questions asked, which is presumably why they were asked.
        TheRealPomax 9y ago
        I was trying to tactfully suggest that google would have trivially found that answer instead of waiting for someone on HN to deliver the answer on a silver plate =)
        wyager 9y ago
        I already found that "answer" and it wasn't very good or descriptive, so I was hoping someone on HN could give me an actual high-quality answer. People here often pull through with good, detailed answers.
    - drawnwren 9y ago
      They increase cache locality and runtime performance of iteration and equality checking. If that answer isn't sufficient, try watching the ~30min Clojure West video on the github page. The speaker seems to be a bit new to public speaking but his talk on the subject was easy to follow and informative for me.
      - ambulancechaser 9y ago
        I was there and you are right, he was very nervous. However his talk was excellent and approachable for everyone reading the above comment. Explains the differences quite well. Certainly worth a talk. I've asked on the clojure slack group if the proposal had gone anywhere and it seems to have stalled unfortunately.
      - loopingoptimism 9y ago
        The talk at Clojure West wasn't given by myself, but I found it worthwhile linking. Rather it was given by someone who independently picked up my research results and replicated them in the context of ClojureScript (https://github.com/bendyworks/lean-map https://github.com/bendyworks/lean-map). The authors independently confirmed the performance improvements of CHAMP over HAMT that I was observing. You can also have a look at the JVMLS'16 talk (https://www.youtube.com/watch?v=pUXeNAeyY34 https://www.youtube.com/watch?v=pUXeNAeyY34) for a high-level overview of the work that is covered in my thesis.
        fnordsensei 9y ago
        From what I've read, it seems that the performance benefits disappear when compound data structures/objects are used as keys. Is this true? 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?
        loopingoptimism 9y ago
        Why should that be the case? Can you point to sources where you read that? In my experience, CHAMP clearly has advantages over HAMT in this scenario. 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.
- norswap 9y ago
  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.
gigatexal 9y ago
Fascinating for sure. I’m looking forward to see what this gets implemented in

wyager 9y ago

Could you expand a bit on the differences between CHAMPs and HAMTs? Most of the info I see about CHAMPs makes them seem very similar, but with a slightly different node structure.

drawnwren 9y ago
From the bottom of the Capsule github page [1]: " HAMTs already feature efficient lookup, insert, and delete operations, however due to their tree-based nature their memory footprints and the runtime performance of iteration and equality checking lag behind array-based counterparts. 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." 1 - https://github.com/usethesource/capsule https://github.com/usethesource/capsule
- wyager 9y ago
  That doesn't answer any of my questions, and they don't have any citation in that block of text. Real details could be in any of the 8 papers linked, or none at all.
  - TheRealPomax 9y ago
    That doesn't feel like a problem? As a PhD thesis, the cited works should cover the subjects, but there is no requirement for the citations to be direct, or even useful to the general public who want to "learn more" =) 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 https://blog.acolyer.org/2015/11/27/hamt which discusses HAMT and then discusses the improvements CHAMP brings to the table.
    - vidarh 9y ago
      > That doesn't feel like a problem? It doesn't make it a bad thesis, but also doesn't answer the questions asked, which is presumably why they were asked.
      - TheRealPomax 9y ago
        I was trying to tactfully suggest that google would have trivially found that answer instead of waiting for someone on HN to deliver the answer on a silver plate =)
        wyager 9y ago
        I already found that "answer" and it wasn't very good or descriptive, so I was hoping someone on HN could give me an actual high-quality answer. People here often pull through with good, detailed answers.
  - drawnwren 9y ago
    They increase cache locality and runtime performance of iteration and equality checking. If that answer isn't sufficient, try watching the ~30min Clojure West video on the github page. The speaker seems to be a bit new to public speaking but his talk on the subject was easy to follow and informative for me.
    - ambulancechaser 9y ago
      I was there and you are right, he was very nervous. However his talk was excellent and approachable for everyone reading the above comment. Explains the differences quite well. Certainly worth a talk. I've asked on the clojure slack group if the proposal had gone anywhere and it seems to have stalled unfortunately.
    - loopingoptimism 9y ago
      The talk at Clojure West wasn't given by myself, but I found it worthwhile linking. Rather it was given by someone who independently picked up my research results and replicated them in the context of ClojureScript (https://github.com/bendyworks/lean-map https://github.com/bendyworks/lean-map). The authors independently confirmed the performance improvements of CHAMP over HAMT that I was observing. You can also have a look at the JVMLS'16 talk (https://www.youtube.com/watch?v=pUXeNAeyY34 https://www.youtube.com/watch?v=pUXeNAeyY34) for a high-level overview of the work that is covered in my thesis.
      - fnordsensei 9y ago
        From what I've read, it seems that the performance benefits disappear when compound data structures/objects are used as keys. Is this true? 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?
        loopingoptimism 9y ago
        Why should that be the case? Can you point to sources where you read that? In my experience, CHAMP clearly has advantages over HAMT in this scenario. 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.
norswap 9y ago
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.

gigatexal 9y ago

Fascinating for sure. I’m looking forward to see what this gets implemented in