HackerTrans
TopNewTrendsCommentsPastAskShowJobs

SUPERCILEX

no profile record

Submissions

Lockless MPSC/SPMC/MPMC queues are not queues

alexsaveau.dev
39 points·by SUPERCILEX·10 माह पहले·31 comments

The need for new instructions: atomic bit fill and drain

alexsaveau.dev
3 points·by SUPERCILEX·10 माह पहले·0 comments

comments

SUPERCILEX
·10 माह पहले·discuss
Fair point, though I'm not sure I agree. MPMC channels underpin pretty much every general task scheduler (take a peek inside tokio or rayon for example). And SPSCs are quite useful for designing custom pipelines. Though I agree that MPMC channels are silly.
SUPERCILEX
·10 माह पहले·discuss
As noted by other commenters, the point I was trying to get across is that the way we implement lockless channels is suboptimal and could be made faster from a theoretical standpoint.

In my benchmarks[1], the average processing time for an element is 250ns with 4 producers and 4 consumers contending heavily. That's terrible! Even if your numbers are correct, 100ns is a bit faster than two round trips to RAM while 33ns is about three round trips to L3 and ~100x slower than spamming a core with add operations. That's slow.

[1]: https://github.com/SUPERCILEX/lockness/blob/master/bags/benc... $ cargo bench -- 8_threads/std_mpmc
SUPERCILEX
·10 माह पहले·discuss
Thanks for sharing, I had not! It sounds like "processor sharing" would be the expected mode of operation for lockless queues. But see my comment to the parent, this is not how they work.
SUPERCILEX
·10 माह पहले·discuss
This is actually a great analogy because it exemplifies the misconceptions people have about lockless queues.

In the example with multiple counters, in real life each counter could shout out a number and have people approach their respective counters in parallel. But this is not how lockless queues work. Instead, the person at the head of the queue holds a baton and when multiple numbers are called, everybody waiting in the queue goes up to the counter of the person holding the baton. Once that head-of-the-queue has made it to the counter, they give the baton to the person behind them who then drags everybody along to their counter. And so on.

The article was arguing for a lockless channel implementation akin to your interpretation of a queue with parallel access to the counters.