= Spatial locality
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 $4\times4$ <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 $i$ and column $j$, with $0\leq i,j<4$, the address and <cache block> number are
$$
\operatorname{address}(i,j)=4(4i+j),\qquad
\operatorname{line}(i,j)=\left\lfloor\frac{\operatorname{address}(i,j)}{16}\right\rfloor=i.
$$
Here $\lfloor\cdot\rfloor$ is the <floor function>. Each row occupies exactly one <cache line>: row zero begins at addresses $0,4,8,12$, row one at $16,20,24,28$, and so on. <Row-major order> describes this storage layout; traversal can follow rows or columns without moving the elements.
\Image[/array-traversal-spatial-locality.png]
{title=Two traversal paths through the same <row-major> <array>, coloured by physical <cache line>}
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 $j$ varying fastest, requests <cache blocks> $0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3$. 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 $i$ varying fastest, requests <cache blocks> $0,1,2,3$ 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>.
\Image[/cache-line-traversal-misses.png]
{title=All sixteen <memory references> and their <cache hits> or <cache misses> with capacity one <cache line>}
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>. https://www.akkadia.org/drepper/cpumemory.pdf[Ulrich Drepper, What Every Programmer Should Know About Memory, sections 3.2 and 6.2.1: cache operation and optimizing data-cache access]{ref}
// Destination: computer-science.bigb
Back to article page
