Free preview

Requirements checklist

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.

Sign up free to continue