threads? SPSC — one producer, one consumer, parallel cores
full behavior? try_push returns false; no blocking, no silent loss
records? fixed-size POD, copied by value
capacity? fixed; ask for power of two (mask, not modulo)
API? non-blocking try_push / try_pop; waiting is the
caller's policy
use case? latency-first handoff (e.g. NIC -> processing)
The design in ten lines
slots[capacity] fixed array, capacity = 2^k
tail (producer-owned) free-running counter
head (consumer-owned) free-running counter
slot(p) = slots[p & (capacity-1)]
size = tail - head full: size == capacity
empty: size == 0
push: write record -> store-release tail+1
pop: acquire tail -> read record -> store-release head+1
each side: relaxed-load own counter, acquire-load the other's
Invariants
1. one writer per counter (tail: producer, head: consumer)
2. head <= tail <= head + capacity
3. [head, tail) holds complete records (release/acquire on tail)
4. slot reuse only after read completes (release/acquire on head)
5. stale reads err conservatively (looks fuller/emptier, never wrong)
Complexity and performance facts
try_push / try_pop O(1), allocation-free, syscall-free
dominant cost the 64B copy; atomics cheap uncontended
false sharing pad head and tail to separate 64B cache lines
batching n records, one publish — amortizes fences
The five report dimensions — what earns points here
Requirements & interface asked the threading question unprompted;
pinned full-behavior + non-blocking API
Core design & invariants one-writer-per-counter stated; full/empty
disambiguation defended; fences placed AND
justified in words
Extension probe (withheld — the mock tests you cold; answer
with: name the invariant, trace the break,
cost the fix)
Complexity honesty O(1) with the copy named as dominant cost;
false sharing raised with its mechanism
Communication narrated ownership and ordering as you
wrote each line
Enjoying the preview?
Create a free account to unlock the rest of this course, the in-browser judge, and live AI mock interviews.