JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Locality: Why Caching Works

The last guide left us facing the memory wall — a processor that idles for hundreds of cycles waiting on slow DRAM. The escape is one deep observation about how real programs touch memory: locality. Meet temporal and spatial locality, the cache line they justify, and the hit/miss arithmetic (AMAT) that turns a tiny fast memory into an enormous fast one.

The trick that makes the wall climbable

The previous guide left us stuck against the memory wall: a CPU that can finish an instruction in a fraction of a nanosecond, chained to a main memory that takes hundreds of cycles to answer. The memory hierarchy promised a way out — a tiny, blazing-fast memory close to the core backed by ever larger, ever slower stores behind it. But a small memory can only ever hold a sliver of your data. Why should keeping a sliver close help at all, when the next thing the program asks for could be anywhere in a multi-gigabyte address space?

It helps because programs are not random. Watch any real program touch memory and you see something striking: the addresses it asks for are nothing like a fair lottery over the whole space. They cluster, in time and in place. This empirical regularity has a name — the principle of locality — and it is the single load-bearing fact under every cache ever built. Caching is not a clever way to make slow memory fast; it is a bet that the recent past predicts the near future, and on real workloads that bet pays off astonishingly often.

Two kinds of locality

Locality comes in two flavours, and it is worth feeling each one in your bones. Temporal locality says: if you touched an address recently, you are likely to touch it again soon. Think of a loop counter, a function you are inside, or a lookup table you keep re-reading — the same handful of locations get hammered over and over. The everyday picture is your desk: the few books you are actually using stay open on the desk, not reshelved after each glance, precisely because you keep coming back to them.

Spatial locality says something subtler: if you touched an address, you are likely to touch its neighbours soon. Walking through an array element by element, executing instructions one after another in memory order, reading the fields of a struct — all of these march through nearby addresses. The desk picture again: when you reach for one book in a series, the next volumes you will want are sitting right beside it, so it costs almost nothing to grab a small armful at once. That second insight is exactly why caches do not fetch single bytes.

The cache line: locality made concrete

Spatial locality has a direct hardware consequence. When the CPU needs a byte that is not in the cache, it does not fetch just that byte — it fetches a whole aligned block of contiguous bytes called a cache line, typically 64 bytes on modern machines. The bet is that you will soon want the neighbours too, so dragging them along now turns one slow trip into many fast ones. A cache, then, is not a bag of individual bytes; it is a shelf of fixed-size lines, each line a faithful copy of one aligned 64-byte chunk of main memory.

When the data you ask for is already sitting in a line in the cache, that is a cache hit — answered in a cycle or a few, almost for free. When it is not, that is a cache miss: the hardware must go to the next level down, pay the long miss penalty to drag the whole line up, install it, and only then serve your byte. The first byte of a freshly-touched line is always a miss; but thanks to spatial locality, the next 63 bytes you read from that same line are hits. One painful trip, then a run of cheap ones — that is locality converting raw slowness into average speed.

Doing the arithmetic: AMAT

How much does locality actually buy? We can put a number on it. The average memory access time (AMAT) folds the two cases — fast hits and slow misses — into one expected cost, weighted by how often each happens. The whole game is to make hits common and misses rare, because a miss is dramatically more expensive than a hit.

AMAT = hit time + miss rate x miss penalty

Example (one level of cache):
  hit time     =   1 cycle   (data already in cache)
  miss penalty = 100 cycles  (trip to slow DRAM)

  miss rate = 10%   ->  AMAT = 1 + 0.10 x 100 = 11 cycles
  miss rate =  3%   ->  AMAT = 1 + 0.03 x 100 =  4 cycles
  miss rate =  1%   ->  AMAT = 1 + 0.01 x 100 =  2 cycles

Note: without any cache, EVERY access costs 100 cycles.
Even a 10%-miss cache turns 100 into 11 -- a 9x speedup,
and it is locality that drives the miss rate down.
AMAT weighs a cheap hit against an expensive miss. Because the miss penalty dwarfs the hit time, small drops in miss rate produce large speedups — and locality is exactly what lowers the miss rate.

Stare at those numbers and the lesson jumps out. With no cache, every access pays the full 100 cycles. A cache that misses just 10% of the time already cuts that to 11 — and the only reason the miss rate is that low is that locality keeps the recently- and nearby-used lines on hand. This is a textbook case of making the common case fast: hits are the common case, so we make them cost almost nothing, and we tolerate the rare miss. Notice too that AMAT is recursive — when a miss happens, its penalty is itself an access to the next level, which has its own hit time and miss rate. That nesting is exactly why real machines stack several caches, a multilevel idea we will reach later in this rung.

Tracing a few accesses

Let us make it tangible. Suppose lines are 64 bytes and we run a loop that reads a contiguous array, one 4-byte integer at a time: `for i: sum = sum + a[i]`. Sixteen integers fit in one 64-byte line. Walk through what the cache experiences as we touch a[0], a[1], a[2], and so on, assuming the array starts at the beginning of a line.

  1. Touch a[0]: nothing is in the cache yet, so this is a compulsory miss. The hardware fetches the whole 64-byte line — a[0] through a[15] — paying the miss penalty once, and installs it.
  2. Touch a[1] through a[15]: every one of these is already in that freshly-loaded line, so all 15 are hits. This is spatial locality cashing in — one slow trip bought sixteen accesses.
  3. Touch a[16]: this falls into the next aligned 64-byte block, which is not cached yet, so it is a miss. Fetch that line, and a[16] through a[31] become resident.
  4. The pattern repeats: exactly one miss per 16 elements, the rest hits. The miss rate settles near 1/16 (about 6%), and AMAT collapses toward the hit time. Now also reuse sum each iteration — that variable lives in a register or stays hot in cache by temporal locality, costing nothing extra.

Both kinds of locality are at work in that one tiny loop: spatial locality across the array (each line serves sixteen reads), and temporal locality on sum (touched every iteration, never evicted). Now flip the script — imagine reading the array with a huge stride, say every 16th element, so each access lands in a different line. Every read becomes a miss, you fetch 64 bytes to use only 4, and the very same computation crawls. The data is identical, the answer is identical, but locality is gone — and with it, all the cache's benefit. That gap, between locality-friendly and locality-hostile traversal, is the heart of cache-aware programming, and it is where the last guide of this rung will take us.