4 ms·
New algorithms are always welcome. But it isn't a general-purpose MPMC queue (nor does it claim to be). The following constraints are listed in the "Reasons not
by RossBencina 10y ago
New algorithms are always welcome. But it isn't a general-purpose MPMC queue (nor does it claim to be). The following constraints are listed in the "Reasons not to use" section:
- not linearizable wrt multiple producers
- not NUMA aware
- not sequentially consistent, quote: "things (such as pumping the queue until it's empty) require more thought to get right in all eventualities"
These are subtleties (especially the first and the last) that may bite if you don't know what you're doing and just want to "plug in a queue." It's going to depend on how you use the queue.
Side note: There are other examples of novel lock-free algorithms that have only been published by blog, powerpoint or github (e.g. Dmitry Vyukov's well-known work, Cliff Click's concurrent hash table, Jeff Preshing's hash table.) However, in general, lock-free algorithms are widely known to be very difficult to get correct (not too dissimilar to getting a Distributed Consensus Algorithm correct). I can't help thinking that we need a higher bar of correctness than the author's claims and some unit tests. Would you use a distributed algorithm that didn't come with a correctness proof? Personally I'd like to see a formal proof, peer review, and a Spin model. Peer-review need not be via academic channels, just something more than self-publication.
- hvidgaard 10y ago> I can't help thinking that we need a higher bar of correctness than the author's claims and some unit tests. Would you use a distributed algorithm that didn't come with a correctness proof? Not any chance. Using any multi party algorithm, without any formal proof of any kind, and you just know that there is something that will not work as expected.
- eternalban 10y ago> Would you use a distributed algorithm that didn't come with a correctness proof? That happens all the time in practice. Prior to Kyle Kingsbury's influential blogs on noSQL darlings, for example, it was not even on the geek-pop radar. And then, quite frankly, there is the gap between implementation and formal description of an algorithm. Incorrect implementation will obviate the guarantees your formal proof is asserting.
- RossBencina 10y ago> there is the gap between implementation and formal description of an algorithm. Incorrect implementation will obviate the guarantees your formal proof is asserting. Agree. One aspect of this wrt implementing lock-free algorithms in C++: Usually the academic papers assume a sequentially consistent memory model, so when you're implementing the algorithm you have to work out how to place the memory barriers correctly (a potentially non-trivial task, as other comments on this page demonstrate).