Cache lines and locality

Caches do not move single bytes. They move fixed-size blocks called cache lines: 64 bytes on x86 and most ARM server chips, 128 bytes on Apple Silicon. Read one int from DRAM and the hardware pulls in the whole surrounding line. If your next access is a neighbor in that line, it is a fast L1 hit.

The big idea

Programs have two kinds of locality:

• Spatial locality: if you touched address X, you will probably touch X + 8 soon. Arrays scanned in order are the ideal case. One DRAM trip brings in sixteen 4-byte integers.
• Temporal locality: if you touched X, you will probably touch X again soon. Loop counters, hot config values and the top of the stack stay in L1.

Hardware prefetchers amplify spatial locality. They watch the stream of misses, notice patterns like "the address goes up by 64 each time", and fetch lines before you ask. A sequential scan runs close to memory bandwidth with its latency mostly hidden.

A linked list or a tree of heap-allocated nodes defeats the prefetcher. The address of the next node is unknown until the current node arrives, so every hop pays full latency. That, more than big-O, is why arrays often beat linked lists in practice. See data structures in practice for more on this.

Walking through it: row-major vs column-major

C, Go, Rust, Java and NumPy (by default) store a 2D array row by row. Row 0 is contiguous, then row 1, and so on. The order of your loops decides whether you walk memory in order or jump around. Here is a complete program (the second loop is the variant discussed below):

#include <stdio.h>
#include <stdlib.h>

#define N 8192

int main(void) {
    int *a = malloc(sizeof(int) * N * N);      // 256 MB
    for (long k = 0; k < (long)N * N; k++) a[k] = 1;

    long sum = 0;
    for (int i = 0; i < N; i++)                // row-major: consecutive addresses
        for (int j = 0; j < N; j++)
            sum += a[i * N + j];

    printf("row-major sum: %ld\n", sum);
    free(a);
    return 0;
}

row-major sum: 67108864

Swap the two loops, so j is the outer loop and i the inner one, and the sum is the same. But each step now jumps N × 4 = 32 KB ahead. On an Apple M-series laptop in 2026 (clang -O1), the row-major loop took 31 ms and the column-major loop took 196 ms. Same arithmetic, 6.3× apart:

Elements:      8192 × 8192 = 67,108,864
Row-major:     31 ms / 67.1M  ≈ 0.46 ns per element
               each 64-byte line serves 16 consecutive ints,
               and the prefetcher streams lines ahead of you
Column-major:  196 ms / 67.1M ≈ 2.9 ns per element
               each access lands 32 KB from the last, on a new line
               and often a new 4 KB page (a TLB miss too)

On older hardware, or with larger strides, the gap is often 10× or more. The fix costs nothing: put the loop over the contiguous dimension innermost. In NumPy, prefer operations along the last axis.

Common mistakes

• Trusting big-O on pointer-heavy structures. A tree with many cache misses can lose to a small array scan.
• Benchmarking a tiny input. A loop over 10 KB runs in L1 and hides the costs that appear on real data.
• Iterating the wrong way. Column-major loops over row-major arrays are a silent 5 to 10× penalty.

Check yourself

• Why does the row-major loop beat the column-major loop when the arithmetic is identical? Consecutive elements share a cache line, and the prefetcher streams the lines in order. Column-major jumps 32 KB each step and misses almost every access.
• Why are arrays usually faster than linked lists for scans? Array elements sit side by side, so the prefetcher can run ahead. Linked-list nodes can be scattered, and each hop waits for the previous one.

Key takeaways

• Caches move 64-byte lines (128 on Apple Silicon). One miss brings in a neighborhood of data.
• Sequential, contiguous access gets many values per trip and is helped by prefetchers.
• Pointer chasing pays full latency on every hop.
• Loop order alone changed a 2D sum by 6.3× in the measurements above.

Further learning

Next, see how the layout of a record changes which bytes are loaded, in array of structs vs struct of arrays.

Mike Acton's data-oriented design talk is opinionated, but it is the most memorable argument for designing around how data flows through caches.