When Translation Itself Is the Bottleneck
A profile shows memory stalls. The data fits in cache. Cache miss rates look fine. The stalls are real and the usual suspects are all innocent — because the CPU is not waiting for data, it is waiting to find out where the data is.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Two working sets, only one of which you were watching
A program has a data working set measured in bytes and a translation working set measured in pages, and they are not proportional to each other. Touching one byte on each of ten thousand pages is a trivial data footprint and an enormous translation footprint.
The pathological pattern is a large stride. Walk an array with a step larger than a page and every single access lands on a fresh page: the data cache sees a stream of misses it can prefetch, but the TLB sees a new translation every time and can predict nothing. Reduce the stride so several accesses share a page and the translation cost collapses while the data cost barely moves.
The comparison below is the whole lesson. Both loops read the same number of elements from the same array. One reuses translations, the other does not, and nothing in the source hints at which is which.
1// stride chosen so consecutive accesses land on different pages2for (i = 0; i < n; i++) {3 sum += data[i * ELEMENTS_PER_PAGE];4}5 6// per access: 1 new page -> TLB miss -> page-table walk7// data touched is tiny; pages touched is n1// same total elements, contiguous2for (i = 0; i < n; i++) {3 sum += data[i];4}5 6// per page: 1 TLB miss, then many hits7// data touched is identical; pages touched is n / ELEMENTS_PER_PAGEIdentical element count, identical bytes read, identical arithmetic. The only difference is how many distinct pages are in play, and therefore how many page-table walks the CPU has to perform. A profiler attributing time to the load instruction will look the same in both cases; only the TLB counters separate them.
What the counters look like when it is translation
The diagnostic value here is that the signature is specific. Translation-bound workloads show high TLB miss rates *with* unremarkable data-cache miss rates — a combination that nothing else produces. If both are high you have an ordinary memory-bound problem; if only the cache is missing, translation is not your issue.
The reason it is easy to misdiagnose is that a coarse profile lumps everything into "memory stall" and a function-level profile points at the load instruction, which is true and useless. You need the counter split to tell the two apart, and if you only ever look at cache misses you will conclude the memory system is fine and go looking somewhere unproductive.
The table below is the disambiguation. Reading it correctly is the skill; the underlying mechanism is The Page-Table Walk: Dependent Loads All the Way Down, and the broader diagnostic framing lives in Busy Is Not the Same as Working.
| Cache miss rate | TLB miss rate | What it means | Where to go next |
|---|---|---|---|
| Low | Low | Not memory-bound at all; look at dependencies or execution | IPC: Instructions Per Cycle, Dependency Graphs: The Real Shape of Your Code |
| High | Low | Ordinary memory-bound: too much data, poor locality | Cache Thrashing: Load, Evict, Reload, Repeat, Working Set: Why Performance Falls Off a Cliff |
| Low | High | Translation-bound: small data, many pages | Huge Pages: More Coverage per Entry, and What It Costs, denser layout |
| High | High | Sparse access punishing both structures at once | Pointer Chasing: The Address You Do Not Have Yet, Data-Oriented Design, Without the Dogma |
What actually fixes it
There are exactly two levers, and they are independent. Reduce the number of pages the working set spans, or increase how much each translation covers. The first is a layout change; the second is Huge Pages: More Coverage per Entry, and What It Costs.
Reducing page count is usually the better first move because it helps the data cache too. Packing structures more densely, replacing pointer-linked nodes with contiguous arrays, and blocking a traversal so it finishes with one region before moving on all reduce page count and improve locality simultaneously.
Huge pages are the blunter instrument and the more situational one. They cost memory when the mapping is sparse, they can cause allocation stalls when memory is fragmented, and transparent implementations sometimes hurt. Reach for them when you have measured that coverage is the constraint — not because a workload feels memory-heavy.
- Densify the layout — fewer, larger, contiguous allocations. Helps translation and caching together.
- Block the traversal — finish with one region before starting the next, so pages are reused while still resident.
- Replace pointer chains with arrays where the access pattern allows; see Both Are O(n). One Is Far Slower..
- Then consider huge pages, having first confirmed with counters that coverage is genuinely the limit.
- Re-measure after each change independently — these levers interact, and changing two at once tells you nothing about either.
Key points
- Translation has its own working set, measured in pages, independent of the data working set measured in bytes.
- The signature is specific: high TLB miss rate with an unremarkable cache miss rate, which nothing else produces.
- A large stride is the classic cause — every access lands on a fresh page, and prefetching cannot help translation.
- The two fixes are independent: reduce pages spanned, or increase coverage per entry with larger pages.
- Densifying layout is usually the better first move because it improves cache behaviour at the same time.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Loop → access: a strided or scattered access lands on a page not recently used.
- 2Access → TLB: no matching entry exists, so the translation cannot be supplied from cache.
- 3TLB → walker: the page-table walk begins, a chain of dependent loads the prefetcher cannot anticipate.
- 4Walker → TLB fill: the new translation evicts an existing entry, which will itself be needed again shortly if the pattern is cyclic.
- 5Next iteration → repeat: because the pattern never reuses a page before eviction, every access pays the full cost.
- • Concluding the memory system is fine because cache miss rates are low — that check does not cover translation at all.
- • Attributing the stall to the load instruction a profiler highlights, which is true of every memory stall and distinguishes nothing.
- • Assuming a small dataset cannot be memory-bound. Footprint in bytes says nothing about footprint in pages.
- • Reaching for huge pages as a general performance measure. If coverage was not the constraint they cost memory and change nothing.
Consequences, controls and cost
- • A dataset that fits in L2 can run at DRAM-like speed because translation, not data, is the constraint.
- • Function-level profiles point at the load instruction and offer no way to distinguish this from ordinary cache pressure.
- • Increasing the data cache size, or shrinking the dataset, produces no improvement at all — which is often the clue.
- • Random access patterns punish translation and caching simultaneously, so the two costs compound rather than alternate.
- • The same code can be translation-bound on one machine and not on another, because coverage varies enormously.
- • Count distinct pages touched per iteration first; if it is small relative to plausible coverage, stop — this is not your problem.
- • Densify the layout: contiguous allocations, packed structures, arrays instead of pointer chains.
- • Block the traversal so a region is finished before the next begins, keeping translations resident while they are still useful.
- • Enable huge pages once counters confirm coverage is the constraint, and measure the delta rather than assuming it.
- • Re-measure each change on its own; the levers interact and a combined change attributes nothing.
- • Read `dTLB-load-misses` alongside `L1-dcache-load-misses` and compare the *pair* — the combination is the diagnosis, not either number.
- • Prefer walk-cycle counters where the machine exposes them; they report cost, whereas miss counts report only frequency.
- • Derive distinct pages per iteration analytically from the stride and page size, and sanity-check it against the measured miss rate.
- • A/B with transparent huge pages: a large improvement confirms translation was the constraint, a negligible one rules it out cleanly.
- • [[counters]] covers reading these events without drawing conclusions from a single number.
- • Densifying layout costs flexibility — contiguous structures are harder to grow, insert into and share than pointer-linked ones.
- • Blocking a traversal complicates otherwise simple loops and can obscure the algorithm for a benefit that varies by machine.
- • Huge pages trade memory footprint and allocation predictability for coverage, and can regress workloads that never needed them.
Scope
§224 — what these claims are specific to.
- MICROARCH-SPECIFICWhether a given working set overflows coverage depends on TLB size and page size, both of which vary by machine. The same binary can be translation-bound on one host and not on another.
- SIMULATEDThe stall-cost scale is modelled to show how cost falls as page reuse improves. It is not measured, and absolute values are meaningless — only the shape transfers.