Could 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

Could 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.