Back To Basics: The Ring Buffer

If you’ve been writing software for very long, you’ve likely encountered the humble ring buffer. Ring buffers are everywhere . They appear in code for audio engines, network stacks, kernel drivers, graphics engines, etc. They’re one of the most important data structures for getting data from point A to point B in a timely and thread-safe way. Today, we’re going to show the ring buffer some love. We’ll talk about how the ring buffer works, why you might use it, and we’ll even implement one in C++.

What Is a Ring Buffer?

You may have heard of something called a circular buffer, or maybe even a cyclic queue. Both of those are just other names for the ring buffer. You can think of a ring buffer as a specialized type of queue. Just as with any old, vanilla queue, a producer produces some data, shoves it into the data structure, and a consumer comes along and consumes it. This all happens in first-in-first-out (FIFO) order. But what sets the ring buffer apart is the way it manages its data and the limitations it imposes.

A ring buffer has a fixed capacity. It can’t grow and it can’t shrink. If you create a ring buffer that can store 10 items, 10 items will forever be its max capacity. Because the capacity is fixed, a producer has two options once it fills the ring buffer – the choice of which is largely driven by how the ring buffer is designed and the application’s needs. The producer can either wait until a slot is free in the ring buffer so that it can add more data. Or it can just stomp over data that hasn’t been consumed yet. Both approaches are valid in certain contexts.

The consumer’s role is to consume data.  If there’s no data available in the ring buffer, the consumer has to wait or go do something else. The side-effect of a consumer reading data is that it frees up slots within the ring buffer for the producer to use.

Ideally, the producer’s producing is always just slightly ahead of the consumer’s consuming, resulting in a nice game of “catch me if you can” with virtually no waiting by either party.

The canonical diagram of a ring buffer looks like so.

In this diagram, we have a buffer with 32 slots. The producer has filled 15 of them, indicated by blue. The consumer is behind the producer, reading data from the slots, freeing them as it does so. A free slot is indicated by orange.

Keep in mind that these sorts of diagrams are meant to demonstrate a concept and not so much depict an implementation. It’s certainly possible to implement a ring buffer that’s physically circular, as in the image above, using something like a linked list of separate smaller buffers. Quite often, however, you’ll see a ring buffer implemented using one big memory allocation. In this case, separate state is used to track used capacity as well as read and write indices.

Why Use a Ring Buffer?

You’ll most commonly see ring buffers used in circumstances that involve high volumes of data that need to be produced and consumed at high speeds. Real-time audio/video, network drivers, etc. are all contexts where you’ll find ring buffers being used. In these situations, performance of the data structure is key.

Performance takes a beating if you’re having to allocate and deallocate memory all the time. Memory allocation is slow. So ring buffers avoid it by allocating a chunk of memory one time and reusing it over and over. Memory fragmentation is also avoided.

Anything that involves locking (e.g.,  mutexes, and even memory allocation) is problematic when it comes to performance.  You simply can’t predict how long a lock will be held. As we’ll see in our example implementation, ring buffers can be both thread-safe and lock-free.

Speed Is My Jam. When Would I Not Want to Use a Ring Buffer?

Ring buffers are ideally suited for the single producer/single consumer scenario. If there are more than one of either, things get complicated and locking will certainly need to be introduced either directly within the ring buffer or as a wrapper.

If you need your data structure to grow to an arbitrary size, then ring buffers are off the table.

If you need to explicitly control the lifetime of data within the ring buffer (e.g., if you need to hold pointers/references to contained data), then ring buffers are obviously the wrong choice.

If your data needs to be sorted or have a priority associated with it, ring buffers are the wrong choice here as well. Ring buffers are ALWAYS first-in, first-out.

The Gotcha

Because the ring buffer size is fixed, you sometimes have to experiment to find the optimum size to keep the producer ahead of the consumer at a rate that neither ever has to wait to do their job. Take the world of professional audio software as an example. Here, you’ll sometimes find the ring buffer capacity explicitly configurable within the UI as a mechanism for the user to tradeoff between audio latency and glitchy audio for a given hardware configuration.

Screenshot taken from Cakewalk BandLab

When is it ok for a producer to stomp over unconsumed data?

I mentioned earlier that in some scenarios it’s ok for a producer to stomp over unread data. When would this ever be ok? Consider a real-time audio or video streaming application such as a radio streamer or video conferencing app, or perhaps the broadcasting of player states in an online game. For sundry reasons, network hiccups occur. We’ve all experienced them. But regardless of the why, it’s always important to charge forward and have our applications processing the latest and greatest data.

Implementing an Audio Ring Buffer

The time has come. We’re going to implement a simple ring buffer in C++. We’ll make it data type agnostic and lock-free. Let’s start things off with a class skeleton, a constructor that allocates the buffer, and some state for tracking how much of the buffer is free.

template<typename DataType>
class RingBuffer
{
public:
    RingBuffer(int capacity) :
        m_capacity(capacity),
        m_freeItems(capacity),
    {
        static_assert(ATOMIC_INT_LOCK_FREE == 2);
        m_spBuffer = std::make_unique<DataType[]>(m_capacity);
        memset(m_spBuffer.get(), 0, sizeof(DataType) * m_capacity);
    }
    ...
private:
    ...
    std::unique_ptr<DataType[]> m_spBuffer;
    const int m_capacity;
    std::atomic<int> m_freeItems;
};

This is a data type agnostic implementation. RingBuffer is a class template that allows clients to parameterize it with whatever data type they wish (so long as it’s memcpy and memcmp compatible).

The constructor allows the client to specify the size of the ring buffer. This is stored in m_capacity.

We also have a std::atomic<int> that’s used to track how many free slots are available for writing. Having this atomic is key to making this class thread-safe, as both producers and consumers will be indirectly checking this value during the reading and writing of ring buffer data.

You’ll also note that the constructor has a static_assert for ensuring that std::atomic<int> is lock free. This is to avoid any locking that could impact performance.

And just for fun, we initialize the contents of m_spBuffer to zero to put us in a known initial state. This isn’t really all that important. But it might benefit unit tests (which I did write for this, incidentally).

Next up, let’s add the state and functions needed for writing data into the buffer.

    int m_writeIndex; // Initialized to zero in constructor. Not shown above.
 
    int getWriteableItemCount() const
    {
        return m_freeItems.load();
    }
 
    int write(DataType * pData, int numItems)
    {
        int writeableItemCount = getWriteableItemCount();
        if (writeableItemCount == 0)
            return 0;
 
        int totalItemsToWrite = std::min(writeableItemCount, numItems);
 
        // Note that writeableItemCount will do nothing to help us 
        // determine if we're on the edge of the buffer and need to wrap around.
        // That's up to us to determine here.
        int itemsLeftToWrite = totalItemsToWrite;
 
        // Note that we're treating m_capacity like an index here for 
        // one-past-the-end.
        if ((m_writeIndex + itemsLeftToWrite) &gt;= m_capacity)
        {
            // We'd exceed the extent of the buffer here if wrote totalItemsToWrite samples, 
            // so let's do a partial write.
            int itemsAvailableUntilEnd = m_capacity - m_writeIndex;
            memcpy(m_spBuffer.get() + m_writeIndex, pData, itemsAvailableUntilEnd);
 
            // Bookkeeping
            m_writeIndex = 0;
            itemsLeftToWrite -= itemsAvailableUntilEnd;
            pData += itemsAvailableUntilEnd;
        }
 
        if (itemsLeftToWrite &gt; 0)
        {
            memcpy(m_spBuffer.get() + m_writeIndex, pData, itemsLeftToWrite * sizeof(DataType));
 
            // Bookkeeping
            m_writeIndex += itemsLeftToWrite;
            itemsLeftToWrite = 0;
        }
 
        m_freeItems -= totalItemsToWrite;
        return totalItemsToWrite;
    }

There’s one new piece of state here and two new functions.

The new state, m_writeIndex, is used to track where the producer is writing next. This value is only ever used by the producer, so we don’t need to make it atomic.

The function getWriteableCount() merely returns the number of free slots available for writing in the ring buffer. It’s for the benefit of both the producer and the write() function itself.

The write() function attempts to write the specified number of items into the ring buffer and returns the actual number of items written. There are some things worth noting here.

We first check to see if we CAN actually write anything. If we can’t, we return immediately.

Next, we decide how MUCH we can actually write and store it in a local variable called totalItemsToWrite. This value may be less than what the producer requested if they requested more than we have space for. After that, we check to see if we might be trying to write more towards the end of the buffer than we have space for. If so, we write what we can and then loop back around to the beginning to write what’s left. Anything that’s left goes wherever the current write position is located.

Before leaving the function, we update the relevant member variables.

Now let’s look at the state and functions for reading data from the buffer.

    int m_readIndex; // Initialized to zero in constructor. Not shown above.
 
    int getReadableItemCount() const
    {
        return m_capacity - m_freeItems.load();
    }
 
    int read(DataType * pData, int numItems)
    {
        int readableItemCount = getReadableItemCount();
        if (readableItemCount == 0)
            return 0;
 
        int totalItemsToRead = std::min(readableItemCount, numItems);
 
        // Note that readableItemCount will do nothing to help us 
        // determine if we're on the edge of the buffer and need to wrap around.
        // That's up to us to determine here.
        int itemsLeftToRead = totalItemsToRead;
 
        if ((m_readIndex + itemsLeftToRead) &gt;= m_capacity)
        {
            // We'd exceed the extent of the buffer here if read totalItemsToRead items, 
            // so let's do a partial read.
            int itemsAvailableUntilEnd = m_capacity - m_readIndex;
            memcpy(pData, m_spBuffer.get() + m_readIndex, itemsAvailableUntilEnd);
 
            // Bookkeeping
            m_readIndex = 0;
            itemsLeftToRead -= itemsAvailableUntilEnd;
            pData += itemsAvailableUntilEnd;
        }
 
        if (itemsLeftToRead &gt; 0)
        {
            memcpy(pData, m_spBuffer.get() + m_readIndex, itemsLeftToRead * sizeof(DataType));
 
            // Bookkeeping
            m_readIndex += itemsLeftToRead;
            itemsLeftToRead = 0;
        }
 
        m_freeItems += totalItemsToRead;
        return totalItemsToRead;
    }

Much like the writing side of things, we have a new piece of state for tracking the consumer’s read position. We also have a complementary getReadItemCount() function for returning the number of items available for reading. And then there’s the read() function.

If you compare the write() and the read() function implementations here, you’ll see they’re almost exactly the same. There are only two big differences – the direction the data goes in and out of m_spBuffer and the way the member variables are updated (m_freeItems being incremented vs. decremented, and m_readIndex being used vs. m_writeIndex). Apart from that, they’re pretty much the same.

The checks against m_freeItems ensure that the consumer will never overtake the producer. And, in this implementation, the producer can never overwrite data. So accessing m_spBuffer from two different threads is safe because the producer and consumer are never accessing the same slots at the same time.

The only other shared state between the producer and the consumer is m_freeItems and that’s atomic.

The complete RingBuffer implementation is as follows.

/**
 * A simple ring buffer class. This is thread-safe so long as only a
 * single producer and a single consumer are clients.
 */
template<typename DataType>
class RingBuffer
{
public:
    /**
     * Constructor.
     *
     * @param capacity The total number of items to accommodate in the RingBuffer.
     */
    RingBuffer(int capacity) :
        m_capacity(capacity),
        m_freeItems(capacity),
        m_readIndex(0),
        m_writeIndex(0)
    {
        // Lock-free would be important for scenarios that can't use locking, such
        // as real-time audio. If you don't have real-time concerns, then this can 
        // possibly be removed.
        static_assert(ATOMIC_INT_LOCK_FREE == 2);
        m_spBuffer = std::make_unique<DataType[]>(m_capacity);
        memset(m_spBuffer.get(), 0, sizeof(DataType) * m_capacity);
    }
    /**
     * @return The number of items that can be read by the consumer.
     */
    int getReadableItemCount() const
    {
        return m_capacity - m_freeItems.load();
    }
    /**
     * @return The number of items that can be written by the producer.
     */
    int getWriteableItemCount() const
    {
        return m_freeItems.load();
    }
    /**
     * Attempts to read the specified number of items.
     *
     * @return The number of items read.
     */
    int read(DataType * pData, int numItems)
    {
        int readableItemCount = getReadableItemCount();
        if (readableItemCount == 0)
            return 0;
 
        int totalItemsToRead = std::min(readableItemCount, numItems);
        // Note that readableItemCount will do nothing to help us 
        // determine if we're on the edge of the buffer and need to wrap around.
        // That's up to us to determine here.
        int itemsLeftToRead = totalItemsToRead;
        // Note that we're treating m_capacity like an index here for 
        // one-past-the-end.
        if ((m_readIndex + itemsLeftToRead) >= m_capacity)
        {
            // We'd exceed the extent of the buffer here if we read totalItemsToRead 
            // items, so let's do a partial read instead.
            int itemsAvailableUntilEnd = m_capacity - m_readIndex;
            memcpy(pData, m_spBuffer.get() + m_readIndex, itemsAvailableUntilEnd);
            // Bookkeeping
            m_readIndex = 0;
            itemsLeftToRead -= itemsAvailableUntilEnd;
            pData += itemsAvailableUntilEnd;
        }
        if (itemsLeftToRead > 0)
        {
            memcpy(pData, m_spBuffer.get() + m_readIndex, itemsLeftToRead * sizeof(DataType));
            // Bookkeeping
            m_readIndex += itemsLeftToRead;
            itemsLeftToRead = 0;
        }
        m_freeItems += totalItemsToRead;
        return totalItemsToRead;
    }
    /**
     * Attempts to write the specified number of items. This is only
     * guaranteed to write what we have space for. The amount of available
     * space can be determined by invoking getWriteableItemCount(). 
     * 
     * @return The number of items actually written.
     */
    int write(DataType * pData, int numItems)
    {
        int writeableItemCount = getWriteableItemCount();
        if (writeableItemCount == 0)
            return 0;
        int totalItemsToWrite = std::min(writeableItemCount, numItems);
        // Note that writeableItemCount will do nothing to help us 
        // determine if we're on the edge of the buffer and need to wrap around.
        // That's up to us to determine here.
        int itemsLeftToWrite = totalItemsToWrite;
        // Note that we're treating m_capacity like an index here for 
        // one-past-the-end.
        if ((m_writeIndex + itemsLeftToWrite) >= m_capacity)
        {
            // We'd exceed the extent of the buffer here if we wrote totalItemsToWrite
            // samples, so let's do a partial write instead.
            int itemsAvailableUntilEnd = m_capacity - m_writeIndex;
            memcpy(m_spBuffer.get() + m_writeIndex, pData, itemsAvailableUntilEnd);
            // Bookkeeping
            m_writeIndex = 0;
            itemsLeftToWrite -= itemsAvailableUntilEnd;
            pData += itemsAvailableUntilEnd;
        }
        if (itemsLeftToWrite > 0)
        {
            memcpy(m_spBuffer.get() + m_writeIndex, pData, itemsLeftToWrite * sizeof(DataType));
            // Bookkeeping
            m_writeIndex += itemsLeftToWrite;
            itemsLeftToWrite = 0;
        }
        m_freeItems -= totalItemsToWrite;
        return totalItemsToWrite;
    }
private:
    std::unique_ptr<DataType[]> m_spBuffer; //! The data.
    int m_writeIndex; //!< Where the producer is writing to next.
    int m_readIndex; //!< Where the consumer is reading from next.
 
    const int m_capacity; //!< Total number of frames managed by the ring buffer.
    std::atomic<int> m_freeItems; //!< Number of frames that are available to be written into.
};

Hopefully this article has helped you to appreciate the humble ring buffer a little bit more. If ring buffers were new to you before this article, I hope this was a helpful introduction and that you’ll be able to recognize them in the wild when you see them (they’re not always given helpful names like RingBuffer. 🙂 ). The implementation shown here is one of the simplest ones, and just one of many possible ways to do it.

If you find a bug in my code or have any questions or comments, please let me know. If you’ve seen any bizarre ring buffer implementations, tell me about that too. Weird code is always fun to see.

Until next time.

R2 Build Update

I’ve been absolutely terrible about keeping my R2 build log up to date. So I thought I’d take a minute to share where my R2 build is at today. Here’s a very short video that’ll give you a peek into the state of things.

As you can see in the video above, my R2 has lights, sounds, and scoots around like a happy toddler. Besides paint, I still need to work out a mechanism for the utility arms. I also need to get the motor installed for the dome. I’m contemplating redoing much of the electronics as well. My original approach was implemented a few years ago. I’ve since realized that I over-engineered things in some ways and under-engineered things in others.

I know I say this every year, but I believe this might just be the year I finish him. 🙂

The Bath Tub in the Woods

I grew up in a rural area outside a small coal-mining town in eastern Kentucky. My childhood home was nestled in a little valley formed where three mountains met. The house itself sat on maybe 2 acres, with a small creek running along the back edge. Across the creek and up a dirt road, my parents owned a fair amount of mountain property we referred to as “the holler.”

It was in the holler that I spent much of my childhood – exploring the hills, building hideouts, monster hunting, and playing in old abandoned mines from generations past. (That last bit my mother was blissfully ignorant of. So let’s keep it between you and me, ok?)

One summer, in the midst of an adventure undoubtedly of epic proportions, I stumbled across an old green fiberglass bath tub. I had no idea how it got there or who put it there. But there it was, surrounded by tall weeds and filled with all the gross stuff that things abandoned in nature tend to accumulate. I stared at it for a bit. And then found a big stick to bang around on it in hopes of scaring away any poisonous snakes that might be lurking around. I flipped it over one way and then another. And then somehow I managed to stand it up on its short end so that it stuck straight up in the air.

It was a little dirty, yeah. But it would do. This would be my fuselage.

You see, the movie “Explorers,” starring River Phoenix, Ethan Hawke, and the third guy who never gets the recognition he deserves, had just come out the year before. And I was obsessed with it. The notion that three kids could build a spaceship out of junk and a computer wasn’t just a fantasy for me. It was a blueprint. A blueprint I was convinced I could follow. I just needed to find the right stuff. And, um, learn about computers.

We were, in fact, too poor to have a computer. I don’t think I had even touched one up to that point. But that didn’t stop me. I spent all summer collecting random bits of junk for my ship. Old hoses, sparkplugs, pipes, wires, etc. Everything had a purpose. I just didn’t know what it was, but I was sure the thing would tell me in time.

I had also gotten my hands on quite the collection of “3-2-1 Contact” magazines. Each issue had snippets of BASIC code in it for kids to try out. I didn’t understand a lick of it. But I was sure some magic could be found in there. Like a witch brewing her stew, I could take a little of this and little of that and everything would find its own way to become what I needed it to be.

I worked on and played in this ship for weeks.

Eventually, school started again. Summer gave way to fall. And though that particular adventure’s time had passed, the places my mind took me, the things my eyes saw, and the extraordinary reactions of all the imaginary people passing below me as I flew over them were all important. Not only did they provide an escape for me from a home in conflict, but they fueled even more wonderful adventures later on, teaching me about myself and helping me to learn that ambition and curiosity is a powerful combination.

The tub is gone now, carted away. The ground beneath it has been bulldozed over and now a house sits there that was built by a young couple who eventually purchased the land. I imagine there are still bits and bobs left over from that project, buried deep in the dirt that’s been imprinted with my stories. Artifacts from a little boy’s exploration into the unknown.

I like to think that in a parallel universe, little-boy-me actually succeeded in getting that ship off the ground.