Circular Buffers

Ah, circular buffers. A classic of consumer/producer designs: a fixed-size buffer that is effectively infinite as long as consumers keep up.

For all its simplicity, there are some important decisions to be made when the time comes to implement one (or better to select an existing one if it fits!).

Abstract Data Type Description

Let's sketch out a description for the circular buffer as an ADT:

• enqueue(B, e), adding an element, first-in first-out (FIFO)
• dequeue(B), removing and returning an element or indicating none is available, FIFO
• isFull(B), indicating whether the buffer is full
• isEmpty(B), indicating whether the buffer is empty

Design Decisions

As a bonus, many of these decisions apply to other stream-like ADTs by the way, so this can serve as a handy guide to think through those (say, something like a network socket read/write). Streams also share the 'infinite sequence of elements' aspect of the abstraction.

Single-Element vs. Multi-Element Operations

A single-element circular buffer is useful if you have fixed-sized structures or if you're including pointers to data kept elsewhere (but then you have to figure out how to manage the lifetime of that data).

A more common approach is to have multi-element operations, which changes the ADT operations to these:

• enqueue(B, elements), adding multiple elements, first-in first-out (FIFO)
• dequeue(B, maxElements), removing and returning up to maxElements elements and indicating how many where removed, FIFO

This introduces some additional considerations for what happens when elements is larger than all available data or buffer space, in which case the considerations for "Overwriting Behavior" below kick in. A common approach here for example is to preserve FIFO when overwriting, and to "wipe out" the buffer with the last buffer capacity number of elements in the input elements.

Often the circular buffer itself is rather "dumb" and manages mult-bytes reads and writes, and the framing for those bytes is given by a higher-level construct.

Overwriting Behavior

When someone writes more elements than the circular buffer has capacity for, there are a handful of strategies about what to do.

• Overwrite. This is the most common solution to my knowledge. The buffer simply overwrites older content, which also means advancing the read position.
• Block. This really only works if your circular buffer is built for concurrency and makes things significantly more complex, as you have to walk through all the usual asynchrony concerns: signaling, callbacks (and all its concerns like scheduling), timeouts, etc.
• Fail. Simply let the writer know that there's not enough room yet.

Partial commits for multi-element writes are very unusual in practice - I don't think I've ever seen an implementation that does that. That would be a case where you want to write 5 bytes but only have space for 3, so you write the first 3 and return an error.

Overreading Behavior

You can run into a similar problem when someone asks to read more than is available.

• Partial read. This is the most common solution by far, but I'm including the others for completeness.
• Block. Don't fullfill the read request until some or all of the requested bytes have been satisfied.
• Fail. Just let the caller know there aren't enough bytes to read and don't read anything.

The reader is always aware of how much valid data is available, so there usually isn't a "dirty read" scenario.

Concurrency

Another pivot for options in terms of concurrency is how many producers and consumers there are running at the same time.

• Single producer, single consumer. For example, reading data from a network connection.
• Multiple producer, single consumer. For example, gathering data from multiple sensors, then flushing them out to disk.
• Single producer, multiple consumers. For example, incoming work requests that get picked up by multiple processors.
• Multiple producers, multiple consumers. For example, parallelized copies.

Locking or Lock-Free

If the circular buffer supports concurrency of some sort, the next aspect to consider is whether access is lock-based or lock-free.

There are a few ways in which I've seen concurrency managed in practice.

• "Timing / process rate." Often, the system is set up in such a way that producers never really overwrite based on timing and production/consumption data rates and scheduling. Often any effort expended, if any, goes into detecting overwrites for example with torn values.
• "Bag o' tricks". Worth a separate post on how to think through lock-free algorithms, but typically there are additional constraints put to make this work lock-free, for example with a single producer/single consumer model. Multiple writers for example would need additional coordination to avoid the race between 'reserving' a slot and writing to it (with a single writer, you can write the data first and then update the size for the reader to find out, without worrying about a race).

Example: Windows Audio

Windows has more than one audio port driver model; older ones relied on copying data around, then working with scatter/gather, and the latest one is the WaveRT Port Driver, based on a "cyclic buffer". (The term cyclic buffer refers to the fact that when the buffer position register reaches the end of the buffer in a playback or record operation, the position register can automatically wrap around to the beginning of the buffer.)

Here are how some of the choices work out in this example:

• Multiple samples are written to the audio buffers.
• There is no support for blocking and samples are not just "not delivered", so overwriting can yield to glitching. There is no 'overreading' in the implementation, which has knowledge of valid data ranges.
• Concurrency is set up for a writer and reader that function independently, and there is a bunch of optional support for driving activity based on timers or notifications and sharing position values.
• The whole thing is lock free, relying on a combination of hardware support and timing/scheduling to manage production and consumption without interference.

Other Considerations

There are other related data structure like a bipartite buffer (bip buffer), which is basically a buffer with two regions, where element buffers are laid out contiguously (a "multi-element write" or read can be guaranteed to be contiguous, which is nice).

Happy buffering!

Tags:  coding design

Home