Cache lines and useful locality

Imagine a hypothetical cache with 64-byte lines and an aligned array of eight-byte values. Each complete line contains eight array elements. A sequential read can consume all eight after the first fill, provided the line stays available. A read that takes one element from each distinct line consumes only one eighth of each fetched line. The cache-line size here is a declared example parameter, not a universal property of every processor or every cache level.

Alignment changes which line contains an element. An access spanning a boundary can touch two lines even when its payload is small. Distinguish the processor instruction's access size from the bytes transferred at the particular hierarchy boundary under discussion. Compression, write policies, speculative accesses, and prefetching can change traffic further. State whether an estimate counts demand fills, all memory-controller traffic, or only useful application bytes; those quantities answer different questions.

Temporal locality means returning to previously used data; spatial locality means using nearby data that arrives together. Neither is a yes-or-no property of an entire program. A matrix multiply may reuse a small tile intensely while streaming through another matrix. A pointer chase may revisit the same nodes only after touching a much larger intervening set. The order of access therefore matters as much as total allocation size when deciding whether useful data can remain close to execution.

Blocking reorganizes work so a manageable subset receives repeated use before the program moves on. Count inputs, outputs, and temporary storage together when choosing a block. Fitting their nominal bytes into a cache is necessary for some reuse plans but does not guarantee residency: set conflicts, competing threads, replacement, and shared cache capacity still matter. Verify the transformation preserves dependencies and numerical requirements before interpreting any speed improvement as a memory benefit.

Compare two traversal orders with identical useful work and data, while recording dimensions, layout, initialization, and thread placement. Keep correctness checks outside the timed region when appropriate, but prevent the compiler from removing the computation. Test more than one working-set size: a change that helps a tiny hot loop can lose when extra packing or copying dominates. Elapsed time is the outcome; misses and transferred bytes provide supporting evidence about the mechanism.

After the spatial byte calculation, inspect temporal reuse in the cache lab. It starts empty, uses fully associative LRU replacement, and requests address identifiers (i×s) mod 16 for N=min(4096,16+floor(2t)) requests. Reset, set capacity C=4 and stride s=4, then predict the time-zero readout: the four-address period gives four misses and twelve hits among sixteen requests. Step adds one request, which hits. For a separate run, Reset and re-set C=4, s=3: predict a sixteen-address period and sixteen misses at time zero. The first working set fits; the second exceeds four entries and continues evicting entries before reuse. Control edits recompute the trace at retained elapsed time, so Reset separates comparisons. These are abstract address identifiers, not CPU cache lines or byte addresses. The toy has no set mapping, spatial line fills, prefetching, or measured processor timing.