The Page-Table Walk: Dependent Loads All the Way Down
A translation the TLB does not have must be looked up in tables that live in memory. The lookup is multi-level, each level depends on the one before it, and any of them can miss in cache — which is why a TLB miss is expensive out of all proportion to the work it represents.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
One flat table would not fit
Start with the naive design: one array, indexed by page number, holding frame numbers. On a 64-bit machine with 4 KiB pages, the virtual page number is large enough that a complete flat table would need vastly more memory than the machine has — and every process would need its own. The design is not merely wasteful, it is impossible.
Worse, it would be almost entirely empty. A typical process maps a few regions — code, heap, stack, some libraries, some mapped files — scattered across an enormous address space. A flat table pays for the whole space; the process uses a vanishingly small fraction of it.
The fix is a sparse tree. Split the page number into several fields, each indexing one level. Levels covering unmapped regions simply do not exist, so a process pays only for the parts of its address space it actually uses. The cost is that a lookup now requires walking down the tree rather than a single index.
| Property | Single flat table | Multi-level tree |
|---|---|---|
| Memory per process | Proportional to the entire address space | Proportional to what is actually mapped |
| Unmapped regions | Still occupy table space | Cost nothing — the subtree is absent |
| Lookup cost | One access | One dependent access per level |
| Parallelism within a lookup | N/A | None — each level needs the previous result |
| Feasible on 64-bit | No | Yes, and it is what every mainstream design does |
The walk is a dependency chain
Here is the property that makes the cost bite. To read level two, the CPU needs the address that level one returned. To read level three it needs level two's result. The loads cannot be issued together, cannot be reordered around each other and cannot be overlapped — they are a serial chain of dependent memory accesses.
This is the same pattern as Pointer Chasing: The Address You Do Not Have Yet in application code, and it is slow for the same reason: out-of-order execution cannot hide a latency it cannot start early, and a prefetcher cannot predict an address it has not seen yet. Everything a modern CPU does to overlap memory latency depends on knowing the address ahead of time, and a walk defeats all of it by construction.
And each of those levels is ordinary memory, so each can miss in the data cache. A walk whose levels all hit in cache is a handful of fast accesses. A walk that misses at several levels is several *DRAM round trips*, serialised. That is the difference between a TLB miss being an annoyance and a TLB miss being the thing your profile is made of.
Why hardware caches the walk itself
Because the upper levels of the tree change slowly and are shared by enormous ranges of addresses, hardware caches intermediate results in structures separate from the TLB — often called page-walk caches. A miss on a nearby address can then skip the upper levels and resume partway down.
This is why TLB misses within one region are far cheaper than TLB misses scattered across the address space: the former reuse the cached upper levels, the latter re-walk from near the top. It is the same locality argument as the data cache, applied one level of indirection up, and it is invisible to any counter that only reports "TLB miss".
The scale below shows the shape. Note it is unitless by design: what transfers is that a fully-missing walk is drastically more expensive than a partially-cached one, not any particular figure. Under virtualization the picture gets worse again, because guest and host translation compose — see What a vCPU Actually Is.
Key points
- A flat page table is impossible on 64-bit, so translation uses a sparse multi-level tree that costs only what is mapped.
- The walk is a chain of dependent loads: each level needs the previous level's result, so none of them can overlap.
- Every level is ordinary memory and can miss in cache, so a walk can turn into several serialised DRAM round trips.
- Hardware caches intermediate walk results, which is why scattered misses cost far more than clustered ones.
- This dependency chain is why a TLB miss costs vastly more than the "one extra lookup" intuition predicts.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1TLB → walker: the lookup missed, so the hardware page walker is started with the virtual address.
- 2Walker → level 1: the table base register plus the top field of the page number gives the first entry's address.
- 3Level 1 → level 2 → level 3: each entry supplies the base of the next table; each load must wait for the previous result.
- 4Leaf entry → physical address: the frame number is combined with the untranslated page offset.
- 5Walker → TLB: the completed translation is installed so the next access to this page skips the walk entirely.
- • Assuming a TLB miss costs "one memory access" and pricing it accordingly; it is a serialised chain, potentially several DRAM trips.
- • Expecting the prefetcher to hide walk latency. It cannot prefetch an address that does not exist until the previous level returns.
- • Treating all TLB misses as equal. A miss near a recently-walked page is far cheaper than one in a fresh region, and no ordinary counter distinguishes them.
- • Concluding that because data fits in L1, translation cannot be the problem — the two structures have entirely separate working sets.
Consequences, controls and cost
- • Translation cost scales with how scattered your pages are, not with how many bytes you touch.
- • A TLB miss cannot be hidden by out-of-order execution, because the walk's addresses are not known in advance.
- • Access patterns that defeat data prefetching usually defeat translation locality too, so the two costs arrive together.
- • Larger pages reduce walk frequency by covering more memory per entry — the mechanism behind [[huge-pages]].
- • Nested translation under virtualization multiplies the number of dependent accesses in an uncached walk.
- • Reduce the number of distinct pages a hot loop touches: contiguous layouts and blocked traversal reuse translations as well as cache lines.
- • Prefer one large allocation over many small scattered ones, so the working set clusters into fewer subtrees.
- • Consider huge pages for genuinely large working sets, which cuts both walk frequency and TLB pressure at once.
- • Keep hot data structures adjacent rather than pointer-linked across the heap, for the same reason [[array-vs-linked-list]] favours arrays.
- • Otherwise: nothing directly. You cannot instruct the walker — you can only give it less to do.
- • Compare `dTLB-load-misses` against `dTLB-load-misses.walk_completed`-style events where available: the ratio hints at how many misses required a full walk.
- • Look for walk-cycle counters (`dtlb_load_misses.walk_active` or the equivalent) — they attribute stall cycles to translation directly, rather than to "memory".
- • Run the workload with huge pages on and off; a large delta in walk cycles proves translation was a real cost rather than a suspicion.
- • Correlate TLB miss rate with the number of distinct pages touched per iteration, not with bytes touched — that is the variable that actually drives it.
- • The sparse tree makes 64-bit address spaces affordable, at the cost of turning one lookup into a serial dependency chain.
- • More levels cover more address space but lengthen every uncached walk; fewer levels shorten walks but coarsen the mapping granularity.
- • Walk caches make clustered misses cheap, which makes performance depend on access locality in a way that is hard to observe directly.
Scope
§224 — what these claims are specific to.
- MICROARCH-SPECIFICLevel counts, walk-cache organisation and whether the walk is hardware- or software-managed all vary. x86-64 and AArch64 walk in hardware; some MIPS and older RISC designs trap to software instead.
- SIMPLIFIEDThe four-level example omits page-size promotion at intermediate levels, permission composition down the tree, and address-space identifiers. The dependency-chain property, which is the lesson, is unaffected.