On 27/10/2015 11:05, Gottlob Frege wrote:
NOTE: None of the above means it is a bad queue; that remains to be seen. It is just not lock-free. It may typically perform better than lock-free. And lock-free is typically about performance. But note that it is also about being robust and deadlock free, etc. So it may depend on use cases.
Performance is a tricky subject with lock-free. Often uncontended performance is worse. But the main reason they exist is to provide better worst-case guarantees for latency in particular in the face of contention. (Typically the key improvement is that at least one running thread can always make forward progress, unlike lock-based structures where one thread can make progress, but it is not necessarily running.)
See also, https://www.youtube.com/watch?v=Xf35TLFKiO8 which starts to describe my array-based MPMC queue. The C++Now version is better, but those videos aren't available yet. I'd blame Marshall here, but he's volunteering his own time, so let's be patient.
My queue uses CAS and I don't claim that it is fast. I'm doing it for theoretical correctness first. (It also, at least in the video, does not yet handle anything beyond ints).
My current favourite mostly-lock-free MPMC queue is Dmitry Vyukov's (http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue).