The TLB: A Cache for Addresses, Not Data
The translation lookaside buffer holds recently used virtual-to-physical mappings so the common case skips the walk entirely. It is small, it is split by purpose, and its capacity is measured in pages — which makes its working set a completely different quantity from your data cache's.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
The same idea as a data cache, applied to addresses
A TLB is a cache with all the usual properties: limited entries, an associativity, a replacement decision, and hits that are cheap and misses that are not. What is unusual is what it caches — not data, but the *mapping from a virtual page to a physical frame*, plus the permission bits that came with it.
Because translation is on the critical path of every access, the TLB has to be fast enough to answer within the time budget of a cache lookup. That forces it to be small. It holds a number of entries that would look absurd for a data cache, and it succeeds anyway because programs concentrate their accesses in a handful of pages at a time.
The consequence is worth stating plainly, because it is the crux of the module: the TLB's working set is counted in pages, the data cache's in bytes. A loop striding through a large array with a big step touches few bytes and many pages, and will thrash the TLB while barely troubling the data cache. This is exactly the situation When Translation Itself Is the Bottleneck is about.
| Property | Data cache | TLB |
|---|---|---|
| What it holds | Cache lines of data | Virtual page → physical frame mappings |
| Unit of capacity | Bytes | Pages — so far more address space per entry |
| Working set measured in | Bytes actually touched | Distinct pages actually touched |
| A miss costs | A fetch from the next level | A page-table walk, itself several dependent loads |
| Helped by | Spatial and temporal locality of data | Locality of *pages*, and larger page sizes |
| Typical failure mode | Streaming a dataset larger than the cache | Sparse access across many pages |
Split, layered and tagged
Real designs do not have one TLB. Instruction fetch and data access have separate ones, for the same reason instruction and data caches are separate: their access patterns are unrelated and they compete badly when combined. Many designs then layer them, with a very small fast first level backed by a larger second level, precisely mirroring the data-cache hierarchy.
There is usually further structure by page size, because an entry mapping a huge page and an entry mapping a small page cover different amounts of address space and often live in different arrays. This is part of why enabling huge pages can change TLB behaviour so sharply — it moves entries into a different, differently-sized structure.
Entries are also commonly tagged with an address-space identifier so translations belonging to different processes can coexist. Without that, every context switch would have to discard the whole TLB, and the cost of switching would be dominated by rebuilding translations. With it, a process returning to a core may still find its translations present — which connects directly to Cache Warmth and the Real Cost of Migration and Thread Affinity: Pinning and Its Price.
| Structure | Why it exists | What it means for software |
|---|---|---|
| Separate instruction and data TLBs | Uncorrelated access patterns competing for entries | Large hot code and large hot data do not evict each other |
| Multiple levels | A fast small level cannot also be large | A second-level hit is cheaper than a walk but not free |
| Per-page-size arrays | Entries cover different address ranges | Huge pages may draw from a different, smaller pool |
| Address-space tags | Avoid flushing everything on a context switch | Returning to the same core can retain translations |
Coverage is the number that matters
The useful way to think about a TLB is not "how many entries" but how much address space those entries can cover at once — entries multiplied by page size. That single quantity tells you whether a given working set can be translated without constant walking.
This framing makes the huge-page argument obvious rather than magical. Increasing page size multiplies coverage by the same factor without adding a single entry. A working set that overflowed coverage by a large margin with small pages can fit comfortably with large ones, and the TLB miss rate collapses — while the *data* cache behaviour is entirely unchanged.
It also gives you the diagnostic question to ask, which is a page-counting question rather than a byte-counting one: how many distinct pages does the hot loop touch per iteration? If that number is comfortably below coverage, translation is not your problem and you should stop looking. If it is far above, translation may well be the whole problem, and Huge Pages: More Coverage per Entry, and What It Costs is the lever.
Key points
- The TLB is a cache of address translations, consulted on every access before the data access can proceed.
- Its working set is counted in pages, not bytes — a completely different quantity from the data cache's.
- Real designs split instruction from data, layer by level, and often separate entries by page size.
- Address-space tags let translations survive a context switch, which is part of why core affinity matters.
- Coverage — entries times page size — is the number that predicts whether translation will be a problem.
Progressive depth
Overview
The TLB remembers recent address translations so the CPU does not have to look them up in memory every time. A hit is nearly free; a miss means walking the page tables.
Practical
Its capacity is in pages, not bytes, so the question to ask is how many distinct pages your hot loop touches — not how much data. A small dataset spread across thousands of pages will thrash the TLB while sitting comfortably in L2.
Advanced
Real designs split instruction from data, layer levels, partition by page size and tag entries with an address-space identifier. Coverage — entries times page size — is the quantity that predicts behaviour, and it is why huge pages can transform a translation-bound workload without touching data-cache behaviour at all.
Internals
TLB lookup overlaps the L1 set lookup using untranslated offset bits, which constrains L1 geometry. Invalidation is a cross-core problem: changing a mapping requires the initiating core to tell every other core that might hold a stale entry, an operation usually implemented with inter-processor interrupts. That shootdown cost is why frequent permission changes on shared memory scale badly with core count.
TLB Reach
Change an input and watch which number moves — and which one refuses to.
Only 3% of the working set can be mapped at once, so accesses outside that window trigger page-table walks — several dependent memory accesses each. Note this can happen while the data itself sits comfortably in cache, which is why the symptom is so often misread as a cache problem. Raise the page size and watch reach grow without adding a single entry.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Address generation → TLB: the virtual page number is presented, in parallel with the L1 set lookup using the untranslated offset.
- 2TLB → tag compare: entries in the selected set are checked for a matching page number and a compatible address-space tag.
- 3TLB → hit: the frame number and permission bits are returned, and the physical tag comparison in L1 can complete.
- 4TLB → miss: the walker is invoked (The Page-Table Walk: Dependent Loads All the Way Down) and the resulting translation is installed, evicting an existing entry.
- 5Context switch → TLB: untagged entries are discarded; tagged entries may survive, so returning to the same core can avoid re-walking.
- • Reasoning about TLB pressure in bytes. Coverage is entries times page size, and a small dataset spread thinly can overflow it easily.
- • Assuming a TLB is flushed entirely on every context switch. Address-space tags mean it often is not, which changes the cost of switching substantially.
- • Treating instruction-side and data-side pressure as one budget when the structures are separate.
- • Concluding that huge pages must help because they helped elsewhere. If coverage was never the constraint, they change nothing and can cost memory.
Consequences, controls and cost
- • A program with a small data footprint can still miss constantly in the TLB if that data is spread across many pages.
- • Enabling huge pages can transform a translation-bound workload while leaving data-cache behaviour completely unchanged.
- • Migrating a thread to another core loses its translations along with its cache lines ([[cache-warmth]]).
- • Large hot code and large hot data do not compete for translation entries, because the structures are separate.
- • Sparse random access punishes translation and data caching simultaneously, so the two costs compound.
- • Count the distinct pages your hot loop touches per iteration; that number, against coverage, predicts translation cost better than anything else.
- • Cluster hot data so the same pages are reused, rather than spreading it thinly across a large region.
- • Use huge pages when coverage is genuinely the constraint, accepting the allocation and fragmentation costs.
- • Pin latency-sensitive threads to cores so tagged translations and warm caches survive between scheduling slices.
- • Otherwise: almost nothing. There is no instruction to control the TLB from user code — only ways to give it a smaller job.
- • Read `dTLB-load-misses` and `iTLB-load-misses` separately — conflating them hides which side is under pressure.
- • Where available, read walk-active cycle counters rather than miss counts; cycles attribute cost, counts only attribute frequency.
- • Compute distinct pages touched per iteration from the access pattern and compare it against a plausible coverage figure before assuming anything.
- • A/B the workload with transparent huge pages enabled and disabled — a large swing in TLB counters is direct evidence, a small one closes the question.
- • A small fast TLB keeps translation off the critical path but limits coverage, so large working sets suffer disproportionately.
- • Address-space tags avoid flushes at the cost of entries being shared between processes, so coverage per process falls under heavy multiprogramming.
- • Splitting by page size lets each entry be simple, but means a workload mixing page sizes cannot pool the entries.
Scope
§224 — what these claims are specific to.
- MICROARCH-SPECIFICEntry counts, levels, associativity and page-size partitioning differ between vendors and generations, and are frequently undocumented. Do not port a number measured on one machine to another.
- SIMPLIFIEDThe coverage table treats entries as uniform and ignores that huge-page entries often come from a separate, smaller pool. The ratio argument holds; the absolute reach is optimistic.