On 04/12/13 20:51, Michael Woerister wrote:
I've implemented a persistent HAMT [1] a while back:
https://github.com/michaelwoerister/rs-persistent-datastructures/blob/master/hamt.rs
It's the data structure used for persistent maps in Clojure (and
Scala, I think). It's not too hard to implement and it's pretty nifty.
I'm not sure about the performance with atomic reference counting
being used for memory management. It will definitely be worse than
with a stop-the-world garbage collector. Although, it's noteworthy
that look ups in the data structure only have to copy one `Arc` for
returning the result, so the high fan-out of the data structure should
not hurt if you mostly read from it. I'd be very interested in a
performance comparison to other persistent map implementations in Rust
(e.g. a red-black tree or splay tree).
Here are some things I came across during implementing this:
* I too discovered that I couldn't parametrize on the type of
reference being used without higher kinded types. I did the
implementation with regular @ pointers at first and later switched to
`Arc`, since concurrent contexts are where persistent data structures
really shine. Switching the implementation from @ to Arc was pretty
straight forward.
* I found there is no standardized trait for persistent maps in libstd
or libextra. It would be nice to have one!
* It's probably a very good idea to provide a non-persistent "builder"
that avoids the excessive copying during the insertion phase. In
Clojure one can switch between "transient" and persistent mode for a
data structure instance which also allows for optimized batch
modifications. An `insert_from(iterator)` method might also do the
trick. There's quite a bit of design space here.
For reference, the FromIterator & Extendable traits are the things to
implement if one has a structure that can be constructed from/extended
with an iterator and wishes to share the behaviour.
http://static.rust-lang.org/doc/master/std/iter/trait.FromIterator.html
http://static.rust-lang.org/doc/master/std/iter/trait.Extendable.html
Huon
* I would have liked to avoid some allocations and pointer chasing by
using fixed size vectors directly within nodes but I could not get
that to work without a lot of unsafe code that I was not sure would be
correct in all cases. So I just used owned vectors in the end.
Looking forward to seeing more in this area :)
-Michael
[1] https://en.wikipedia.org/wiki/Hash_array_mapped_trie
_______________________________________________
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
