A queue in an array
A queue takes items in at the back and hands them out at the front, in the order they arrived. The obvious way to build one is an array: add at the end, remove from the start.
The trouble is the removing. Take the first item out of an array and every other item has to shift down one place to close the gap. With a thousand items, that is a thousand moves for one removal.
A ring buffer (also called a circular buffer) is a queue that never moves its data. Instead of shifting the items, it moves two markers.
Two markers chasing each other
Use a fixed array and treat it as a circle
After the last slot comes the first slot again.
tail marks where the next item is written
Write there, then move tail one step forward.
head marks the oldest item
Read from there, then move head one step forward.
When a marker passes the last slot, it wraps to slot 0
Slots that were read are free again, so the writing just continues around.
Start. Eight slots in a circle, all empty. head marks the oldest item (the next to be read). tail marks where the next write goes.
- Items
- 0 / 8
- head (read here)
- slot 0
- tail (write here)
- slot 0
Watch one written item. From the moment it is stored until it is read, it never changes slot. Only head and tail move, and each moves one step per operation.
The wrap-around is one line of arithmetic: the remainder after dividing by the size.
class RingBuffer:
def __init__(self, size):
self.slots = [None] * size
self.head = 0 # oldest item
self.tail = 0 # next free slot
self.count = 0
def write(self, item):
self.slots[self.tail] = item
self.tail = (self.tail + 1) % len(self.slots) # wrap around
if self.count == len(self.slots):
self.head = self.tail # full: the oldest was overwritten
else:
self.count += 1
def read(self):
item = self.slots[self.head]
self.head = (self.head + 1) % len(self.slots)
self.count -= 1
return itemWhat happens when it is full
When tail catches up with head, every slot is in use. There are two reasonable things to do, and which one is right depends on the data.
| When full | Behaviour | Good for |
|---|---|---|
| Overwrite the oldest | The newest data always fits. Old data is lost | Logs, audio, sensor readings, "the last 100 events" |
| Refuse the write | Nothing is lost. The writer must wait | Work queues where every item matters |
The animation overwrites. The second choice is the queue limit described in Queues and Backpressure.
Good at
- Add and remove in one step each, with nothing shifted or copied
- Memory is allocated once and never grows
- Items sit side by side, which processors read quickly
Where it bites
- The size is fixed in advance
- When it is full you must lose data or make the writer wait
Where you will meet it
- Audio and video: the sound card reads samples from one end while the program writes them at the other.
- Network cards and keyboards: incoming data waits in a ring until the program collects it.
- Logging "the last N things": overwrite mode keeps recent history in fixed memory.
Key takeaways
- A ring buffer is a queue in a fixed array that is treated as a circle.
- Writes happen at tail and reads at head. Both markers move forward and wrap around.
- The stored items never move, so both operations take one step.
- When tail meets head it is full: overwrite the oldest, or make the writer wait.