an experimental bounded mpmc-queue algorithm...

[Chris M. Thomasson]

First of all, study this beautiful algorithm invented by Dmitriy Vyukov:

http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue


Notice the wonderful thing he is doing with the version counters? 1
CMPXCHG-loop per operation... Pretty darn good for a MPMC bounded queue! I
have noticed that the version counts could be used to create a distributed
bakery algorithm such that a fast-path consists of 1 XADD, and some loads
and stores with acquire/release memory ordering on the version count
contained within the buffer cells; here is a crude test program:

http://pastebin.com/cumRgj4n


btw, you need the latest version of Relacy (e.g., 2.4) to run it:

http://www.1024cores.net/home/relacy-race-detector


It think the algorithm is fairly different than Dmitriy's. Unfortunately, I
think I see a fairly rare race condition happening in which 2 threads are
producers and one of those does XADD, gets 0 and _stalls_... Then the other
producer performs UINT_MAX pushes and rolls the counter back to zero. The
next producer that comes in will get zero as the result of it's XADD... Then
the stalled thread decides to run right then and there; Ouch! Perhaps a
64-bit counter is in order. Joe Seigh has a very neat 63-bit atomic counter
algorithm. Humm... Need to think...



BTW, I will explain the queue algorithm in greater detail. No time right
now. Sorry!

;^(