Cache locality before cleverness

Count useful bytes before counting instructions

Imagine an illustrative record that occupies 128 bytes, while a repeated scan reads only one 8-byte score. Processing one million records means the useful scores total 8 megabytes, but the containing records occupy 128 megabytes before accounting for allocations outside the record. The exact traffic depends on layout, alignment, cache state and hardware behaviour. Still, the mismatch is a useful first question: why does a score scan need access to a representation dominated by fields it never reads?

Reducing one arithmetic instruction in that scan may be less useful than making the scores contiguous. That is not a prediction of a particular speedup. It is a hypothesis about what limits the operation. I would inspect the access pattern, measure the working set and compare a representation that exposes only the needed data. The goal is to identify whether the processor spends its time computing, waiting for dependent loads or moving more data than the operation logically requires. Each diagnosis suggests a different optimization.

Locality is a relationship between layout and work

Drepper's memory paper explains why nearby accesses and reuse can matter in a cache hierarchy, and why writes shared across cores can create coherence traffic. I take that as a model for asking questions, not a source of timeless nanosecond constants. Cache sizes, line sizes, prefetch behaviour and memory topology depend on the target. A layout that suits one access pattern can harm another. There is no universally cache-friendly container independent of the operations performed on it and the machine executing them.

In the illustrative record scan, storing scores separately may help an operation that reads scores only. If the next operation always needs score, timestamp and identifier together for one selected record, splitting every field into a separate allocation may require more independent memory accesses. The useful unit of locality is the group of values consumed together. I would trace real operations through the representation before choosing between an array of records, arrays of fields, or a hybrid grouping of frequently co-accessed fields.

References: [1] What Every Programmer Should Know About Memory — Ulrich Drepper

Contiguous handles are not contiguous payloads

Rust's Vec guarantees contiguous initialized elements, but the meaning of element matters. A Vec of boxed records has contiguous box handles, not necessarily adjacent record payloads. Likewise, a contiguous array of strings does not imply that all their text bytes are packed together. This distinction is easy to miss when a type looks like a simple list at the API level. The compiler cannot infer that independently allocated payloads should be repacked merely because the caller traverses their handles in order.

The illustrative structures below express two different choices. Keeping whole records together is straightforward when most operations consume a record as a unit. Keeping scores and identifiers in parallel arrays can reduce the data needed by a score-only pass, but creates an invariant that the arrays correspond. A more complete design would encapsulate mutation so callers cannot accidentally reorder one array alone. The performance benefit is not free: some simplicity moves from the iteration loop into the representation and its maintenance rules.

struct Record {
    id: u64,
    score: f64,
    description: String,
}

struct Scores {
    ids: Vec<u64>,
    values: Vec<f64>,
}

fn score_sum(values: &[f64]) -> f64 {
    values.iter().copied().sum()
}

References: [2] Rust standard library: Vec guarantees

Dependent loads can limit available parallelism

A linked traversal often needs one load to discover the address of the next load. Even if each node is small, that dependency can restrict how much work the processor overlaps. A dense array makes subsequent addresses easier to determine, although the actual benefit depends on the workload and hardware. I would distinguish bandwidth pressure from dependent-load latency: one asks how many bytes can move per unit time, while the other asks how long a chain must wait before it can reveal its next address.

An illustrative lookup workload can justify an index even if it requires an extra indirection, because avoiding a full scan changes the amount of work dramatically. That is the counterweight to locality advice: a contiguous linear scan is not automatically preferable to a less contiguous structure with much better search complexity. Compare at realistic sizes and query distributions. Small collections may favour simple scans; large or highly selective workloads may favour indexing. The crossover belongs to the measured application, not to a slogan about arrays beating pointers.

Write sharing can undo read locality

Packing frequently read fields together can be beneficial, but packing independently written counters together may cause different cores to contend over the same cache line. The counters need not be logically related for the hardware to move ownership at a coarser granularity. I would investigate this possibility when adding workers stops improving throughput despite little apparent lock contention. The question is whether the representation makes independent updates communicate through the memory hierarchy more often than the algorithm logically requires.

An illustrative statistics collector can keep per-worker counters and combine them periodically instead of updating one shared counter on every event. That reduces immediate sharing but changes the freshness of the aggregate and adds merge work. Padding fields apart can also increase footprint and hurt other accesses. Neither technique should be applied everywhere. Decide whether an approximate recent aggregate is acceptable, whether exact values are needed on every read and whether the extra memory buys a measurable reduction in harmful contention.

Working-set size belongs in the benchmark

A layout experiment should vary dataset size rather than choose one convenient input that fits comfortably in a cache. It should also vary access order, skew, update frequency and the amount of concurrent work. An illustrative score scan over ten thousand records may behave differently from the same scan over ten million, even when the source code is identical. If the claimed improvement depends on the dataset crossing a particular capacity boundary, that boundary is part of the explanation and should remain visible.

I would compare end-to-end operations as well as the isolated loop. A compact layout may require conversion, sorting or copying before the scan; those costs matter if the data is used only once. If the compact representation is reused repeatedly, the preparation cost may amortize. Record the reuse count and include the costs of maintaining the representation after updates. Otherwise a benchmark can reward a fast steady-state view while ignoring the expensive work necessary to keep that view correct under the application's actual mutation pattern.

Keep correctness checks outside the timed loop but inside the experiment. Reordering records can change floating-point accumulation order or observable tie-breaking even when every input remains present. An optimization that changes those results may be acceptable, but only under an explicit numerical or ordering contract, not because its benchmark happened to run faster.

Keep the representation understandable

The attraction of a sophisticated layout is that it can concentrate many small improvements: fewer bytes, better grouping, predictable access and simpler computation. The danger is that it can introduce undocumented coupling between fields, indices and lifecycle rules. I would require a readable ownership model and mutation API before accepting a complex representation. Debugging a wrong result caused by parallel arrays drifting out of alignment can erase a great deal of performance value, especially if the invariant is distributed across unrelated parts of the code.

My preferred sequence is to identify the expensive operation, describe its required data, try the simplest representation that exposes that data efficiently, and measure the complete cost. Only then would I reach for manual prefetching, architecture-specific instructions or a more elaborate indexing scheme. The strongest objection is that algorithmic improvements can dwarf locality improvements; that is correct, and algorithm choice stays in the comparison. Locality before cleverness means understanding the representation before decorating the loop, not refusing a better algorithm because its memory access is less tidy.