# Techniques and evidence

Durable facts behind `SKILL.md`, each with its source.
Numbers are from the cited measurements; rerun on the target machine before relying on them.

## Cost model

- Cache line is 64 bytes on common targets (32 or 128 exist); every access goes through one; the question is only whether one gets evicted. [Kelley]
- Latency ladder (2020 numbers): L1 ≈ 1 ns, branch mispredict ≈ 3 ns, L2 ≈ 4 ns, mutex lock/unlock ≈ 17 ns, main memory ≈ 100 ns; each level is an order of magnitude. [mnt.io], [Kelley]
- Arithmetic, including multiplication, is faster than an L1 read; recomputing can beat memoizing. [Kelley]
- A heap allocation typically takes a global lock and may reach a kernel call; small allocations are not cheaper than large ones. [perf-book]
- L1 data cache is on the order of 32 KB; hot-loop data that does not fit there is data-bound, and layout work pays only when the workload is data-bound rather than compute-bound. [gendignoux]

## Layout rules (Rust)

- rustc reorders struct and enum fields to minimize padding unless `#[repr(C)]` is set. [perf-book]
- Alignment of a struct is its largest field's alignment; size rounds up to a multiple of it; `u32, u64, u32` is 24 bytes, reordered 16; adding one `bool` to the 16-byte form costs 8 bytes. [Kelley]
- Enum size is the largest variant plus discriminant, minus niches; one outsized variant inflates every value; box it when rare. [perf-book]
- Types larger than 128 bytes are moved with `memcpy` rather than inline code. [perf-book]
- `Vec` is three words (ptr, len, cap); `Box<[T]>` is two; `ThinVec` is one with len and cap in the allocation. [perf-book]
- `-Zprint-type-sizes` (nightly) prints size, alignment, per-variant sizes, field order, and padding; `top-type-sizes` compacts the output. [perf-book]
- Guard hot types with a static size assertion under `#[cfg(target_arch = "x86_64")]`; sizes differ per platform. [perf-book]

## Shrinking strategies

- Indexes instead of pointers: 64-bit pointers double a record on 64-bit targets; `u32` indexes halve it and drop alignment to 4, so a following `u32` field costs no padding. Type the index (newtype) or lose the compile-time safety pointers gave. [Kelley], [Weissflog]
- Booleans out of band: keep alive and dead in two arrays; the bit lives in which array, the loop over the live array has no branch and no load. 24 → 16 → 12 bytes in the monster example. [Kelley]
- Sparse fields in a side table keyed by index: with 10 % of records holding an item list, 366 KB → 198 KB for 10 000 records, overhead included. [Kelley]
- Struct of arrays removes per-element padding: a pointer plus a one-byte enum in an array of structs pays 7 bytes of padding per element; as two arrays, none. 160 KB → 91 KB for 10 000 elements. [Kelley]
- Small integers for indexes (`u8`, `u16`, `u32`) and coercion to `usize` at use points. [perf-book]
- `smallvec` | `arrayvec` for many short vectors; `SmallVec` is slightly slower per operation and larger when `N` or `T` is big; `ArrayVec` when the maximum is known. [perf-book]
- `smallstr` | `smartstring` (`compact_str` is the same idea) inline strings under 24 bytes. [perf-book]
- Measure the length distribution at a hot `push` site before choosing capacity or inline size. [perf-book]

## Access-pattern layout

- Struct of arrays vs array of structs: position and velocity update over players ran in half the time as SoA because the loop vectorized over contiguous fields; with the wider target features the gap shrank to the cache-bandwidth difference; set `target-cpu` deliberately for benchmarks and deployment. [jamesmcm]
- Branch on a kind tag inside a hot loop vs pre-split arrays per kind: about 4× faster split. [jamesmcm]
- `LinkedList` vs `Vec` iteration: about 10× faster `Vec`. [jamesmcm]
- `Vec<Box<dyn Trait>>` vs generic `Vec<T>`: about 4× faster monomorphized; `Vec<Box<T>>` monomorphized was nearly as slow as `dyn`, so the cost is the indirection, not the vtable. [jamesmcm]
- `Vec<Vec<usize>>` for a 5-element ranked ballot is 216 bytes; flattened to `Box<[u8]>` values plus `Box<[u8]>` cut positions it is 48 bytes and ran up to 20 % faster on a data-bound workload. [gendignoux]
- Bit-packing the same data to 3 bytes reduced cache misses and ran ≥ 30 % slower from unpacking cost and forced a GAT-heavy refactor; optimize one metric and others regress. [gendignoux]
- Sorting records halved branch misses (16 % fewer cycles) but sorting owned pointers randomizes heap order: 2× L1 misses, 14× L3 misses. Cloning after the sort restored sequential heap order for another 10 %; production code should use an arena rather than rely on allocator order. [gendignoux]
- Inlining is the root optimization; `#[inline(always)]` on tiny arithmetic newtype methods gave 30 % when rustc declined to inline. [gendignoux]

## Allocation and sharing

- `Rc`/`Arc` on rarely shared values raises allocation rate; `clone` of `Arc` is a count increment, `clone` of `Vec` is an allocation. [perf-book]
- `clone_from` reuses the destination allocation. [perf-book]
- Workhorse collections: declare outside the loop, `clear()` per iteration; or keep one in the struct. [perf-book]
- `BufRead::lines` allocates per line; `read_line` into one reused `String` does not. [perf-book]
- `Cow<'static, str>` holds literals and formatted strings in one `Vec` without promoting literals. [perf-book]
- Cloning a 144-byte value under a read lock inside a comparator produced 322 042 allocations and 743 MiB for one sort of ~600 items, plus lock contention; the fix reads the needed fields into a compact, sortable record once (data-oriented view), then sorts: 98.7 % less time. [mnt.io]
- DHAT identifies hot allocation sites; `dhat-rs` heap-usage tests pin allocation counts so they cannot regress. [perf-book]

## Tools

- `std::mem::size_of`, `-Zprint-type-sizes`, `top-type-sizes`, `static_assertions::assert_eq_size!`.
- `criterion` for benchmarks; `perf stat -d` for cycles, IPC, branch misses, L1/LLC misses; `perf record` + flamegraph for where.
- `cargo-show-asm` or Godbolt to confirm vectorization.
- `soa-rs` | `soa_derive` for derived struct-of-arrays; `slotmap` | `id-arena` when generational handles are needed; plain `Vec` + `u32` newtype otherwise.

## Sources

- [Kelley] Andrew Kelley, "A Practical Guide to Applying Data Oriented Design", Handmade Seattle 2021; transcript at josherich.me.
- [jamesmcm] James McMurray, "An introduction to Data Oriented Design with Rust", 2020, with criterion benchmarks and Godbolt links.
- [gendignoux] Guillaume Endignoux, "Making a parallel Rust workload even faster with data-oriented design (and a sprinkle of unsafe)", 2024, with `perf stat` output.
- [mnt.io] Ivan Enderlin, "About memory pressure, lock contention, and Data-oriented Design", 2026, Matrix Rust SDK room list.
- [perf-book] Nicholas Nethercote, "The Rust Performance Book", chapters "Type Sizes" and "Heap Allocations".
- [Weissflog] Andre Weissflog, "Handles are the better pointers", 2018.
- [Fabian] Richard Fabian, "Data-Oriented Design" (dataorienteddesign.com/dodbook), the long form.