4 ms·

32bit here turns out to mean head and tail indices are in the same 32bit integer and the data is somewhere else. That's enough to put head and tail in the same

32bit here turns out to mean head and tail indices are in the same 32bit integer and the data is somewhere else. That's enough to put head and tail in the same cache line, so it's a disaster for performance on roughly any platform. The mpmc variant looks non-serialising (threads push multiple things before another manages to push one) so it's not a queue, and it has a cas loop in it so lock-free is a bit of a stretch.

binarycoffee 4y ago
Note that the second variant does not claim to be MPMC, only SPMC. Many lock-free structures use CAS loops. It would not be lock-free if a consumer pre-empted at the wrong time could prevent other consumers to make progress, but I don't think this is the case here.
bob1029 4y ago
Head and tail not being the same abstraction is the central theme for why alternatives like the LMAX Disruptor are so fast, even in MP/MC scenarios.
- pclmulqdq 4y ago
  This queue seems to have issues with multi-producer operation. Each producer busy polls until the previous producer finishes. What happens if the previous producer gets de-scheduled while you are busy polling? You keep occupying a core that the other thread could use to do useful work. When I transitioned from trading to tech, I realized that HFT data structures have limited usefulness when you are not also doing HFT. You can do a lot more things lock-free when you don't have to worry about adverse scheduling. By the way, there is no easy way to fix this with an MPMC ring buffer. You have to accept some chance of adverse behavior. There may be something complicated you can do, but it's easier to just split into multiple rings.
  - bob1029 4y ago
    > What happens if the previous producer gets de-scheduled while you are busy polling? You keep occupying a core that the other thread could use to do useful work. This is why newer versions of LMAX offer additional wait strategies beyond BusyWait. The one I prefer to use, unless latency is absolutely insanely critical, is the YieldingWait strategy.
    - pclmulqdq 4y ago
      If yieldingwait does what I think it does, this does not work nearly as effectively as you might think. I am assuming that YieldingWait just calls "sched_yield" once in a while, assuming that the kernel will interpret that correctly. That is a bad assumption: the kernel gets sched_yield calls in a lot of places and it means different things to different people. If YieldingWait does a proper yield, by calling futex, well then it's not really lock free any more.
anthomtb 4y ago
Why is having head and tail in the same cache line bad for performance? Given that the code reads both head and tail to check if the queue is empty, being in the same cache line seems optimal.
- anthomtb 4y ago
  https://rigtorp.se/ringbuffer/ https://rigtorp.se/ringbuffer/, from a comment below, answered my question. In rough terms, every push or pop from the queue also causes head or tail to be written, thus dirtying a line of cache. That’s the bit I misunderstood.
  - binarycoffee 4y ago
    To be clear, as mentioned in another thread [0] there is no need to ensure consistency between head and tail for a SPSC so storing them in different cache lines would be much better. For the multiple-consumer variant, however, consistency between head and tail is required so packing them in the same atomic is the simplest solution. [0] https://news.ycombinator.com/item?id=31386741 https://news.ycombinator.com/item?id=31386741
atq2119 4y ago
> it has a cas loop in it so lock-free is a bit of a stretch. To be fair, if that's your standard, there are virtually no lock-free algorithms. The multi-consumer has a wait-free retry loop. That's pretty much as good as it gets. And the SPSC case is lock-free under even the strictest definitions, though of course that's not particularly difficult to achieve.
- JonChesterfield 4y ago
  That's reasonable. I'm twitchy about CAS loops because I'm used to unfair schedulers, but they're a great choice in Linux/x64 land

binarycoffee 4y ago

Note that the second variant does not claim to be MPMC, only SPMC. Many lock-free structures use CAS loops. It would not be lock-free if a consumer pre-empted at the wrong time could prevent other consumers to make progress, but I don't think this is the case here.

bob1029 4y ago

Head and tail not being the same abstraction is the central theme for why alternatives like the LMAX Disruptor are so fast, even in MP/MC scenarios.

pclmulqdq 4y ago
This queue seems to have issues with multi-producer operation. Each producer busy polls until the previous producer finishes. What happens if the previous producer gets de-scheduled while you are busy polling? You keep occupying a core that the other thread could use to do useful work. When I transitioned from trading to tech, I realized that HFT data structures have limited usefulness when you are not also doing HFT. You can do a lot more things lock-free when you don't have to worry about adverse scheduling. By the way, there is no easy way to fix this with an MPMC ring buffer. You have to accept some chance of adverse behavior. There may be something complicated you can do, but it's easier to just split into multiple rings.
- bob1029 4y ago
  > What happens if the previous producer gets de-scheduled while you are busy polling? You keep occupying a core that the other thread could use to do useful work. This is why newer versions of LMAX offer additional wait strategies beyond BusyWait. The one I prefer to use, unless latency is absolutely insanely critical, is the YieldingWait strategy.
  - pclmulqdq 4y ago
    If yieldingwait does what I think it does, this does not work nearly as effectively as you might think. I am assuming that YieldingWait just calls "sched_yield" once in a while, assuming that the kernel will interpret that correctly. That is a bad assumption: the kernel gets sched_yield calls in a lot of places and it means different things to different people. If YieldingWait does a proper yield, by calling futex, well then it's not really lock free any more.

anthomtb 4y ago

Why is having head and tail in the same cache line bad for performance? Given that the code reads both head and tail to check if the queue is empty, being in the same cache line seems optimal.

anthomtb 4y ago
https://rigtorp.se/ringbuffer/ https://rigtorp.se/ringbuffer/, from a comment below, answered my question. In rough terms, every push or pop from the queue also causes head or tail to be written, thus dirtying a line of cache. That’s the bit I misunderstood.
- binarycoffee 4y ago
  To be clear, as mentioned in another thread [0] there is no need to ensure consistency between head and tail for a SPSC so storing them in different cache lines would be much better. For the multiple-consumer variant, however, consistency between head and tail is required so packing them in the same atomic is the simplest solution. [0] https://news.ycombinator.com/item?id=31386741 https://news.ycombinator.com/item?id=31386741

atq2119 4y ago

> it has a cas loop in it so lock-free is a bit of a stretch. To be fair, if that's your standard, there are virtually no lock-free algorithms. The multi-consumer has a wait-free retry loop. That's pretty much as good as it gets. And the SPSC case is lock-free under even the strictest definitions, though of course that's not particularly difficult to achieve.

JonChesterfield 4y ago
That's reasonable. I'm twitchy about CAS loops because I'm used to unfair schedulers, but they're a great choice in Linux/x64 land