The TLB

The last page ended on a threat: translating an address can cost a four-access page-table walk, and it happens on every load and store. If we truly paid that each time, virtual memory would make every program several times slower and the idea would have been abandoned decades ago. It wasn't — because of one small, brilliant cache. The Translation Lookaside Buffer (TLB) is a cache of recent translations: VPN → PPN, ready in a single cycle. It is the reason virtual memory is essentially free.

A cache — of translations

Everything you learned about caches applies. The TLB is a small (often 64–1536 entry), usually highly- or fully-associative cache. Its "block" is a single page's translation. You look up a VPN; a TLB hit returns the PPN in about a cycle, and translation is done. A TLB miss triggers the page-table walk — which then fills the TLB with the translation it found, so the next access to that page hits. Locality does the rest: because programs touch the same pages over and over (temporal) and nearby pages (spatial), a tiny TLB captures the overwhelming majority of translations.

TLB hit — translation found in the TLB, ~1 cycle. The common case (often >99%).
TLB miss, page-table hit — walk the page table (a few memory accesses, mostly served by the data caches), fill the TLB, retry. Tens of cycles.
Page fault — the walk finds the page not present in RAM; trap to the OS to fetch it from disk. Millions of cycles.

On modern chips the walk is done by a hardware page-table walker — a dedicated state machine — so a TLB miss doesn't even interrupt the OS; software only gets involved on an actual page fault.

TLB reach: how much memory the TLB covers

A crucial figure of merit is TLB reach — the total memory the TLB can map without a miss:

\text{TLB reach} = (\text{TLB entries}) \times (\text{page size}).

A 64-entry TLB with 4 KB pages reaches only 64 \times 4\ \text{KB} = 256\ \text{KB} — smaller than an L2 cache! A program striding through a 100 MB array will miss the TLB on nearly every new page even while the data itself hits in cache. This is why big-data and HPC workloads lean on huge pages (2 MB or 1 GB instead of 4 KB): a single huge-page entry multiplies reach by 512× or more, so a handful of entries can map gigabytes.

// TLB reach = entries × page size. Watch huge pages transform it. function reachMB(entries: number, pageKB: number): number { return (entries * pageKB) / 1024; // MB } const entries = 64; console.log(`4 KB pages: reach = ${reachMB(entries, 4).toFixed(2)} MB`); console.log(`2 MB pages: reach = ${reachMB(entries, 2048).toFixed(0)} MB`); console.log(`1 GB pages: reach = ${reachMB(entries, 1024 * 1024).toFixed(0)} MB`);

The VIPT trick: translate and look up at once

Now the elegant part. A first-level cache faces a chicken-and-egg problem: should it be indexed by virtual or physical addresses? Virtual is fast (no translation first) but causes aliasing headaches; physical is clean but seems to force you to wait for the TLB before you can even start the cache lookup — serialising two slow steps. The resolution is VIPT — virtually indexed, physically tagged.

The key insight from the last page: the page offset bits are not translated, so they are known immediately. If the cache's index and block offset fit entirely within those untranslated page-offset bits, the L1 can start indexing on them right now — reading out the candidate tags — while the TLB translates the VPN in parallel. When the TLB delivers the physical page number a moment later, its physical tag is compared against the tags the cache already fetched. Translation and cache access overlap completely; the TLB latency vanishes into the shadow of the cache read.

There is a price: the trick only works if \text{index bits} + \text{offset bits} \le \log_2(\text{page size}), i.e. the number of sets × block size must not exceed the page size. That caps a VIPT cache at (\text{page size}) \times (\text{associativity}). It is exactly why L1 caches are stuck near 32–48 KB and grow via associativity (8-way) rather than more sets: raising associativity enlarges the cache without adding index bits, keeping the VIPT constraint satisfied.

// Largest VIPT L1 that still overlaps with translation: page_size × associativity. function maxViptKB(pageKB: number, ways: number): number { return pageKB * ways; // sets × blockSize ≤ pageSize => capacity ≤ pageSize × ways } const pageKB = 4; for (const ways of [1, 2, 4, 8, 16]) { console.log(`${ways}-way, 4 KB pages -> max VIPT L1 = ${maxViptKB(pageKB, ways)} KB`); } console.log("This is why real L1s are ~32-48 KB and go WIDER (more ways), not more sets.");

Naively, yes: process B's virtual addresses mean different physical pages than process A's, so switching processes would require flushing the whole TLB — and then B stalls through a storm of cold TLB misses rebuilding it. That flush cost made context switches painful for years. The fix is address-space identifiers (ASIDs), sometimes called PCIDs on x86: each TLB entry is tagged with the ID of the process it belongs to, so entries from A and B coexist and only the matching process's translations hit. Now a context switch just changes the current ASID — no flush, and when you switch back to A its translations are often still warm. A few tag bits per entry buy back the whole flush.

They are easy to conflate because both are "misses", but they concern different things. A cache miss means the data isn't in the cache. A TLB miss means the translation isn't in the TLB — the data might be sitting right there in L1, but you can't form its physical address to find it. All four combinations occur: TLB-hit + cache-hit (ideal), TLB-hit + cache-miss, TLB-miss + cache-hit (translate first, then the data's already there), and TLB-miss + cache-miss. And a page fault is a third, far rarer beast still — the page isn't in physical memory at all. Keep the three levels — translation, cache, physical presence — separate in your head.

Down to the metal

The TLB is the last piece that keeps the fast path fast. Everything above it — caches, translation — has assumed a "main memory" that eventually answers. What that memory actually is, and why its latency has barely improved in twenty years, is the floor of the whole hierarchy: DRAM and its memory controller.