I think the more important question would be "can we make concurrent self-adjusting data structures that do not need stop-the-world rebuilding steps to avoid the worst case behavior?" Sure, you can amortize the rebuilding over multiple queries but if you're interested in worst case latency for any operation, stop-the-world logic works really bad for the worst case latency. This is no different from why Java sucks for concurrent low-latency stuff.
Dear Mikko, That is a really good question and comment. At first, it does not need stop-the-world in lock-based manner - it is possible to do the rebuilding lock-free: the operations can help each other. Secondly, indeed we are currently looking on how to achieve a logarithmic worst-case upper bound on operations.
I think the more important question would be "can we make concurrent self-adjusting data structures that do not need stop-the-world rebuilding steps to avoid the worst case behavior?"
Sure, you can amortize the rebuilding over multiple queries but if you're interested in worst case latency for any operation, stop-the-world logic works really bad for the worst case latency. This is no different from why Java sucks for concurrent low-latency stuff.
Dear Mikko,
That is a really good question and comment. At first, it does not need stop-the-world in lock-based manner - it is possible to do the rebuilding lock-free: the operations can help each other. Secondly, indeed we are currently looking on how to achieve a logarithmic worst-case upper bound on operations.
nerds 😂