On Tue, Oct 20, 2015 at 11:02 PM,
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