2 ms·

A very nice approach for read heavy structures is the Left-Right algorithm. http://concurrencyfreaks.blogspot.com/2013/12/left-right-classical-algorithm.html?m

• jlokier 4y ago
  It's a fine algorithm, but in left-right those atomic increments/decrements on read can be costly, up to some 200x slower than the read itself. The "wait until" steps in the writer can also be an issue if the atomic decrements in the reads are not signalling writer wakeups, in a pre-emptive scheduling environment. The description doesn't mention the memory barriers that are also required, and which are also a little costly on some architectures. This is still better than a mutex or reader-writer lock for performance. (But it has different read-after-write behaviour than a mutex, so they aren't directly comparable; sometimes you still need a mutex). Where possible and optimising specifically for wait-free read performance, I would aim for RCU-style reads for speed. RCU reads are as fast as normal reads, because they are atomic-free as well as wait-free, and on almost all architectures do not require barrier instructions either. However the writes are more expensive and sometimes a lot more complicated. It is possible to combine left-right and RCU into a hybrid algorithm that uses fixed memory with grace periods, to combine the no-allocation property with the fast atomic-free reads property.