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: Gottlob Frege (gottlobfrege_at_[hidden])
Date: 2015-10-26 18:05:03

On Tue, Oct 20, 2015 at 11:02 PM,  <boost_at_[hidden]> wrote:
> Is there any interest in an alternate implementation of a lockfree queue
> that doesn't use compare_exchange (assuming it is correct, or can be made to
> be correct)?
>

<...>

> This was tested on Windows 7 x64 with Inel Xeon X5355 x 2 (2 sockets w/ 4
> cores a piece) @ 2.66 Ghz and 32 GB RAM @ 667 MHz.

P.S. Intel isn't the best place to test lock-free code.  You need
crazy platforms with more relaxed guarantees.

>
> The implementation can be found here:
> https://github.com/benmccart/GuarunteedMpmcQueue/blob/master/queue/queue.hpp
>
> Is the implementation correct?  Can anyone spot any race conditions, or
> conditions under which the implementation would fail to work as expected
> (other than queue is full/empty or over-subscription)?
>

I took a quick look, I may easily have misunderstood the code:

So you have a leading edge and trailing edge on both front and back. OK.

So on push, we incr leading edge, reserving a space.  When we are
done, we incr the trailing edge.

But we can't incr the trailing edge until every other pusher has
incremented the trailing edge, correct?
ie between trail and lead, we have some partially constructed
elements, and we can't move trail until we know the one on that edge
is completely written.  ie the important part is that everything
before trail MUST be completely written.  That is our invariant.

It appears to me, then, that if T's copy/move constructor decides to
grab a lock, or deadlock, or kill its own thread, all other pushers
stop, waiting for the trailing pusher to finish, even though it may
never do so.

Is that correct?

If so, it is not lock free.  Answer the question: "Is there ANY point
in the program where an idiot could kill a thread and cause the
algorithm to break?" If the answer is yes, then it is not lock free.
It may be obstruction free, I haven't thought about it enough.

The other question is "do I have comments in the code starting with
the word 'wait'?"  If so, it is probably not lock free.

Also, eventually, pullers will also wait forever, as they appear to
spin-lock on empty.

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.

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

Tony