A single-producer single-consumer ring buffer

Build a lock-free SPSC queue and push every item through it.

pub fn spsc_roundtrip(items: Vec<i64>, capacity: usize) -> Vec<i64>

One producer thread writes every item in order. One consumer thread reads them and returns them. The output must equal the input exactly — same values, same order — for any capacity >= 1, including a capacity far smaller than the number of items. capacity == 0 is treated as 1; empty input returns [].

No Mutex, no channel. Two atomic indices and an array of atomic slots.

The smallest real lock-free structure

A ring buffer with exactly one producer and one consumer is the simplest useful lock-free data structure there is, and it is everywhere: audio callbacks, kernel/userspace rings, network drivers, crossbeam‘s internals. The single-producer, single-consumer restriction is what makes it small enough to hold in your head — each index has exactly one writer.

That is the whole trick. head is written only by the producer; tail only by the consumer. Each side keeps its own index in a local variable and only reads the other’s atomic. There is no read-modify-write anywhere, no CAS, no contention, no retry loop.

The protocol

Use monotonically increasing counters and index the array with % capacity. It reads better than wrapping the counters themselves, and it makes full/empty unambiguous:

empty  when  head == tail
full   when  head - tail == capacity

(Wrapping the indices directly gives you the classic ambiguity where full and empty look identical, which is why textbook implementations sacrifice a slot. Monotonic counters sidestep it.)

Producer, per item:

while h - tail.load(Acquire) == cap { spin_loop(); }   // wait for space
buf[h % cap].store(item, Relaxed);                     // fill the slot
h += 1;
head.store(h, Release);                                // publish it

Consumer, per item:

while head.load(Acquire) == t { spin_loop(); }         // wait for an item
let v = buf[t % cap].load(Relaxed);                    // read the slot
t += 1;
tail.store(t, Release);                                // publish the free slot

The orderings, and why each one is what it is

This is the clearest release/acquire pair you will meet, so read it slowly.

head.store(h, **Release**) is the producer saying: everything I wrote before this store is now safe to read. head.load(**Acquire**) is the consumer saying: if I see that value, I also see everything written before it. Together they create the happens-before edge that makes the slot write visible.

Which is exactly why the slot itself can be Relaxed. The slot is not synchronising anything; it is the payload being published. The index does the synchronising.

tail mirrors it in the other direction: the consumer’s Release publishes “I am finished with that slot”, and the producer’s Acquire is what makes it safe to overwrite.

Weaken any of those four and the program still works perfectly on x86-64, because a Relaxed load and an Acquire load compile to the same instruction there. This grader cannot tell the difference, and neither can your laptop. Getting them right is a matter of reasoning, and it is the reason the previous article is an article.

The starter’s error

error[E0499]: cannot borrow `buf` as mutable more than once at a time

The producer must write the slots and the consumer must read them, and a plain Vec<i64> hands out one &mut at a time. That is the borrow checker correctly refusing a data race — the disjointness here is a temporal one enforced by your protocol, not a structural one it can see.

Since the indices are already atomics, make the slots atomics too: Vec<AtomicI64>. Now everything is shared by &, AtomicI64 is Sync, and no unsafe appears anywhere. (A production ring stores arbitrary T in an UnsafeCell<MaybeUninit<T>> and takes on the proof obligation; i64 lets you learn the protocol without it. The spinlock problem later in this track is where that obligation arrives.)

About the spinning

std::hint::spin_loop() inside a wait loop emits a CPU hint (pause on x86, yield on ARM) that reduces power draw and speeds up the eventual exit. It is not optional style — an empty spin loop is measurably worse.

clippy::missing_spin_loop and clippy::empty_loop catch this, but be precise about when: they fire reliably when the atomic is a local, and were observed not to fire when it is reached through an Arc or a reference parameter — which is the shape this problem uses. So the gate here will not catch it for you. Write the hint anyway.

Spinning is also only appropriate when the wait is expected to be very short. A ring buffer that is usually neither full nor empty qualifies. A ring buffer whose producer is asleep does not — real implementations fall back to parking after a bounded number of spins, which is precisely what you built by hand with park/unpark.