Cache locality

A cache is a small, fast memory between the CPU and main memory. Data moves in blocks called cache lines (typically 64 bytes). A program runs faster when most of its memory accesses are hits. Cache locality is the tendency of a program to access data that is already in, or close to, the data in the cache.

Two kinds of locality

Type	Meaning	Example
Temporal locality	A location that was just used is likely to be used again soon	A loop variable or a running sum accessed in every iteration
Spatial locality	Locations near a recently used one are likely to be used soon	Walking through consecutive array elements

When one element is fetched, the whole line comes with it (for example 16 consecutive 4-byte ints), so sequential access gives about 1 miss per 16 accesses, while a large stride can give a miss on every access.

Why it matters in loop optimization

Loops execute most of a program's instructions and memory accesses. A cache miss costs on the order of 100 cycles against 1-4 for a hit, so the order in which a loop nest touches memory often matters more than the arithmetic it does.

Example (C arrays are stored row by row)

// Poor spatial locality: column-wise walk, stride = N elements
for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
        sum += a[i][j];

// After loop interchange: row-wise walk, stride = 1
for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        sum += a[i][j];

Both loops compute the same result, but the second uses every element of each fetched cache line before it is evicted.

Loop transformations that improve locality

Transformation	Effect
Loop interchange	Reorders nested loops so the innermost loop has stride 1
Loop tiling (blocking)	Splits the iteration space into small blocks that fit in the cache so data is reused (key for matrix multiplication)
Loop fusion (jamming)	Merges loops that use the same data so it is used while still in cache
Loop fission (distribution)	Splits a loop whose body touches too much data for the cache
Array padding / data layout change	Avoids conflict misses; structure-of-arrays vs array-of-structures

The compiler applies these only after a dependence analysis shows that the new order gives the same results.