5 ms·

So I just recently learned how a rather simple ring buffer implementation is lock-free and doesn't even need primitives like CAS (although it does need memory b

So I just recently learned how a rather simple ring buffer implementation is lock-free and doesn't even need primitives like CAS (although it does need memory barriers). In spite of this, all the literature about lock-free queues that I see (including this one) is for some kind of linked structure. Any reason for that? I guess one big limitation of the ring buffer is that it only works for a single reader and single writer. Although maybe you can work around that using CAS primitves...

daigoba66 10y ago
A ring buffer has a limit to the number of unread items before you either block or start discarding. Different use cases I suppose.
- adrianratnapala 10y ago
  I think the fixed-size limitation is the least important thing in practice. If your queue is filling up arbitrarily far, then you are almost certainly in trouble anyway, and want some limitation strategy. The ring buffer gives you this quite naturally. I suppose there could be cases where you did not want to pre-commit to a buffer size. E.g. you have lots of queues which you expect to be short, but which might grow large in rare cases. But I have never actually seen such a case.
  - ramchip 10y ago
    I would expect it to be a common use case in actor-based systems like Erlang, Akka, etc. It's perfectly supported to have 100k+ processes running in an Erlang VM, but the vast majority of them will have an empty message queue at any given time.
    - adrianratnapala 10y ago
      Indeed large numbers of small queues are an important case. But large numbers of small queues, every one of which might unexpectedly but legitimately need to grow large is not. I don't know Erlang or Akka first hand, but I know that Go channels are inpsired by Erlang. Channels can be very numerous and are usually empty; but they are fixed size. In the rare occasion that you think a channel needs more buffering, you must say so explicilty.
Betelgeuse90 10y ago
I'm not sure you're aware of this, but there's a distinction between wait-free and lock-free. http://rethinkdb.com/blog/lock-free-vs-wait-free-concurrency/ http://rethinkdb.com/blog/lock-free-vs-wait-free-concurrency... This might be relevant to answering your question.
- jstimpfle 10y ago
  Wouldn't the ring buffer queue be also wait-free in this sense? (except that the number of unread items in the queue is restricted).
- adrianratnapala 10y ago
  I became aware of the distinction when I skimmed the paper. But I couldn't figure out what it meant in this case. Specifically does the every thread requirement rule out algorithms where there only one reader and one writer is allowed? If not, then this ring buffer is wait-free, since there is no CAS-and-retry step. (Of course an operation can fail because the queue is empty/full, but that is still completion).
  - the8472 10y ago
    there are several aspects to consider when talking about a concurrent queue: * multiple/single producer, multiple/single consumer * progress guarantees (wait-free, lock-free) * bounded vs. unbounded * whether it's double-ended or single-ended * memory reclamation being dependant on a GC or not * which atomic operations they need (e.g. some require double-CAS) What you mention is a spsc bounded queue. this is about a mpmc unbounded queue. And from skimming the paper is seems like it does not require a GC either. So it's far more powerful. Of course spsc queues still have their use even if we have a good mpmc queue, they generally incur less overhead.
ambrop7 10y ago
A ring buffer can work for a single writer and multiple readers, in the model that each element is received by all the readers. Each reader just needs their own read index and the writer probably needs to check all the read indices before writing a new element, to ensure it doesn't overwrite data still being read. And indeed it you want all readers to get all elements, I think a ring buffer is easier than a linked structure.
the8472 10y ago
fixed-size vs. variable size maybe?
scott_s 10y ago
The single-writer, single-reader limitation is a big deal. You can work around it, but it's no longer the same thing, as what makes such queues so fast is that they don't do CAS or other kinds of atomic operations at all. Such queues are extremely useful when you can ensure single-reader and single-writer, but it does not prevent us from need more general purpose solutions. More general solutions will require more synchronization, and if they do not want them to be fixed-sized structures, they will usually require some kind of linked structure. For practical examples of all of the above, see Boost's lockfree structures: http://www.boost.org/doc/libs/1_61_0/doc/html/lockfree.html http://www.boost.org/doc/libs/1_61_0/doc/html/lockfree.html

daigoba66 10y ago

A ring buffer has a limit to the number of unread items before you either block or start discarding. Different use cases I suppose.

adrianratnapala 10y ago
I think the fixed-size limitation is the least important thing in practice. If your queue is filling up arbitrarily far, then you are almost certainly in trouble anyway, and want some limitation strategy. The ring buffer gives you this quite naturally. I suppose there could be cases where you did not want to pre-commit to a buffer size. E.g. you have lots of queues which you expect to be short, but which might grow large in rare cases. But I have never actually seen such a case.
- ramchip 10y ago
  I would expect it to be a common use case in actor-based systems like Erlang, Akka, etc. It's perfectly supported to have 100k+ processes running in an Erlang VM, but the vast majority of them will have an empty message queue at any given time.
  - adrianratnapala 10y ago
    Indeed large numbers of small queues are an important case. But large numbers of small queues, every one of which might unexpectedly but legitimately need to grow large is not. I don't know Erlang or Akka first hand, but I know that Go channels are inpsired by Erlang. Channels can be very numerous and are usually empty; but they are fixed size. In the rare occasion that you think a channel needs more buffering, you must say so explicilty.

Betelgeuse90 10y ago

I'm not sure you're aware of this, but there's a distinction between wait-free and lock-free. http://rethinkdb.com/blog/lock-free-vs-wait-free-concurrency/ http://rethinkdb.com/blog/lock-free-vs-wait-free-concurrency... This might be relevant to answering your question.

jstimpfle 10y ago
Wouldn't the ring buffer queue be also wait-free in this sense? (except that the number of unread items in the queue is restricted).
adrianratnapala 10y ago
I became aware of the distinction when I skimmed the paper. But I couldn't figure out what it meant in this case. Specifically does the every thread requirement rule out algorithms where there only one reader and one writer is allowed? If not, then this ring buffer is wait-free, since there is no CAS-and-retry step. (Of course an operation can fail because the queue is empty/full, but that is still completion).
- the8472 10y ago
  there are several aspects to consider when talking about a concurrent queue: * multiple/single producer, multiple/single consumer * progress guarantees (wait-free, lock-free) * bounded vs. unbounded * whether it's double-ended or single-ended * memory reclamation being dependant on a GC or not * which atomic operations they need (e.g. some require double-CAS) What you mention is a spsc bounded queue. this is about a mpmc unbounded queue. And from skimming the paper is seems like it does not require a GC either. So it's far more powerful. Of course spsc queues still have their use even if we have a good mpmc queue, they generally incur less overhead.

ambrop7 10y ago

A ring buffer can work for a single writer and multiple readers, in the model that each element is received by all the readers. Each reader just needs their own read index and the writer probably needs to check all the read indices before writing a new element, to ensure it doesn't overwrite data still being read. And indeed it you want all readers to get all elements, I think a ring buffer is easier than a linked structure.

the8472 10y ago

fixed-size vs. variable size maybe?

scott_s 10y ago

The single-writer, single-reader limitation is a big deal. You can work around it, but it's no longer the same thing, as what makes such queues so fast is that they don't do CAS or other kinds of atomic operations at all. Such queues are extremely useful when you can ensure single-reader and single-writer, but it does not prevent us from need more general purpose solutions. More general solutions will require more synchronization, and if they do not want them to be fixed-sized structures, they will usually require some kind of linked structure. For practical examples of all of the above, see Boost's lockfree structures: http://www.boost.org/doc/libs/1_61_0/doc/html/lockfree.html http://www.boost.org/doc/libs/1_61_0/doc/html/lockfree.html