Live data from Hacker News

Lockless MPSC/SPMC/MPMC queues are not queues

alexsaveau.dev

31–32 of 32 posts

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

#31

Earlier quoted context omitted.

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.

In principle there is an infinite number of possibilities for service disciplines, since it is an arbitrary function to select an element from sets. Service disciplines can also include randomness. I only know the basics of the mathematics of queue theory, but my introduction to it gave me the impression that almost anything but the most basic of disciplines didn't have closed form solutions to most questions. Like many models, you can introduce some things as approximations to get close enough answers. I personally prefer simulation, but that has its own problems.

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

#32
Possible compromise between space and time efficiency: use bytes instead of bits to mark reserved/committed slots. This wastes 7/8 of space but you can now use ordinary byte-width loads/stores instead of CAS (these are guaranteed to be atomic on both x86 and ARM). You still have false sharing of course, but it's diluted somewhat and you avoid atomic RMW overhead. The other problem of course is that you now have 8x more memory to scan for free slots, so not sure whether it's a good tradeoff; only benchmarking will tell.
Post reply on HN