1. 19
  1.  

  2. 12

    The reason that Tim Harris (and / or Keir Fraser’s?) lockless ring buffer uses separate words for the producer and consumer queue is twofold:

    • You don’t need to worry about overflow. In this version, when you increment the counter in the low bits, it can overflow into the high bits. In their version, as long as the size of the queue is less than half the range of the integer, you can always just mask off the low bits. The wrapping behaviour of C unsigned integers means that the arithmetic for calculating the amount of free space is a simple subtraction even if either counter overflows.
    • The producer and consumer counters can be concurrently written from different cores. Putting them in the same word increases false sharing. Typically, you’d want to put them in separate cache lines (you can save some space by putting one in front of the ring and one after, which gives you some false sharing when you use the first / last entries in the ring but not for the common case).
    1. 4

      Another point for using separate words is that the single-producer and single-consumer cases can use an atomic store to commit instead of an atomic read-modify-write; The former of which (with release semantics) reduces to a normal store on x86.

      1. 3

        I was curious so I looked for this…

        I don’t know if any of these are precisely what you’re referring to…

        1. 2

          The one that’s used in the Xen ring buffer implementation. I think this comes from Keir’s dissertation but I’m not sure whether Keir, Tim, or some combination of the two invented it. A lot of the stuff in that project came out of pub conversations between the two of them and with Ian Pratt, so attribution is nontrivial.

          1. 1

            Bingo, found an article explaining it. Thanks!

            And I’m digging the Fraser/Harris paper. The transactional object system is clever enough that I’m having to fight off an urge to implement it just for fun.

            1. 1

              Bingo, found an article explaining it. Thanks!

              Hmm, that looks very familiar…

              And I’m digging the Fraser/Harris paper. The transactional object system is clever enough that I’m having to fight off an urge to implement it just for fun.

              I have a similar reaction. A bunch of the stuff that they did is so elegant that I find it very difficult to not apply it in horribly inappropriate settings.

      2. 2

        Really cool, now do it without hardware-supported atomics! ;)