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-25 23:02:37

On 2015-10-23 15:53, Giovanni Piero Deretta wrote:
> On Fri, Oct 23, 2015 at 7:41 PM,  <boost_at_[hidden]> wrote:
>> On 2015-10-22 03:18, Giovanni Piero Deretta wrote:
>>> 
>>> On 22 Oct 2015 9:04 a.m., "Gavin Lambert" <gavinl_at_[hidden]> 
>>> 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.
>>>> 
>>> Lock free still requires at least one thread to make progress in any
>>> situation. If this were the case  yield wouldn't be necessary. As I t 
>>> is I
>>> do not think it qualifies even as obstruction-free.
>> 
>> Assuming all threads are currently schedule, then multiple reader and 
>> writer
>> threads make progress on average, and at least one reader thread and 
>> one
>> writer thread will make progress.  Assuming all threads are scheduled, 
>> it is
>> absolutely obstruction free, and lock free.  It is 'mostly' wait 
>> free...
>> the waiting is the time it takes to increment the trailing edge of 
>> either
>> back (for writers) or front (for readers).
>> 
> 
> According to your previous description, it seems to me that a writer
> could be blocked forever waiting for a preempted, dead thread or
> blocked thread. Similarly for a reader.

If the yield bit is removed from the push/pop implementation, I think 
you will find the statement above about assumptions to be accurate upon 
investigation of implementation, assuming the implementation is correct. 
  It would be fabulous if anyone could spot errors in implementation, let 
me know if they think it is correct.  It may very well be that there are 
no generalized use cases where higher throughput is needed in a queue 
with larger numbers of readers/writers.  However, I would expect there 
is at least limited utility for some work loads... I was hoping there 
would be some interest on this list if there was.