(More) Efficient locking when rotating nodes in threaded binary tree

Answer 1

Have a look at immutable binary trees. You have to change a bit more nodes (every node to the root), but that doesn't change the complexity of an insert which is log n both ways. Indeed, it may even improve the performance because you do not need any synchronization-code.

For example, Eric Lippert wrote some posts about immutable avl trees in C#. The last one was: Immutability in C# Part Nine: Academic? Plus my AVL tree implementation

Answer 2

There would usually be one lock for the entire data structure, given that a lock itself usually takes up some serious resources. I'm guessing given that you are trying to avoid that, this must be some very specialized scenario where you have a lot of CPU intensive worker threads constantly updating the tree?

You could get a balance by making every N nodes share one lock. When entering a rotation operation, find the set of unique locks used by the affected nodes. Most of the time it will be just one lock.

Answer 3

Hi, the best solution depends on your application. But if you have like an in-memory database of stuff and you want to do concurrent updates to it AND want to have very fine-grained locking, you could also look at B-trees which do not require node rotation as often as binary trees. They are also automatically balanced, unlike binary trees, which require more rotations to maintain balancing (e.g. Splay or AVL trees).

If you want to have transactional modifications to the trees, instead, you could use functional B-trees (which Thomas Danecker calls immutable trees). These are kind of "copy-on-write" binary trees, and there the only thing you need to lock is the root node. So you need only one lock. And the operations have in practice the same complexity as for binary trees, because all ops on functional binary trees are O(log n) and you spend the same logarithmic time whenever you descend down any tree.

Having one lock per node is most likely not the correct solution.

Answer 4

John Valois' paper briefly describes an approach to implementing a binary search tree using auxilary nodes. I am using the auxilary node approach in my design of a concurrent LinkedHashMap. You can probably find many other papers on concurrent trees on CiteSeerX (an invaluable resource). I would stray away from using trees as a concurrent data collection unless truly necessary, as they tend to have poor concurrency characteristics due to rebalancing. Often more pragmatic approaches, like skip lists, work out better.

Answer 5

I played around making binary trees read lock-free using partial copy on write. I posted a incomplete implementation here http://groups.google.com/group/comp.programming.threads/msg/6c0775e9882516a2?hl=en&

Answer 6

Lock-free algorithms, as far as I can see, lack reference counts, which makes their general use problematic; you can't know if the pointer you have to an element is valid - maybe that element went away.

Valois' gets around this with some exotic memory allocation arrangement which is not useful in practise.

The only way I can see to do lock-free balanced trees is to use a modified MCAS, where you can also do increment/decrement, so you can maintain a reference count. I've not looked to see if MCAS can be modified in this way.