3 ms·
Funny timing, I've been looking at this recently. Some other well performing concurrent ordered data structures are ART (adaptive radix trees) and masstree. Ski
by foota 2y ago
Funny timing, I've been looking at this recently. Some other well performing concurrent ordered data structures are ART (adaptive radix trees) and masstree. Skiplists are common since they're easier to implement lock free, but they don't seem to perform well relative to these alternatives.
- judofyr 2y agoYou should check out Height-Oriented Tries as well. Their benchmarks shows that it outperforms both ART and masstree. EDIT: Oops, yes, I meant Height-Optimized Trie! Sorry about that.
- foota 2y agoWill take a look, thanks! I think you meant height-optimized tries, since I had a tough time giving it at first :) Ideally I'd like to find a way to store a non overlapping ordered list of intervals while being able to atomically (wrt other insertions) avoid inserting overlaps. This is part of a data structure tracking locked ranges, so being able to update them in parallel would be nice, since it today takes a lock over the whole tree while inserting new locked ranges. Probably, this would require something with next value pointers. Maybe I could do some kind of scheme where to insert you have to first optimistically lock the predecessor with the to be inserted node, and then insert the new node where it belongs?
- mad 2y agoYou should also check out the Maple Tree (https://docs.kernel.org/core-api/maple_tree.html https://docs.kernel.org/core-api/maple_tree.html). It's the data structure used to track non-overlapping intervals in the Linux kernel's virtual memory subsystem. If you don't mind sharing, what's your use case for such a data structure?