Data layout and cache coherence

1.4 Data layout is a performance decision

Caches reward two behaviours. Spatial locality means touching an address and then its neighbours, so one line fetch serves several accesses. Temporal locality means touching something again soon, while it is still resident. The top five bid levels stored contiguously have spatial locality: one or two lines cover a scan. The top-of-book record has temporal locality: every message reads it. A resting order deep in the book has neither; it is touched on arrival and on cancel, minutes apart.

Temporal locality is fragile. After a 100 ms lull (a quiet spell with no messages), other activity has evicted part of your working set, so the first message after the lull runs slower than the thousandth in a burst. That first message is often the one that matters, which is why some firms push dummy messages through the hot path during quiet periods.

Array of structs versus struct of arrays

Store one side of the book as a ladder of 1,024 levels indexed by tick distance from a reference price. As an array of structs (AoS) it is [PriceLevel; 1024], 32 KB, two levels per line. As a struct of arrays (SoA) it is four arrays, price, qty, order_count and last_update, each 1,024 long.

Now the best bid is cancelled, and the handler scans down for the next level with qty > 0, 40 ticks lower. Under AoS the scan reads 40 × 32 = 1,280 bytes: 20 lines, three-quarters of each ignored. Under SoA it reads 40 × 8 = 320 bytes of qty: 5 lines, every byte used. Footprint matters too. The AoS ladder is 32 KB, two-thirds of a 48 KB L1; the qty array is 8 KB. The SoA scan is also a plain loop over [u64], which the compiler can vectorise (section 1.9).

SoA does not always win. Applying a quantity change writes qty, order_count and last_update of one level: one line under AoS, three lines in three arrays under SoA, and three misses if the level is cold. SoA wins when an operation reads one field across many elements; AoS wins when it touches many fields of one element. Real books do both, so real designs put the fields that scans read into dense arrays and keep the rest together.

Size, alignment and padding in Rust

std::mem::size_of::<T>() and std::mem::align_of::<T>() report a type’s size and alignment. A u64 must sit at an address divisible by 8, a u32 at one divisible by 4. A struct takes the largest alignment of its fields, and its size rounds up to a multiple of that alignment. The compiler inserts padding to satisfy these rules. With #[repr(C)], fields stay in declaration order, as in C. Without it, Rust’s layout is unspecified; a compiler may reorder fields, and sizes must be checked for the target build.

For example, compare two field orders on the x86-64 target used here:

#[repr(C)]
struct OrderC {
    active: bool, price: u64, flags: u8, qty: u32, venue: u16, id: u64,
}
#[repr(C)]
struct OrderPacked {
    price: u64, id: u64, qty: u32, venue: u16, active: bool, flags: u8,
}
assert_eq!(std::mem::size_of::<OrderC>(), 40);
assert_eq!(std::mem::size_of::<OrderPacked>(), 24);

In OrderC, 7 padding bytes follow active, three follow flags, and six follow venue: 16 wasted bytes out of 40. The second order removes them, reducing a million records from 40 MB to 24 MB. A default Rust layout may achieve the same size, but does not promise that order or size.

So why write #[repr(C)] at all? It provides C-compatible field layout for FFI and helps control field placement. A wire overlay additionally requires correct alignment, length, byte order and valid bit patterns; section 4.7 covers those checks. Rust’s reordering minimises size; it knows nothing about which fields are hot. If a struct exceeds 64 bytes and two fields must share a line, declare it #[repr(C)] and place them together yourself.

Two Rust types inflate layouts quietly. Option<u64> is 16 bytes, not 8, because the discriminant needs room; Option<NonZeroU64> is 8. An enum is as large as its largest variant plus a tag, so one 200-byte message variant makes every element of a Vec of messages over 200 bytes, heartbeats included. Box the rare large variant.

Hot/cold splitting

A real order record carries more than the matching path needs: client order ID, account, audit timestamps and venue tags. Say the hot fields (price, quantity, side, and a link to the next order at the level) fit in 24 bytes and the rest take 104. Together, each order is 128 bytes, two full lines, and a million orders take 128 MB, far beyond any L3.

Split them into parallel arrays indexed by the same slot: hot: Vec<OrderHot> and cold: Vec<OrderCold>. The hot path now touches fewer lines per order, though a 24-byte record can straddle a line, and the hot table for a million orders is 24 MB, small enough to have a real chance of staying in a 60 MB L3. A lookup that cost a 90 ns DRAM miss now often costs a 20–30 ns L3 hit. The cold fields are read off the hot path, where their misses do not matter.

Why Vec<T> beats pointers by more than big-O says

Summing ten million u64 values from a Vec<u64> and from a LinkedList<u64> are both O(n). They differ by two orders of magnitude.

The Vec is 80 MB of contiguous memory, eight values per line, streamed by the prefetchers at 15–20 GB/s: about 5 ms, roughly 0.5 ns per element. The list keeps each value in its own heap node, and finding node k+1 requires loading node k. Nothing overlaps and nothing is predictable. Once the nodes are scattered, each step is a DRAM miss plus usually a page-table miss: 100 ns or more, about a second in total, 200 times slower at the same big-O. Vec<Box<T>> sits in between. Its pointers are contiguous, so the core can issue several misses at once; expect 10–40× slower than Vec<T>.

The trap is that pointer structures often benchmark well. Boxes allocated in sequence in a fresh process tend to be adjacent, so the prefetcher works by accident; after hours of production churn the nodes are scattered. When you need links, such as the queue of orders at a price level, keep the nodes in one Vec and link them with u32 indices. An index is half the size of a pointer and the nodes stay contiguous.

1.5 False sharing and cache coherence

Private caches mean the same line can live in several cores at once. If two cores each held a different modified copy, they would disagree about memory. A coherence protocol prevents that. Intel and AMD use extended versions (MESIF on Intel and MOESI on AMD), but plain MESI explains everything you need here. Each line in each private cache is in one of four states.

The central rule is that writing requires sole ownership. Follow one line through two cores. Core A reads it and holds it Exclusive. Core B reads it, and both copies become Shared. A writes. It broadcasts an invalidation, B’s copy becomes Invalid, and A’s becomes Modified. B reads again. It misses, the request finds the Modified copy in A’s cache, A supplies the data, and both copies return to Shared. Each hand-off between cores on one socket costs roughly 50–100 ns. Across sockets it costs more.

False sharing

Put two counters in one struct: a incremented by a thread on core 0 and b by a thread on core 1. Neither thread ever reads the other’s counter. But both counters sit in one line, and coherence works on lines, not variables.

This is false sharing: two logically unrelated threads serialise on a line they both write. With the counters on separate lines, each increment is an atomic add on a line that stays Modified in local L1, about 5 ns. Adjacent, many increments wait for a line transfer, and the adjacent version runs 5–20× slower. The fix is to wrap each counter separately in #[repr(align(64))] struct Counter(AtomicU64);. Aligning only the containing pair would still leave its two fields together.

In practice, use crossbeam_utils::CachePadded<T>. It aligns to 128 bytes on x86-64, because the adjacent-line prefetcher fetches lines in 128-byte pairs and can couple neighbours. Do not pad everything: a million padded counters take 128 MB. Pad only data written by different threads.

One writer, many readers

A subtler case matters for the queues in later chapters. If one core writes a line and others only read it, the line still moves. Each write invalidates every reader’s copy; each reader’s next read pulls the line back and downgrades the writer to Shared; the next write must invalidate again. Readers are not free.

In a single-producer, single-consumer ring buffer, the producer advances head and the consumer advances tail. They go on separate padded lines, but that is not sufficient. To check for space, the producer reads tail on every push, and the consumer has usually just written it, so frequent polling can force repeated transfers. The fix is for each side to cache the other’s index locally and refresh only when that cached value says full or empty.

With a 1,024-slot ring, one observed tail can grant room for up to 1,024 pushes, depending on occupancy. A consumer refreshes head when its known items run out; if items arrive one at a time, that can still mean one refresh per item. Caching reduces traffic according to the available batch, not capacity alone. Memory orderings come in a later chapter. The rule here: one writer per cache line, and as few cross-core reads of it as the design allows.

Finding it with perf c2c

False sharing is invisible in source code. perf c2c record -- ./binary samples memory accesses, and perf c2c report ranks cache lines by HITM events: loads that found their line Modified in another core’s cache. For each hot line it lists the byte offsets and the code touching them. Different offsets from two threads is false sharing; the same offset is true sharing, which padding cannot fix.