feature request: Implement CHAMP for increased performance.

[NodeGuy]

CHAMP (Compressed Hash-Array Mapped Prefix-tree) is an incremental improvement over HAMT that simplifies the code, decreases the memory footprint, and increases performance.

Leveling up Clojure’s Hash Maps is an easily accessible introduction to it by the guy who replaced Clojure(Script)'s HAMT implementation with it.

The original paper: Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections

The reference implementation in Java: The Capsule Hash Trie Collections Library

The Clojure implementation in Java and ClojureScript implementations look more easily grokkable to me.

[axefrog]

Thanks for the link David, I'll definitely file that away for future upgrades!

[wishfoundry]

just as an FYI, I've attempted a similar effort in porting CHAMP to JS over here

I'm still spinning out variants and comparing benchmarks, but in general these tend to have faster writes with slightly slower reads available HAMT libs in JS today. Unlike what the article claims, there's no magic 5x faster though I'm afraid, maybe 50% faster writes, and 5% slower reads

[NodeGuy]

Huh. That's disappointing. Thanks for sharing your experience.