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: boost_at_[hidden]
Date: 2015-10-23 14:35:08

On 2015-10-22 03:03, Gavin Lambert wrote:
> On 22/10/2015 20:57, Giovanni Piero Deretta wrote:
>> It seems to me then it is not really lock free then, right?
> 
> There's a difference between "lock free" and "wait free" (though I
> haven't examined the code to see which most correctly applies here).
> 
> Wait-free is better than lock-free, of course, but it's also
> incredibly hard to achieve in an MPMC problem.

Strictly speaking it is not wait-free, because all writers in push() 
have to wait for the writer before them to complete (increment trail 
edge index by 1) before they can complete (increase the trail edge index 
by 1).  However, this is the only waiting part, they don't have to wait 
to write their item into the queue (assuming there are empty slots in 
the queue).  The readers behave symmetrically.

The one advantage of this queue (assuming the implementation is correct) 
is that there is lower contention than methods that use compare_exchange 
(and therefore spend more time colliding and waiting).