data locality

Suppose you are cooking from a recipe and you keep flour, sugar, and eggs out on the counter for the whole bake — you reach for them again and again without trips to the pantry. Now suppose instead you put each ingredient away the instant you used it, then fetched it back from the pantry every time. Same recipe, same ingredients, but the second way is exhausting. Data locality is the property of a computation that decides which of these two cooks it resembles: it is how much your program reuses data that is already close at hand before reaching for something far away.

There are two flavours. Temporal locality means you reuse the same data soon after touching it — like keeping eggs out because you crack one every minute. Spatial locality means that when you touch one item you soon touch its neighbours in memory — like grabbing the whole carton because you will use the eggs right next to each other. Caches reward both: temporal locality keeps hot data in the fast levels, and spatial locality cashes in on the fact that a cache miss drags up a whole 64-byte line at once, so neighbouring values come along for free. Code with good locality runs almost entirely from cache; code with poor locality keeps falling through to slow memory and stalling.

Locality is the lever that turns a flop-bound theory into machine-real speed. The reason BLAS level-3 operations (matrix-matrix) are so much faster per flop than level-1 (vector) operations is locality: a matrix multiply touches each loaded value O(n) times, while a vector add touches each value once. Almost every classic high-performance technique — loop reordering, blocking and tiling, storing arrays in the order you traverse them, structure-of-arrays layouts for SIMD — is a maneuver to raise locality. You cannot reduce the data; you can only arrange to reuse each piece many times while it is hot.