Ring costs and burst experiments

What it costs

A try_push or try_pop whose cached copy is valid costs 5–20 ns, 20–80 cycles at 4 GHz, 0.5–2% of a budget: a load of the side’s own counter, a compare with its copy, a masked index, the slot access and a Release store, a plain mov on x86-64, touching no line the other core writes. A refresh adds 50–100 ns, one transfer of the other side’s counter line, when the ring is near full for the producer or near empty for the consumer. The data costs one slot-line transfer per 64 bytes, two Updates to a line, 50–100 ns on the consumer’s first read of each, whatever the ring does. The 16-slot lab ring, which read the other side’s counter on every item, with no cached copies, moved an item in 30–100 ns; the cached ring’s cost per item is mostly its share of a slot line, half a transfer per Update. The indirect cost is the footprint: a Ring<Update, 4096> is 128 KB of slots, too large for L1 and resident in L2, every line written by the producer and first read by the consumer once a lap, in an L2 shared with everything else both threads use. N should be the largest burst the consumer must absorb while busy, not as large as memory allows.

Worked example: 30 updates in a burst from core 2 to core 3

At 14:30:00.000 a large trade in BTC-USDT-PERP moves several of its prices at once, and the venue’s burst reaches the feed thread on core 2 as one recv of 30 messages. The feed decodes them into 30 Updates of 32 bytes, 960 bytes in 15 slot lines, and calls push_batch once. Its cached_tail shows room, because the strategy keeps up, so the call reads no line the consumer writes: 30 slot writes at about the 1–2 ns of a Vec::push, 30–60 ns, and one Release store of head. The strategy on core 3 is spinning on drain. Its Acquire load of head pulls the counter line across, 50–100 ns, and finds 30 new items. It reads the 15 slot lines, each a transfer of 50–100 ns on first touch, 0.75–1.5 µs, and makes one Release store of tail, which the producer will not read until its copy next says full. Taken one after another, the 16 transfers come to 0.8–1.6 µs for the batch, 25–55 ns an update, 0.8–1.6 budgets in all. A core can have several misses in flight, and the prefetcher may run ahead along the slot lines, so a real batch often costs less, though never less than one transfer.

Pushed item by item, with a publish after each, the 30 updates store head 30 times, and a consumer spinning on try_pop pulls the counter line across after each: 30 counter transfers instead of one, 45 transfers in all, 2.3–4.5 µs for the batch and 75–150 ns an update, more if the consumer, reading right behind, pulls a slot line across once for each of its two updates. Through std::sync::mpsc, with the strategy spinning on try_recv, each update costs 100–300 ns, 3–9 µs for the burst, with an allocation whenever a block of 31 fills; had the strategy been asleep in recv, the first update would wait 5–20 µs for the wake before any of that began. Through a Mutex<VecDeque>, at 150–400 ns for each push and pop uncontended, the burst costs 4.5–12 µs, and more when the two threads collide on the lock. The batched ring spends 0.8–1.6 budgets on the 30 updates, nearly all of it the 960 bytes themselves crossing between cores; the alternatives spend two to twelve budgets, most of it on lines that carry no data.

Seeing it

perf c2c record -- ./ring samples loads and stores with their addresses, and perf c2c report ranks the cache lines that moved between cores by HITMs, loads that found the line Modified in another core’s cache, with the byte offsets and the functions that touched each. For the padded ring with cached copies, the HITMs fall on the slot lines, from the consumer’s try_pop or drain, about one per 64 bytes of data, and on the counter lines only at refreshes: the head line once per drain, the tail line a few times a lap. The lab’s pad binary, the same ring with head and tail in one line, puts that line at the top of the report with HITMs from both cores at two offsets eight bytes apart, about one per item: false sharing, in the tool’s own terms. Pinned to two cores that share an L3, expect the padded ring at 5–20 ns an item and the shared line near the 30–100 ns of a ring that moves a counter line every item. The ordering is checked as before, with loom’s atomics and cells swapped in under cfg(loom): a model with N = 2 and K = 3 passes through try_push and try_pop and again through push_batch and drain, and weakening any one of the four orderings to Relaxed, the producer’s load of tail or store of head, the consumer’s load of head or store of tail, stops loom at once with “Causality violation: Concurrent read and write accesses”. The copies and batches changed when the counters are read, not how.

Read more: Dmitry Vyukov’s 1024cores pages: “Producer-Consumer Queues” (https://sites.google.com/site/1024cores/home/lock-free-algorithms/queues), a taxonomy of queues by number of producers and consumers, bounded or not, and what each choice costs; “Unbounded SPSC Queue” (https://sites.google.com/site/1024cores/home/lock-free-algorithms/queues/unbounded-spsc-queue), which keeps the producer’s and consumer’s fields on separate lines; and “False-sharing” (https://sites.google.com/site/1024cores/home/lock-free-algorithms/false-sharing---false), which argues that padding is a refinement after sharing itself has been reduced. The rtrb crate’s README and source (https://github.com/mgeier/rtrb), src/lib.rs for the ring and src/chunks.rs for the batch API, and crossbeam-queue’s src/array_queue.rs (https://github.com/crossbeam-rs/crossbeam), Vyukov’s bounded queue for many threads. Mara Bos, Rust Atomics and Locks (O’Reilly, 2023), chapter 5, “Building Our Own Channels”, which builds a channel from a Mutex<VecDeque> and a Condvar, then one-shot channels from an UnsafeCell<MaybeUninit<T>> and an atomic flag, made safe first with runtime checks and then with types; it builds no ring, but its one-shot channel rests on the same Release/Acquire reasoning about a slot and a flag.