Re:CX: Wait-Free Universal Construction
by amluto on Thursday November 07, 2019 @03:15PM
(#21476857)
> It also consumes larges amounts of memory and in the very unlikely worst case, may require 2x MAX_THREADS replicas of the sequential object.
Depending on how many threads are involved, I have a simple construction [0] that is likely to scale much better. It uses multiple copies of the data structure, but each successive copy is used only half as often, resulting in logarithmic amortized complexity.
IMO these types of constructions only make sense when reads are far more common than writes. Using this for an std::set is ridiculous — if you really want to apply one of these constructions to a mapping, you should build a whole new optimized seat structure for each write. Or maybe you could cleverly use immutable data structures to improve memory and bandwidth usage.
Depending on how many threads are involved, I have a simple construction [0] that is likely to scale much better. It uses multiple copies of the data structure, but each successive copy is used only half as often, resulting in logarithmic amortized complexity.
IMO these types of constructions only make sense when reads are far more common than writes. Using this for an std::set is ridiculous — if you really want to apply one of these constructions to a mapping, you should build a whole new optimized seat structure for each write. Or maybe you could cleverly use immutable data structures to improve memory and bandwidth usage.
[0] https://link.springer.com/chapter/10.1007%2F978-3-540-92221-...