Hardware labs

1.10 Lab

Rules for every measurement

Predict before you measure: write down a number and the reasoning behind it, then run the binary. A wrong prediction teaches you something about the machine; an unpredicted measurement teaches you only a number.

Build in release mode; debug builds run 10–50× slower and distort the ratios. Warm up before timing, because the first pass pays page faults, cold caches and an untrained predictor. Pin to one core, for example taskset -c 3 ./target/release/stride. Set the governor with cpupower frequency-set -g performance and disable turbo if you can; if you cannot, note it, because 30% clock swings swamp small effects.

Each binary repeats its measurement and prints p50, p99 and max. Run each three times; if the p50s disagree by more than about 5%, something is interfering. Never report a mean. It blends the common case with the rare slow one, and in trading the rare slow one is where the money goes.

Lab 1.1 — stride walk (ch01-hardware/src/bin/stride.rs)

The exercise allocates 256 MiB of u64 (33,554,432 elements) and touches every page. For strides of 1, 2, 4, … 4,096 elements, it sums every stride-th element across the array and prints the time per pass and per access.

Reason it through. Eight elements is 64 bytes, one line. For strides 1 to 8, every line is fetched once per pass, in order, and the prefetchers stream at memory bandwidth. If memory bandwidth dominates, time per pass can stay near 256 MiB ÷ 15–20 GB/s, or 13–18 ms, while time per access rises from about 0.4 ns to 3 ns. On Intel, stride 16 may stay flat too, because the adjacent-line prefetcher fetches the lines you skip. From 128 bytes to 2 KB, each access touches a fresh line and the stride prefetcher sees fewer accesses per page, so expect 5–10 ns per access. At 4 KB and beyond, every access is on a new page: the prefetcher gives up and each access also misses the TLB, the cache of address translations. Expect a knee, then a plateau around 10–30 ns.

That plateau sits well below the 90 ns DRAM latency, and that is the lesson. Stride addresses are computed, not loaded, so multiple misses can overlap. At very large strides the number of distinct lines visited also shrinks enough to fit in cache on later passes. You are measuring a mix of parallelism, prefetching, translation and residency, not a pure DRAM latency curve.

Pitfalls: a slow first stride means you timed page faults. A surprisingly low plateau may mean transparent huge pages are on (/sys/kernel/mm/transparent_hugepage/enabled), removing the TLB misses. Write down where time per pass stops being flat, the knee, and any plateau or fall. To locate cache capacities, add a separate working-set sweep at a fixed access pattern; changing stride in one large array does not isolate those boundaries.

Lab 1.2 — branches (ch01-hardware/src/bin/branch.rs)

The binary fills 100 MB with uniform random bytes and sums every byte greater than 128, in three variants: branchy over unsorted data, branchy over a sorted copy (the sort is not timed), and branchless over unsorted data. Run each under perf stat -e branches,branch-misses,cycles,instructions; --help lists the variant names.

Reason it out. On random data the condition is true for 127 of 256 values, close to a coin flip: about 50 million mispredicts at roughly 17 cycles each, 850 million wasted cycles, about 0.2 s. The basic work, about a cycle per byte, adds roughly 25 ms. On sorted data the predictor fails only at the boundary, so expect 25–50 ms. The branchless loop never mispredicts and should also take 25–50 ms, or less if vectorised.

So expect unsorted-branchy to be 4–8× slower than either alternative, with about 50 million branch misses against near zero, and IPC around 0.5–1 against 2 or more.

The common pitfall is that LLVM may turn the branchy loop into a cmov or vector code by itself, and then all three run at the same speed. If unsorted-branchy is not clearly slower, read the assembly before concluding anything. Inside a VM, perf stat may print <not supported>. Write down time, branch misses and IPC for all three.

Lab 1.3 — false sharing (ch01-hardware/src/bin/false_sharing.rs)

The binary starts two threads pinned to chosen cores. Each performs 100 million fetch_add(1, Ordering::Relaxed) on its own AtomicU64. In the adjacent variant the counters sit side by side in one struct; in the padded variant each is wrapped in CachePadded.

Reason it out. Padded, each line stays Modified in its own L1 and an atomic add costs about 5 ns, so expect roughly 100 M × 5 ns = 0.5 s. Adjacent, the line bounces. A core sometimes completes several increments while it holds the line, so not every increment pays the full 50–100 ns, but many do. Expect 5–20× slower: roughly 2.5–10 s.

The pitfalls come from topology. Hyperthread siblings share one L1, so the line never moves and the effect vanishes; /sys/devices/system/cpu/cpu3/topology/thread_siblings_list names a core’s sibling. Cores on different sockets make the adjacent case far worse, which is worth seeing once. Run perf c2c record on the adjacent variant and find the line with offsets 0 and 8. Write down both times, the ratio, and the cores used.

Lab 1.4 (stretch) — pointer chasing (ch01-hardware/src/bin/chase.rs)

The binary builds 10 million nodes two ways: a Vec<u64> summed in order, and a linked list of individually heap-allocated nodes whose links are shuffled into random order. It times a full traversal of each.

Reason it out. The Vec is 80 MB read sequentially, bound by bandwidth: about 5–10 ms, under 1 ns per element. The list is a chain of dependent loads to random addresses, each a DRAM miss plus usually a TLB miss, with nothing overlapping. Expect 100–150 ns per node, 1–1.5 s in total, a ratio of 100–300×. The per-node time is the most honest memory-latency figure you will get from user code; compare it with the ladder and the Lab 1.1 plateau.

Pitfall: without the shuffle, nodes sit in allocation order and the list looks only a few times slower, the trap from section 1.4. For a huge-page comparison, allocate the nodes from a mapped arena and verify AnonHugePages; merely enabling THP does not guarantee scattered small allocations use huge pages. Write down time per element for both, with and without huge pages.