Spatial locality is the tendency to access nearby locations in computer memory within a short interval. A sequential scan of a contiguous array has spatial locality even when each element is read only once. A memory cache can exploit spatial locality by fetching a whole cache line on a cache miss: later reads of neighbouring elements become cache hits. Proximity is in the address layout, so visually adjacent entries in a table need not be adjacent bytes.
Consider a array of 32-bit integers, each occupying four eight-bit bytes, stored contiguously in row-major order. Use toy physical addresses starting at zero, aligned to a 16-byte cache line boundary. For row and column , with , the address and cache block number areHere is the floor function. Each row occupies exactly one cache line: row zero begins at addresses , row one at , and so on. Row-major order describes this storage layout; traversal can follow rows or columns without moving the elements.
Read all sixteen elements and compute their integer sum, keeping the accumulator outside the modelled memory cache. Only the sixteen array reads count as memory references. The toy fully associative cache starts empty, holds exactly one 16-byte cache line, fetches the requested cache block on every cache miss, and uses LRU replacement. No cache block is fetched ahead of a request, and no writeback costs are counted because the modelled accesses are reads.
- Traversing by rows, with varying fastest, requests cache blocks . Each first read in a row is a cache miss; the next three are cache hits. Total: four cache misses and twelve cache hits in sixteen memory references.
- Traversing by columns, with varying fastest, requests cache blocks four times. Every read replaces the sole resident cache line, so the next read always causes a cache miss. Total: sixteen cache misses and zero cache hits in sixteen memory references.
Every element is read once in both traversals. The row traversal exploits spatial locality between distinct elements and temporal locality of their shared cache block. The column traversal returns to each cache block after three other distinct cache blocks, too late for the one-line memory cache. Increase the fully associative cache to four cache lines and both traversals give four compulsory misses and twelve cache hits: no loaded cache block needs eviction. The difference therefore depends on capacity as well as access order and layout.
This makes spatial locality useful and beautiful: the same logical operation on the same elements can use a fetched cache line much more fully simply by changing traversal order. The toy counts do not predict a universal speed ratio on real hardware. Actual cache line sizes, capacities, placement rules, fetching ahead of requests and overlapping work affect runtime; measure a concrete implementation with statistical program profiling. Ulrich Drepper's November 2007 authored paper explains cache line transfers and gives array and matrix access examples connecting layout, temporal locality and spatial locality. Its hardware measurements are historical examples, rather than specifications for every present-day CPU. [ref]
// Destination: computer-science.bigb
New to topics? Read the docs here!