CHAMP - Compressed Hash-Array Mapped Prefix Tree about fsharpx.collections HOT 7 OPEN

Peter Schuck's Clojure/west 2016 presentation is now on Youtube:

https://www.youtube.com/watch?v=GibNOQVelFY

from fsharpx.collections.

marking as up-for-grabs

from fsharpx.collections.

A ClojureScript implementation is in the work. Maybe it's helpful... or not :)

Lean Hash Array Mapped Trie implementation in ClojureScript

It will be presented at Clojure/west 2016 by Peter Schuck.

from fsharpx.collections.

The Java implementation of the CHAMP data structure, by Steindorfer and Vinju (the authors of the http://michael.steindorfer.name/publications/oopsla15.pdf paper):

https://github.com/usethesource/capsule

Another implementation, by someone else, in Kotlin: https://github.com/norswap/triemap

from fsharpx.collections.

Out of interest - do you really expect a CHAMP to perform particularly well in .NET?
My initial thought would be that due to the necessity of holding keys, values, and nodes in the same obj array the boxing / unboxing cost would be very high for non ref-type keys/values.

from fsharpx.collections.

Particularly well? Not unless the boxing/unboxing problem you mention can be solved.

Better than the current PersistentHashMap? Absolutely; it suffers from the exact same boxing/unboxing issue for value types, so converting it to a CHAMP implementation should be a significant performance gain over the existing implementation.

from fsharpx.collections.

CHAMP conceptually splits each object[] into two sections, so it could actually use two arrays, one Node<T>[] and one T[]. This would prevent boxing/unboxing in exchange for the memory cost of having an extra array at each Node<T> (although it could be null if empty).

from fsharpx.collections.