Cache-Friendly Code — Why Two O(n) Loops Can Differ by 10×

Two implementations with identical complexity can differ by an order of magnitude, because the CPU never fetches one value — it fetches a 64-byte block. Locality, cache lines, arrays versus linked lists, AoS versus SoA, loop order and false sharing, from zero assumed background to checking it yourself with perf.

An analogy: the library won't fetch a single book

Picture a library with closed stacks. You request one book, and the librarian wheels out the whole shelf section it came from. If your next request happens to sit on that same cart, you get it instantly. If it doesn't, that's another trip to the stacks.

In this library, the wait is set by the number of trips, not the number of books. Reading 100 books in shelf order takes a handful of trips; reading the same 100 in lottery order takes 100. Same book count, wildly different afternoon.

That is exactly the relationship between a CPU and memory. The CPU never pulls a single number out of RAM. It always pulls a fixed-size block — 64 bytes on most machines — and parks it on a small shelf nearby, the cache. Algorithm textbooks count how many books you read. Wall-clock time is decided by how many trips you make.

Why fetch in blocks — locality as a bet

Blocks exist because, as The Memory Wall from Scratch works out from the physics, fetching one lone value from far away is brutally expensive. Almost all of that cost is the trip itself; dragging the neighbours back along with it adds almost nothing. So the hardware always takes the neighbours.

Whether those neighbours turn out to be useful is a bet on how programs behave. The bet rests on two kinds of locality:

• Temporal locality: a value you just used is likely to be used again soon (loop variables, a recently touched table)
• Spatial locality: if you used a value, the one next to it is likely to be used too (walking an array)

The hardware then raises the bet. A circuit called the prefetcher detects regularity — "this code is reading sequentially", "this code is jumping by a fixed step" — and pulls in blocks nobody has asked for yet. Code that sweeps regularly laid-out data is fast because that guess keeps landing. Code whose next address is unknowable until you read memory itself — anything that chases pointers — gets no prefetching at all, by construction.

The mechanism: the cache line is the unit

The smallest thing a cache handles is a cache line: 64 bytes on x86-64 and most Arm cores, 128 bytes on Apple silicon. Read one 4-byte int and the entire 64-byte line containing it lands in cache. The 15 neighbours come along for free.

When you sweep a contiguous array from the front, the fraction of accesses that miss (that need a trip) is a plain division.

$s$ is the size of one element in bytes, $B$ is the cache line size in bytes, and $m$ is the fraction of accesses that miss. In words: if 4-byte elements ride in 64-byte blocks, only one access in 16 causes a trip. The other 15 are served off the shelf.

Perceived time follows directly from $m$.

$t_{\text{hit}}$ is the time when the value was already on the shelf, $t_{\text{miss}}$ is the extra time a trip costs, and $T$ is the average time per access. In words: average time = the usual time + probability of being wrong × the penalty for being wrong. The penalty is what makes this interesting: an L1 hit costs a few cycles, while going all the way to DRAM costs on the order of hundreds of cycles — two orders of magnitude apart (exact figures vary by machine).

So an implementation with $m = 1/16$ and one with $m = 1$ can differ by a large factor in runtime while executing the same number of instructions. And because the penalty grows the further out you go, the gap can appear discontinuously: two implementations run neck and neck until the working set outgrows a cache level, and then one of them falls off a cliff. O(n) versus O(n) — the fight is decided by the constant factor. That is what this article is about.

What this figure leaves out is the whole subject of this article. Every curve here has a coefficient of 1; you never see several lines of the same shape stacked at different heights. Complexity notation was built to compare growth as the input gets large, so the coefficient is discarded up front. And that coefficient is usually set not by the algorithm but by how the code touches memory.

The rest of this piece walks through the four things that build that coefficient: how data is laid out (array versus linked list), how records are stored (AoS versus SoA), the order of your loops, and threads writing to the same line — false sharing.