Wait-free MPSC and MPMC implement in D

[Andy Smith]

On Tuesday, 8 May 2018 at 22:09:37 UTC, David Nadlinger wrote:
> 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

What's MPSP? :-)

During Shachar's talk on the Saturday morning following the 
conclusion of Dconf he made it clear that the Mecca library is 
being used by the ~200klock Weka.io codebase ... a codebase which 
has very stringent latency *and* throughput requirements to 
satisfy customer needs in the storage space.

So if any D codebase has got bragging rights on the term 
'industry-grade' I think this has to be one of them. So if 
they've copy/pasted a few comments ... meh ... I for one happy to 
let it slide. These guys have got bigger fish to fry :-)

Cheers,

A.