I was listening to the wookash podcast on fredbuf, and got inspired to write up a new list. I just wanted to prove to myself that the words “functional datastructure” should not be used in the same sentence as “high performance”
This is a general purpose collection, with:
- arena backed with generation semantics, useful for undo/redo history or immutable/transience tracking
- leaves, much like a bucket array
- random access, for easy indexing or windowing. better than a bucket array
- structural sharing, for minimal memory footprint
- extremely cheap concat/splice
this is inspired by philip bagwell’s paper on relaxed radix balanced tries, but with optimizations in the sizes table to use a more compressed scheme
There’s an explainer:
https://git.mere.cloud/bngreer/odin-basedlist/src/branch/master/docs/explainer.md
Benchmarks:
https://git.mere.cloud/bngreer/odin-basedlist/src/branch/master/docs/benchmarks.md#basedlist-vs-fredbuf-bench-based_vs_fredbuf
The urls 404 for me.
The only difference between the mutating datastructure and the immutable one is that the functional one allocates new nodes as you make the new datastructure and you refcount the nodes.
Neither of those are actual sources of slowdown. In the fredbuf implementation (at least the arena branch) allocation is solved with arenas + freelist.
And I’ve been able to construct a immutable btree implementation that only needs 1 traversal down and up to do any applicable operation in my fork of it. Which is as fast as its gonna be.
The underlying technique is just as valid for a rb-tree as it is for a b-tree
My apologies, I forgot to set repo to public. It should be good now
Thanks for the link, I’ll check it out!
I’ve added your project in my benchmarks. Very nice optimizations you have!
