The Ring Buffer — Explained in Detail

A ring buffer is a plain array plus two integers, and it is the only queue that can promise you a memory ceiling. The size is decided once, at startup, and never moves again — so when it fills, something has to give. Deciding what gives is the real subject of this video: overwrite the oldest entry, or refuse the write and push back on the producer. Same structure, opposite promise, one branch of code apart. Every number here was executed on a real machine before it was drawn, and one thing I expected turned out to be wrong: • "There is no third option for telling full from empty." False. There are at least four techniques, and one of them is the very formulation this video draws. The true statement is arithmetic: a buffer of eight has nine possible fill levels, and a pair of wrapped indices can only tell eight of them apart — so you either add one bit of information, or delete one of the states. • The unbounded queue: 3,000,000 samples, one writer, one reader, and RSS went 9.9 MB → 617.2 MB. Dead straight at 202.5 MB per million samples. The ring buffer doing identical work grew by 0.64 MB, and the array itself measured 8,248 bytes before and after — the same number, to the byte. • "Nothing is allocated after startup." True in C, misleading in Python: 500,000 dictionaries were still allocated in that loop. What a ring buffer removes is not allocation, it is the part of your memory use that has no ceiling. • Do not hand-roll it in CPython: deque.append is 37 ns, the hand-written push is 285 ns. Write it once to understand it, then use the one in the standard library. The beat I would keep if I could keep only one: a growing queue never tells you it is in trouble. It just takes a little more memory, and a little more, until there is none left. A ring buffer cannot do that. All it can do is lose data, and it tells you exactly how much — which turns an invisible, unbounded risk into a number you can put on a dashboard. 0:00 The ring buffer 0:11 A queue with no limit is a memory leak that behaves 0:55 What this covers, and what it is not 1:43 A pile of paper, or a wheel with eight pockets 2:34 The running example: one process, eight slots 3:14 Stack or queue: which end do you touch? 3:55 The mechanism: two cursors, one array 4:48 push and pop, in four lines 5:34 Wrap-around: the counters never wrap, the index does 6:22 Empty vs full, and the bug between them 7:08 Add a bit of information, or delete a state 7:53 What happens when it is full is a decision 8:18 Policy one: overwrite the oldest 9:01 Policy two: refuse the write 9:47 Both policies, one branch apart 10:28 Measured: 607 MB against 0.64 MB 11:03 Why you would lose data on purpose 11:41 The three honest costs 12:30 deque(maxlen) overwrites. Queue(maxsize) refuses. 13:14 Four ring buffers on this machine right now 13:57 Three interview questions 14:41 Recap: the whole chain 15:22 Wrap up Covered in detail: — what a stack and a queue actually are: which end do you touch — the mechanism, drawn: eight slots, a write cursor and a read cursor — buf[head % n] = x, and why the counters never wrap even though the index does — empty vs full, and the classic off-by-one that lives between the two tests — the two policies: overwrite the oldest, or refuse the write, and when each is right — what it costs you: picking n, the wrap arithmetic, and the second writer — deque(maxlen=n) overwrites, Queue(maxsize=n) refuses — the standard library has already chosen for you — four ring buffers running on this machine right now, three that overwrite and one that refuses Not covered, on purpose: message brokers and competing consumers, how a deque grows, and lock-free programming. Measured on an Intel Core i5-9400F, CPython 3.10.12, Linux. Unit 11.5 of the missing CS degree series. #ringbuffer #circularbuffer #datastructures #algorithms #computerscience #python #systemdesign #backpressure #softwareengineering