Uninitialised memory and honest benchmarks

Uninitialised memory

Uninitialised memory is memory the program has not written since the allocator handed it over. A fresh page from the kernel reads as zeros, because the kernel zeroed it on the first touch; a block malloc recycled holds whatever its last owner left; the language treats both as holding no value at all. Programs want such memory because writing a value first costs. Zeroing runs at 10–20 GB/s, so the 128 KB of a 4,096-slot ring of 32-byte Updates takes 6–13 µs, and the first touch of each 4 KB page adds a minor page fault, 0.5–1 µs. Once, at startup, that is affordable; a 64 KB receive buffer declared as [0u8; 65536] inside the loop is zeroed on every pass, 3–6 µs, three to six budgets, to write zeros the next recv overwrites. And an empty slot has no meaningful value to give; a dummy Update would only hide a read of a slot nobody pushed.

Reading memory before writing it is undefined behaviour, even for a u64, whose every bit pattern is a valid number. Undefined behaviour is the language’s name for a short list of things a program must never do: race on plain memory between threads, read uninitialised memory, follow a dangling pointer, produce a value its type forbids, such as a bool holding 2. The language does not say what happens if a program does one; it says the compiler may assume none ever happens, and optimises on that assumption. So the result is not “a random value”. An uninitialised u64 has no particular value and may differ at each use, so a test x < 10 and a later x >= 10 can both pass, and a check that depends on it can be deleted by reasoning that is correct for every program that does not do this. The program does whatever instructions built on a false premise happen to do, and may do something else after the next compiler upgrade.

MaybeUninit<T> is the type that says “maybe not yet written”. It has T’s size and alignment, and the compiler assumes nothing about its contents, so an unwritten one is allowed; only treating it as a T before a write is undefined. MaybeUninit::uninit() makes one and emits no instruction, and .write(v) stores a value, safely. .assume_init() takes the T out, consuming the wrapper; .assume_init_read() copies it out of a slot that stays put, as a ring’s pop does; .assume_init_ref() lends a reference, as a pool’s get does. All three are unsafe and sound only after a write. It never runs T’s destructor, which for plain data such as Update does not matter.

use std::mem::MaybeUninit;
use ch05_structures::{Side, Update}; // the 32-byte update

fn main() {
    // A ring's or a pool's 4,096 slots, 128 KB: allocated, never zeroed.
    let mut slots: Vec<MaybeUninit<Update>> = Vec::with_capacity(4096);
    slots.resize_with(4096, MaybeUninit::uninit); // writes nothing
    // The producer's push: writing is always allowed.
    slots[7].write(Update { seq: 1_873_465_902, price: 6_812_345, qty: 512, instrument: 42, side: Side::Bid });
    // The consumer's pop: reading is allowed only after a write.
    let u: Update = unsafe { slots[7].assume_init_read() };
    // let bad = unsafe { slots[8].assume_init_read() }; // slot 8 never written: UB
    println!("{} {} {}", u.seq, u.price, u.qty);
}

On rustc 1.97 the resize_with line compiles to the allocation and nothing else, where a vec! of 4,096 zeroed Updates compiles to a loop of stores over all 128 KB. The commented line compiles too, which is the danger. Miri, the interpreter that checks every memory access while a test runs (cargo +nightly miri test), catches it.

Keeping the benchmark honest

Two habits that serve a production build mislead a benchmark: the optimiser deletes work whose result nobody uses, and computes once what it can see does not change. A loop calling exposure(&positions), a function summing the 64 positions’ exposure, a million times on the same input and discarding the answer can compile to nothing; on rustc 1.97 this one did, a million calls measured at under 150 ns on the 2.1 GHz Xeon virtual machine used for this section’s checks. std::hint::black_box, stable since Rust 1.66, returns its argument unchanged, but the compiler must assume it reads the value and may have changed it, so wrapping the result forces the work to happen and wrapping the input stops the answer being computed once, outside the loop:

use std::hint::black_box;

for _ in 0..1_000_000 { exposure(&positions); }                       // deleted
for _ in 0..1_000_000 { black_box(exposure(black_box(&positions))); } // 23–28 ms, measured

It is best effort, for benchmarks only.

The other habit is the target. By default rustc compiles for the baseline x86-64 processor, which promises nothing newer than SSE2, so that the binary runs anywhere. -C target-cpu=native, used earlier in the book to get AVX2, enables every instruction the build machine has: the popcnt, tzcnt and lzcnt that the bitmap’s operations become, and AVX2 or AVX-512 for the vectoriser. The price is portability: on a processor without those features the binary dies at the first instruction it lacks, with an illegal-instruction signal. Naming a level both machines share, such as -C target-cpu=x86-64-v3 for AVX2-era parts, avoids that.

Reading what the compiler made

cargo asm --lib "<ch05_structures::Strategy>::exposure_iter" prints one function, --rust interleaves the source and --target-cpu=native builds for this machine; a function inlined everywhere has no body to print until it is marked #[inline(never)]. perf record -g -- ./binary samples where a running program is at regular intervals, and perf report --sort symbol ranks its functions by their share of the samples. perf annotate on one function shows each instruction beside its share of that function’s samples; a sample tends to land just after the instruction that stalled, so read a hot line together with the one above it. Four shapes deserve a second look: a call where none was expected, a function that did not inline or a call of __rust_alloc, the allocator’s entry; a cmp and a conditional jump to panic_bounds_check ahead of a load inside a loop; a div, integer division at 20–40 cycles, usually a % by a size that is not a constant power of two; and a rep movsb, the processor’s block copy, or a call memcpy, a large value being copied, often a struct passed or returned by value.

What it costs

A call and its return cost 1–5 ns, 4–20 cycles, plus the spilled registers, and nothing when inlined. A bounds check costs 0–1 cycle predicted and 15–20 mispredicted, plus the unrolling and vectorising it blocks. Zeroing runs at 10–20 GB/s, the 128 KB ring in 6–13 µs and 1 MB in 50–100 µs, with a minor fault of 0.5–1 µs per new 4 KB page on top, and MaybeUninit::uninit() costs nothing. Against 4,000 cycles none of these is large once; repeated, they are. A call per position over 64 positions is 64–320 ns, up to a third of a budget, that the inlined version does not pay, and a 64 KB buffer zeroed before every recv is three to six budgets. Undefined behaviour has no price on the ladder, only an unknown program.