Wait-free MPSC and MPMC implement in D

[David Nadlinger]

On Tuesday, 8 May 2018 at 17:20:33 UTC, Dmitry Olshansky wrote:
> On Tuesday, 8 May 2018 at 04:00:03 UTC, manumaster wrote:
>> Is there some implement like this in D ?
>>
>> https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/multilist-2017.pdf
>
> Look for Mecca by Wekka.io team.  It has great idustry-grade 
> lock-free implementations for both. Not very flexible but these 
> things usually are.

Are you referring to 
https://github.com/weka-io/mecca/blob/master/src/mecca/containers/otm_queue.d?

These are SPMC and MPSC variants only, not MPSP.  It is also 
bounded-length (power-of-two sizes only), whereas the paper 
mentioned implements a linked-list based version.

The algorithm isn't wait-free (haven't thought too carefully 
about this, though), and should be used with a queue size much 
larger than the number of threads to make sure all of them make 
progress.

If you are considering to use it in your projects, definitely 
keep an eye on the real-world performance in the beginning (but 
then, if you weren't, you wouldn't be reaching for something like 
this anyway). There are a few interesting points about the 
algorithm in this respect; for example, the availability of queue 
space is checked with loads that use only raw memory order, as 
changes typically appear fast enough across cores on x86 anyway. 
If your use case is similarly enough to Weka's, it is indeed very 
highly optimised, though.

As far as industry-grade goes, note that many of the comments 
have not been updated since a previous combined implementation 
for SPMC/MPSC was split up into two types, so there is quite a 
bit of stale cruft around.

  — David