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

Making Translation Fast: The TLB

Paging gives every program its own private address space, but it hides a nasty cost: every single memory reference now needs a page-table lookup first. This guide meets the TLB — a tiny, blazing cache of recent translations that turns that lookup into a sub-cycle answer most of the time — and shows honestly how it teams up with caches and what happens on the rare miss.

The hidden tax paging just charged us

The previous guides bought us something wonderful: with paging, every program believes it owns a clean, contiguous address space, and a page table quietly maps each virtual page to wherever it really sits in physical memory. But look closely at the bill. Every time the CPU touches memory — every load, every store, every instruction fetch — it must first turn a virtual address into a physical address, and that translation means reading the page table, which itself lives in memory. So a single 'load this word' has secretly become 'first go to memory to find out where in memory the word is, then go get the word.' We have doubled (or worse) the memory traffic.

It gets worse with multilevel page tables, which the last guide introduced to keep the table itself from being absurdly large. A two-level table needs two memory accesses just to translate; a four-level table — the norm on 64-bit machines — needs four memory accesses before you can even start fetching the data you actually wanted. If every translation really cost four trips to slow main memory, virtual memory would be a performance disaster. Something has to make the common case fast.

The TLB: a tiny notebook of recent answers

The fix is the same trick caches already taught us, applied to translations instead of data. The TLB — the translation lookaside buffer — is a very small, very fast hardware cache that remembers the most recently used page-table answers: 'virtual page 0x1F maps to physical frame 0x83.' It usually holds only a few dozen to a few hundred entries, because it has to answer in a fraction of a clock cycle, in parallel with the rest of the pipeline. When the CPU needs a translation, it asks the TLB first; if the answer is there (a TLB hit), the physical address pops out almost for free and the page table is never touched at all.

Why does such a tiny notebook work so well? The same locality that makes data caches pay off. A program running a loop keeps touching the same handful of pages over and over — its code page, its stack page, the array it is grinding through. Those translations sit in the TLB and get reused thousands of times. In practice a well-behaved program hits in the TLB more than 99 percent of the time, so the four-memory-access page walk almost never actually happens. The expensive lookup is real; it just rarely runs.

Walking a hit, then a miss

Let us trace a single load. The CPU computes a virtual address — say the high bits are virtual page 0x1F and the low bits are an offset of 0x0C4 within that page. Notice the offset never needs translating: pages are whole tiles, so the byte's position inside its page is identical in the virtual and physical worlds. Only the page number has to be looked up. Here is the happy path, the TLB hit, then the sad path, the TLB miss.

  1. Split the virtual address: virtual page number (0x1F) and page offset (0x0C4). The offset is carried through untouched.
  2. Ask the TLB for page 0x1F. On a hit it instantly returns the physical frame number (0x83) plus the page's protection bits.
  3. Glue frame 0x83 to offset 0x0C4 to form the physical address, and use it to read the data cache. Done in roughly one cycle.
  4. On a TLB miss, instead walk the page table in memory (one access per level), find the mapping, and load it into the TLB — then retry the access, now a hit.

Who does that page walk on a miss? On most modern chips a dedicated piece of hardware called the page-table walker (part of the MMU) does it automatically, costing a handful of memory accesses but no software involvement. On some designs the hardware instead raises a fault and the operating system walks the table in software — slower per miss, but more flexible. Either way, a miss is dozens to hundreds of cycles, versus essentially zero for a hit, which is exactly why keeping the TLB hit rate high matters so much.

How the TLB and the cache dance together

There is a subtle timing puzzle. The TLB turns a virtual address into a physical one, but the data cache is usually indexed by the physical address (so two programs' identical virtual addresses do not collide). Naively that means: translate first, then look up the cache — two slow steps in a row. A clever and very common arrangement, the virtually-indexed, physically-tagged (VIPT) cache, dodges this by noticing that the page offset bits are not translated. The cache can start its lookup using those untranslated offset bits at the same instant the TLB is translating the page number, so the two run in parallel and the physical tag comparison just confirms the result a moment later.

virtual address (page number | page offset)
   [ 0x1F ......... | 0x0C4 ]
        |                 |
        |                 +--> drives cache index NOW (not translated)
        v                 |
  +-----------+           v
  |   TLB     |--hit--> frame 0x83 --> physical tag, compared to cache tag
  +-----------+
        |  (miss)
        v
  page-table walk in memory --> fill TLB --> retry
The untranslated offset lets the cache lookup and the TLB translation overlap (VIPT); a TLB miss falls back to walking the page table.

One more honest wrinkle: the TLB caches mappings that belong to a particular process. When the OS switches from one program to another, those entries may now be wrong. Old machines simply flushed the whole TLB on every context switch (a real cost — the new program starts cold and suffers a burst of misses). Modern designs tag each entry with an address-space identifier so entries from different processes can coexist, avoiding most of those flushes. Either way, this is why virtual memory is fundamentally a hardware/OS co-design: the OS owns the page tables, the hardware owns the TLB, and they must agree about what is true.

Honest limits: when translation dominates

The TLB is small, so it is easy to overflow if your program's working set of pages is large or scattered. A loop striding through a huge array with a big gap between accesses can touch a new page almost every iteration, blowing past the TLB's few hundred entries and turning nearly every access into a miss. The arithmetic stays identical — the program computes the same answer — but it can run several times slower purely because of TLB misses. This is the translation-layer cousin of cache-hostile code, and it is invisible unless you measure it.

Hardware fights back with bigger TLBs, a second-level TLB behind the first (just as caches have L1 and L2), and huge pages — letting one entry cover, say, 2 MB or 1 GB instead of 4 KB, so a single TLB slot maps a vastly larger region. None of this makes a TLB miss cost nothing; it just makes misses rarer. The honest takeaway is that virtual memory's beautiful illusion is not free: most of the time it costs almost nothing thanks to the TLB, but in the worst case a page fault going to disk or a storm of TLB misses can dominate your run time, exactly as the rung's framing warned.