Re: [boost] boost lockfree queue.hpp - alternate implementation w/o compare_exchange

Subject: Re: [boost] boost lockfree queue.hpp - alternate implementation w/o compare_exchange
From: Gavin Lambert (gavinl_at_[hidden])
Date: 2015-10-26 19:29:34

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).