4 ms·
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 resul
by 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 agoFrom 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 agoWhy 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.