3 ms·

The MPSC/MPMC structure in Aeron is wait-free with respect to producers - one producer cannot block another There are simple node based algorithms that achieve

by nly 3mo ago

The MPSC/MPMC structure in Aeron is wait-free with respect to producers - one producer cannot block another There are simple node based algorithms that achieves a similar guarantee: https://web.archive.org/web/20240928080729/https://www.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue https://web.archive.org/web/20240928080729/https://www.1024c... There is also a MPMC algorithm on this site very similar to the article https://web.archive.org/web/20220524214823/https://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue https://web.archive.org/web/20220524214823/https://www.1024c...

platinumrad 3mo ago
Both Vyukov queues are fast and useful in practice, but neither is even obstruction-free, let alone lock-free or wait-free.
- nly 3mo ago
  What's important is you know the trade-offs you are making. You can't have a bounded queue that is always non-blocking because slow consumers can block producers. You can't have a global FIFO order + multiple producers without slow producers blocking consumers. You can't have a global FIFO order + have have non-atomic reserve and commit without a interrupted/de-scheduled producer thread being able to block the consumer If you want atomic commit then you lose separate reserve which means either unbounded memory or atomic fixed-size data with sentinel values, ABA problems etc. There are trade-offs everywhere, and it's best to pick the data structure that fits your needs just like any other problem.
  - tialaramex 3mo ago
    > There are trade-offs everywhere, and it's best to pick the data structure that fits your needs just like any other problem. That part I think is most crucial. Neither "Lock-free" nor "Wait-free" are vague terms for how awesome a thing is, they're specific properties which are expensive to provide, if you need such a property it was indispensable, if you don't need it then you can likely do better without it.
    - platinumrad 3mo ago
      Exactly. I mentioned that those queues aren't formally obstruction-free because the context of the conversation was new developments in wait-free queues, even though I have only needed the guarantee once in my career and end up using descendants of the Vyukov MPMC cycle queue in practically all other cases because they are better on the metrics that count, like speed.
      - nly 3mo ago
        What was the one time when you need something wait free? I'm assuming interacting with hardware?
        platinumrad 3mo ago
        Hard real-time industrial automation. Worst job ever, by the way.
        tialaramex 3mo ago
        I don't think any of my immediate opportunities are "real-time industrial automation" shaped, but, can't hurt to ask: Do you think it was the work that inherently was the worst ever, or was there some other enviromental factor (e.g. terrible wages, for some reason your office was up six flights of stairs with no elevator, colleague insisted on playing music from your least favourite genre at maximum volume) ?
        platinumrad 2mo ago
        It was the work itself. Embedded systems are already known for bad tooling. Once safety certification gets thrown in the mix you're limited to ancient broken versions of GCC that have been rebranded and certified, and are thus more fit for purpose than newer versions of GCC that actually work. MISRA, its derivatives, and the associated static analysis tooling ecosystem are also low quality evolutionary dead ends that ignore the state of the art in both academia and industry.
dorjoycb 3mo ago
Nice to see Vyukov's MPMC queue mentioned. It's pretty neat. I have used a C implementation[1] of this in a small personal project. [1]: https://github.com/dorjoy03/dsync/blob/master/src/mpmc_queue_generic.h https://github.com/dorjoy03/dsync/blob/master/src/mpmc_queue...

by nly 3mo ago

platinumrad 3mo ago

Both Vyukov queues are fast and useful in practice, but neither is even obstruction-free, let alone lock-free or wait-free.

nly 3mo ago
What's important is you know the trade-offs you are making. You can't have a bounded queue that is always non-blocking because slow consumers can block producers. You can't have a global FIFO order + multiple producers without slow producers blocking consumers. You can't have a global FIFO order + have have non-atomic reserve and commit without a interrupted/de-scheduled producer thread being able to block the consumer If you want atomic commit then you lose separate reserve which means either unbounded memory or atomic fixed-size data with sentinel values, ABA problems etc. There are trade-offs everywhere, and it's best to pick the data structure that fits your needs just like any other problem.
- tialaramex 3mo ago
  > There are trade-offs everywhere, and it's best to pick the data structure that fits your needs just like any other problem. That part I think is most crucial. Neither "Lock-free" nor "Wait-free" are vague terms for how awesome a thing is, they're specific properties which are expensive to provide, if you need such a property it was indispensable, if you don't need it then you can likely do better without it.
  - platinumrad 3mo ago
    Exactly. I mentioned that those queues aren't formally obstruction-free because the context of the conversation was new developments in wait-free queues, even though I have only needed the guarantee once in my career and end up using descendants of the Vyukov MPMC cycle queue in practically all other cases because they are better on the metrics that count, like speed.
    - nly 3mo ago
      What was the one time when you need something wait free? I'm assuming interacting with hardware?
      - platinumrad 3mo ago
        Hard real-time industrial automation. Worst job ever, by the way.
        tialaramex 3mo ago
        I don't think any of my immediate opportunities are "real-time industrial automation" shaped, but, can't hurt to ask: Do you think it was the work that inherently was the worst ever, or was there some other enviromental factor (e.g. terrible wages, for some reason your office was up six flights of stairs with no elevator, colleague insisted on playing music from your least favourite genre at maximum volume) ?
        platinumrad 2mo ago
        It was the work itself. Embedded systems are already known for bad tooling. Once safety certification gets thrown in the mix you're limited to ancient broken versions of GCC that have been rebranded and certified, and are thus more fit for purpose than newer versions of GCC that actually work. MISRA, its derivatives, and the associated static analysis tooling ecosystem are also low quality evolutionary dead ends that ignore the state of the art in both academia and industry.

dorjoycb 3mo ago

Nice to see Vyukov's MPMC queue mentioned. It's pretty neat. I have used a C implementation[1] of this in a small personal project. [1]: https://github.com/dorjoy03/dsync/blob/master/src/mpmc_queue_generic.h https://github.com/dorjoy03/dsync/blob/master/src/mpmc_queue...