The Lockless MP/SC Ring FIFO Revisited
Today has been an interesting day... it started off with one of my servers having a lot of trouble with my new RingFIFO. Because it was still very early in the day (before the open), I just swapped out the RingFIFO with my LinkedFIFO and everything ran fine today. Still... when I had some time later today, I wanted to dig back into the issues with my RingFIFO and see if I couldn't fix it up and put it back into play for tomorrow.
Turns out, all I needed was a break and a little out of the box thinking. What I had originally used as the 'ring' was a simple template array of values:
/** * We have a very simple structure - an array of values of a fixed * size and a simple head and tail. */ volatile T mData[eCapacity]; volatile size_t mHead; volatile size_t mTail; volatile size_t mInsPt;
but the problem with this is that I had the concern about how to atomically move the tail and place a value in the spot while checking for queue crashing. It was just too hard. In my old code, the push() referenced the head and the tail, and the same for the pop(). This was clearly a recipe for disaster.
So I simplified. Significantly. The results are pretty nice.
First thing I realized is that the location is really orthogonal to the validity of the data in the queue. This means that I should really have something that 'tags' the data elements as 'valid' or 'invalid', and then use that to know when I can pop, or if I've overrun the queue.
If the head is pointing to the next good value, then all I need to do is check it's 'valid' flag. If it's valid, then I can pop it. Move the head up, snatck the old value and invalidate it, and we're done.
It's all easily done if we change our data elements to something like this:
/** * In order to simplify the ring buffer access, I'm going to actually * have the ring a series of 'nodes', and for each, there will be a * value and a valid 'flag'. If the flag isn't true, then the value * in the node isn't valid. We'll use this to decouple the push() * and pop() so that each only needs to know it's own location and * then interrogate the node for state. */ struct Node { T value; bool valid; Node() : value(), valid(false) { } Node( const T & aValue ) : value(aValue), valid(true) { } ~Node() { } }; /** * We have a very simple structure - an array of values of a fixed * size and a simple head and tail. */ volatile Node mData[eCapacity]; volatile size_t mHead; volatile size_t mTail;
Now I can have a far more cleanly separated push() and pop(). This is going to make a significant difference, I hope. I can say this for sure - it's considerably faster in my tests - like about twice. Very nice.