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.
