Operating systems · interactive

Cache locality

Memory moves into the cache in lines of several neighbouring values (4 here). Reading the next value in memory is almost free; jumping around misses every time. Same array, same sum, two loop orders.

for (r…) for (c…) sum += a[r][c]

0,00,10,20,30,40,50,60,71,01,11,21,31,41,51,61,72,02,12,22,32,42,52,62,73,03,13,23,33,43,53,63,74,04,14,24,34,44,54,64,75,05,15,25,35,45,55,65,76,06,16,26,36,46,56,66,77,07,17,27,37,47,57,67,7

Colored: the 4 lines currently in cache. Each row is 2 lines. Green: hit. Red: miss.

1 reads · 1 misses · final 16 of 64

Row by row walks memory in order: one miss loads a line, the next 3 reads hit. 16 misses.

Loop order

read 1 of 64

Step 2 of 4 · read left to right

1
Memory moves in lines
A miss loads a whole 64-byte cache line: 16 ints, not one.
Neighbours come free.
2
Walk memory in order
Arrays are stored row after row. Reading along a row uses every value in each line.
Hardware prefetchers also guess the next line.
3
Striding wastes lines
Jumping by a row each time uses one value per line, and big strides evict lines before you come back.
Same Big-O, several times slower.
4
Data layout is a performance choice
Arrays beat linked lists; struct-of-arrays beats array-of-structs when you scan one field; columnar databases exploit exactly this.
Measure with perf stat -e cache-misses.

In production

Tools and technologies

Data layout decides cache performance.

Not tied to one language — use these names when you search docs or design a system.