locality of reference

Watch how you actually use a cookbook. You do not flip randomly across all 400 pages; you stay on one recipe for a while, glancing back and forth among its few pages, then move to the next recipe and settle there. And the pages you read next are usually close to the one you are on — the same recipe spans neighbouring pages. This habit, that your attention clusters in time and in space rather than scattering uniformly, is locality of reference. Programs behave the same way when they touch memory.

Concretely, locality comes in two flavours. Temporal locality says that if a program references a location now, it is likely to reference that same location again soon — a loop counter, a hot variable, a function called repeatedly. Spatial locality says that if a program references a location, it is likely to reference nearby locations soon — stepping through an array element by element, or executing instructions in sequence. Both kinds mean that over any short window of time, a program touches only a small, slowly shifting subset of its total pages rather than spraying references all over its address space.

Why it matters: locality is the single reason demand paging works at all, rather than being a disaster. If a program referenced its pages randomly and uniformly, almost every access would touch a non-resident page and fault, and the effective access time would collapse to disk speed. Because real programs have strong locality, the handful of pages they are currently using can stay resident in RAM, faults are rare after a warm-up, and the costly disk trips are amortized over many cheap in-memory hits. Locality is also the foundation of the working-set idea and of why caches and the TLB pay off. The honest caveat: programs with poor locality — random-access workloads over huge data sets — genuinely paginate badly and are exactly where virtual memory struggles.