"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).