Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lockless MPSC/SPMC/MPMC queues are not queues

alexsaveau.dev

Post reply on HN
Print view View original

11–20 of 32 posts

Re: Lockless MPSC/SPMC/MPMC queues are not queues

#11

Post by BlackFly »

imtringued wrote: post #2

The blog post gatekeeps the definition of "queue" to require a global processing order, (not just merely global dequeue order following the FIFO principle) when the vast majority of real life queues have no such constraint whatsoever. If you go to the the city hall and they have multiple counters, you pull a ticket with your number. There is a global order of dequeue operations. The first person to pull a ticket will…

Yes, the author hasn't heard the term "service discipline" before. Sure, queuing theory is easier if you don't consider all the various service disciplines that real life queues use in practice (both physical queues and digital queues).

Re: Lockless MPSC/SPMC/MPMC queues are not queues

#12

Post by pkhuong »

pclmulqdq wrote: post #9
DannyBee wrote: post #6

Ignoring all the other problems with this article that have been pointed out around definitions, it also claims that lockless is slow anyway. Without giving literally any data. Good news: it's not slow Let's take rust, which has an oddly thriving ecosystem of lockless mpsc/mpmc/etc queues, and lots of benchmarks of them in lots of configurations. The fastest ones easily do at least 30 million elements/second in most…

I have always found MPMC ring buffers to have worse tails than pointer-based MPMC queues. These are very unfashionable (especially in rust) but can be made wait-free with a single atomic for readers and writers. The SPSC ring buffer is perfect, but adding either more producers or more consumers makes the whole thing have terrible pathologies. Reading the article again, this lockless bag idea also needs two atomic wri…

SPMC ring buffer or SPMC "disruptor" aren't that bad. Multiple producers in a general ring buffer definitely introduce a lot of issues.

Re: Lockless MPSC/SPMC/MPMC queues are not queues

#13

Post by pclmulqdq »

pkhuong wrote: post #12
pclmulqdq wrote: post #9

Earlier quoted context omitted.

I have always found MPMC ring buffers to have worse tails than pointer-based MPMC queues. These are very unfashionable (especially in rust) but can be made wait-free with a single atomic for readers and writers. The SPSC ring buffer is perfect, but adding either more producers or more consumers makes the whole thing have terrible pathologies. Reading the article again, this lockless bag idea also needs two atomic wri…

SPMC ring buffer or SPMC "disruptor" aren't that bad. Multiple producers in a general ring buffer definitely introduce a lot of issues.

The "disruptor" pattern has some significant problems with tail performance (around pathological OS scheduling) if you aren't running one thread per core the way LMAX designed it.

Re: Lockless MPSC/SPMC/MPMC queues are not queues

#14

Post by SUPERCILEX »

imtringued wrote: post #2

The blog post gatekeeps the definition of "queue" to require a global processing order, (not just merely global dequeue order following the FIFO principle) when the vast majority of real life queues have no such constraint whatsoever. If you go to the the city hall and they have multiple counters, you pull a ticket with your number. There is a global order of dequeue operations. The first person to pull a ticket will…

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.

Re: Lockless MPSC/SPMC/MPMC queues are not queues

#15

Post by SUPERCILEX »

BlackFly wrote: post #11
imtringued wrote: post #2

The blog post gatekeeps the definition of "queue" to require a global processing order, (not just merely global dequeue order following the FIFO principle) when the vast majority of real life queues have no such constraint whatsoever. If you go to the the city hall and they have multiple counters, you pull a ticket with your number. There is a global order of dequeue operations. The first person to pull a ticket will…

Yes, the author hasn't heard the term "service discipline" before. Sure, queuing theory is easier if you don't consider all the various service disciplines that real life queues use in practice (both physical queues and digital queues).

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.

Re: Lockless MPSC/SPMC/MPMC queues are not queues

#16

Post by weinzierl »

"They come in four variants: {single,multi}-producer {single,multi}-consumer."

The article makes it sound a bit as if they were all created equal, while I think only MPSC is really used widely. The others are all kind if niche, because usually we have better solutions for the problems they are suitable for.

Re: Lockless MPSC/SPMC/MPMC queues are not queues

#17

Post by SUPERCILEX »

DannyBee wrote: post #6

Ignoring all the other problems with this article that have been pointed out around definitions, it also claims that lockless is slow anyway. Without giving literally any data. Good news: it's not slow Let's take rust, which has an oddly thriving ecosystem of lockless mpsc/mpmc/etc queues, and lots of benchmarks of them in lots of configurations. The fastest ones easily do at least 30 million elements/second in most…

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

Re: Lockless MPSC/SPMC/MPMC queues are not queues

#18

Post by SUPERCILEX »

weinzierl wrote: post #16

"They come in four variants: {single,multi}-producer {single,multi}-consumer." The article makes it sound a bit as if they were all created equal, while I think only MPSC is really used widely. The others are all kind if niche, because usually we have better solutions for the problems they are suitable for.

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.

Re: Lockless MPSC/SPMC/MPMC queues are not queues

#19

Post by RHSeeger »

habibur wrote: post #8

I don't know what others are reading. The article basically says that when you have multiple suppliers or consumers, the "order" of the queue loses meaning. It turns into an "unordered" pool of data. Therefore focus should be shifted from maintain a "queue of data" to a "bag of data".

> The article basically says that when you have multiple suppliers or consumers, the "order" of the queue loses meaning.

The disconnect to me is that the title says "it's not a queue". It is a queue, its just (as you note) not being used in a way where it being a queue provides any benefit.

Re: Lockless MPSC/SPMC/MPMC queues are not queues

#20

Post by j_seigh »

I did do an actual lock-free MPMC ring buffer implementation as an exercise. I used that to make blocking bounded queues using various synchronization mechanisms, mutex/condvars and eventcounts among others. The eventcount version runs about 8x faster than the mutex version.
Post reply on HN