Non-blocking operations

[Joel Fuentes]

Hi,

Are you planning to implement this library as non-blocking for all operations (insert, read, remove, etc)?

I've worked on a prototype with your radix tree, I got better performance but still more improvements are needed to be more scalable as the number of threads increases.

Best,

Joel

[Niall]

Hi Joel,

I did consider concurrent writes in the past, but I don't have any immediate plans to support concurrent writes at the moment.

The main challenge with concurrent writes, is that it might be necessary to apply locking to regions of the tree, to ensure that a modification made by one thread could not inadvertently become detached from the tree by a concurrent modification made by another thread.

With radix trees, any modification which updates the root node, or a node near the root, might therefore require a large section of the tree to be locked. These locks would not impact reads as they may use the atomic patching mechanism already employed, but they would impact the performance of concurrent writing threads. And as we would not have any control over which operations could lock large sections of the tree, the latency due to locking could be variable.

There might be other options though. For example to define a mechanism to reorder pending writes so that they would not overwrite each other. It's an interesting question so I'm open to ideas!

Best regards,

Niall