3 ms·
Honestly, I wouldn't bother with red-black or AVL. I'm not sure about the current state of lock-free data structures, but I prefer a B-Tree to a red-black or AV
by openasocket 10y ago
Honestly, I wouldn't bother with red-black or AVL. I'm not sure about the current state of lock-free data structures, but I prefer a B-Tree to a red-black or AVL tree. At least in the single-threaded case B-Tree operations tend to be faster, have better cache locality, etc. Google reveals there are lock-free implementations of B-Trees, so maybe look into those instead?
- liblfds 10y agoCould be. I will look into the choice before I commit - figuring out how one of these complex lock-free data structures works and implmenting it correctly and writing all the tests cases is a major undertaking. It's something you want to make sure you're making the right choice about before you invest the time. As an aside, binary trees turn out to be really great with lock-free. In the obvious locking implementations, there's one lock per tree. You can use read-writer locks to get parallelism on read, but even so, the mere existance of a single lock of any kind induces memory contention which eliminates scaling as processor counts rise. I'm sure there are in the locking literature better solutions, but I'm up to speed with lock-free, rather than locking, solutions, so I don't much know about them. Regarding lock-free, there is no single lock, and btrees are beautiful because they naturally distribute memory accesses throughout the tree. Performance basically scales linearly. There's a gnuplot on the site from a 16 core Amazon VM, and that property can clearly be seen. Every new core simply adds another 200k benchmark ops per second. For the other, non-scaling data structures, new cores are death.