Data-structure decisions for a hot path

5.9 What follows for a hot path

Nothing below is a trick: each rule is what a mechanism leaves once its price is in front of you, and a reader who disagrees with one should be able to point at the number it rests on.

Allocate everything the loop will ever need at startup: fixed-capacity collections sized from the instrument count and the burst size, a pool (slots, a stack of the free ones’ indices and a flag per slot, so that a stale index panics instead of reading a dead value) for values with variable lifetimes, and an arena reset per batch for the rest, so that nothing on the hot path calls the allocator. A call costs 20–50 ns and as much again to free, 1–10 µs on the slow path, and a Vec that doubles copies for 2–3 µs at 32 KB and spends milliseconds at 32 MB, moving the bytes or faulting in their pages, each at a moment the allocator chose. Prove it with Chapter 2’s counting allocator in the test suite: the count before and after a million iterations must be the same.

Use ids, not strings. Intern every venue symbol to a small integer at startup (BTC-USDT-PERP is 42), index arrays by it on the hot path, and keep hash maps for startup, configuration and anything off the hot path. An array index is an address computed from the id, 1 ns; a HashMap<u32, Position> must hash, probe a group and compare, 20–50 ns with the default hasher, 5–15 ns with a cheap one, and 50–100 ns with the table cold in L3. A String symbol also allocates, 20–50 ns, each time it is decoded, and a map that grows pays 1–5 ms for a rehash at 100,000 entries on one unlucky insert.

Answer every “which ones?” question with a bitmap, and find the answer with the bit-scan instructions instead of a loop. One bit per instrument in a 64-bit word says which have a pending order; a test, set or clear costs 1 ns, and trailing_zeros finds the next set bit in 1–3 cycles however far away it is, with no loop exit to mispredict. A scan over [bool; 64] reads about 1 ns per 8 bytes, up to 8 ns, and ends in a mispredict of 15–20 cycles, 4–5 ns.

Put one single-producer single-consumer ring between each pair of threads that talk, with one writer per cache line: the two counters on lines of their own, each side holding a cached copy of the other’s counter, refreshed only when the ring looks full or empty, and the data crossing once, as a slot line moving from producer to consumer. A push or pop with the cached copy valid costs 5–20 ns and reads no line the other core writes. The same ring with both counters on one line and no cached copies costs 30–100 ns an item, std::sync::mpsc with a spinning consumer 100–300 ns, a Mutex<VecDeque> 150–400 ns, and a recv that sleeps and must be woken 5–20 µs.

Drain what is there, process it, publish once, and never wait to fill a batch. One Release store replaces one per item, and each hand-off is a line transfer of 50–100 ns, so 30 updates handed over singly pay 1.5–3 µs and handed over together pay one transfer. Taking what has arrived adds no wait for items still to come; waiting for a fuller batch holds the first for as long as the rest take to come, which on a quiet instrument has no bound. What a batch does cost is the first item’s result, published only after the 29 applied behind it, 60–150 ns at 2–5 ns each.

Declare repr(C) on every struct that is bytes on a wire, use struct-of-arrays for the hot fields of a large table, and put repr(align(64)) on anything two threads write, as Chapter 1 laid out. Only repr(C) stops Rust reordering the 48-byte update’s fields away from the offsets the venue wrote, and a wrong offset reads a wrong number with no error. A 40-level scan down a 1,024-level ladder reads 20 lines as an array of structs and 5 as a struct of arrays, and two counters written by two threads on one line run 5–20 times slower than padded, each write taking back a line at 50–100 ns.

Measure a bounds check before removing it, since in a plain indexed loop the compiler often hoists it to one check before the loop already; remove it with iterators and fixed-size slices before unsafe, and keep every unsafe block behind an invariant written in a comment. A check is a compare and a branch the predictor usually gets right, 0–1 cycle, so it matters when mispredicted, 15–20 cycles, or when it stops the loop around it vectorising; an iterator or a &[T; N] removes it with no promise from you. An unchecked access saves no more, and when its invariant is wrong the compiler has been told something false and may build anything on it.

Run cargo asm on the hot functions as part of code review, looking for the call, the div and the memcpy that should not be there. The source shows none of them: a call not inlined costs 1–5 ns and spills registers, a div where a mask was meant costs 20–40 cycles against one, and a struct passed by value is a memcpy of 2–3 µs at 32 KB, two or three budgets on a line that reads like an assignment.

Use MaybeUninit only where zeroing is measured to matter, and never read before written. Zeroing runs at 10–20 GB/s, 4 KB in 200–400 ns and 1 MB in 50–100 µs plus a page fault on first touch: a cost for a scratch buffer re-zeroed every batch, none for memory zeroed once at startup. Reading an uninitialised value is undefined behaviour even for an integer, so the compiler may assume it never happens, and a mistake costs not speed but code no test can vouch for; the capstone, the project that closes the book, accepts it in two places only, the ring’s slots and the pool’s.

Four things are deliberately not done. There is no multi-producer or multi-consumer queue, since each pair of threads has a ring of its own and a queue several threads write pays a contended read-modify-write of 50–300 ns on the one line they share. There is no custom global allocator, since the hot path no longer calls the allocator and a faster one would speed up a path that does not exist. There is no unsafe beyond the ring’s slots and the pool’s, since each unsafe block is a promise the compiler takes on trust and those two are the only ones whose safe versions cost something measured. There is no SIMD by hand, since the compiler vectorises the simple loops here unaided and cargo asm will say when it has not. The capstone does not need any of them, and each is a chapter of its own.