Answers · How a program runs

How does the CPU avoid walking the page table on every single memory access?

In shortA small cache of recent translations, called the TLB, is checked on every memory access; a hit skips the page-table walk, and a miss walks once then stores the result.

A small cache of recent virtual-to-physical translations, usually called the TLB, sits in front of the page table and is checked on every memory access. A hit supplies the physical address immediately, so the page table is not walked at all; only a miss triggers a walk, and the result of that walk is stored for next time.

The TLB is not a replacement for the page table. It is a record of answers already found: virtual page number to physical frame number, plus permission bits. Hardware looks there first. On a hit the physical address is formed and the data cache lookup proceeds; the page table is never consulted. On a miss hardware either walks the table in hardware or traps to software, depending on the architecture, and then writes the translation into the TLB. The next access to the same page, or to another page in the same large block, hits.

The bill for a walk

The page table is itself ordinary memory, so an uncached translation is not a free indirection. On a common 64-bit machine the map is four levels deep. If each level must be read from main memory at about 80 ns, a walk costs four reads before the data read can begin. Then the data read itself costs 80 ns, so the total is 320 + 80 = 400 ns. That is 400 / 80 = 5 times the cost of a bare memory read, which would make every load run at one fifth of the speed of a machine with no translation at all.

4 \times 80\,\mathrm{ns} + 80\,\mathrm{ns} = 400\,\mathrm{ns} = 5 \times 80\,\mathrm{ns}

Nothing about that arithmetic is wrong. It is simply the price of the rare case. The TLB is consulted on every access, including instruction fetches, which forces it to be tiny: it must answer in a fraction of a cycle. Typical fastest levels hold on the order of 64 entries, and a second, slightly slower level holds 1,536 entries. A data cache can hold tens of megabytes. The translation cache is therefore one of the smallest structures in the machine, and its smallness is exactly why its coverage is limited.

FIG 1Covered memory

: the amount of memory whose translations can be held at once
: the number of entries in the translation cache
: the block size, four kilobytes by default

One multiplication gives the working set that can be translated without a miss; it has nothing to do with installed RAM.

Put real entry counts into $r = n s$ . With 64 entries and 4 KB blocks, $r = 64 \times 4\,\mathrm{KB} = 256\,\mathrm{KB}$ . With 1,536 entries and the same 4 KB blocks, $r = 1,536 \times 4\,\mathrm{KB} = 6,144\,\mathrm{KB} = 6\,\mathrm{MB}$ . That is the whole coverage of the second-level translation cache on a default configuration. A service touching hundreds of megabytes is far past it. The same 1,536 entries with 2 MB blocks give $r = 1,536 \times 2\,\mathrm{MB} = 3,072\,\mathrm{MB} = 3\,\mathrm{GB}$ . A configuration with 32 entries and 1 GB blocks gives $r = 32 \times 1\,\mathrm{GB} = 32\,\mathrm{GB}$ . The entry count did not move; only the size of the block each entry describes did.

What the free-looking picture misses

The natural guess is that the CPU checks the page table the way it checks a register, as a fixed step that can be ignored. It cannot. Page table entries live in memory, and the lower levels of the table are themselves addressed through the upper levels, so a cold walk is a chain of dependent memory reads. A TLB miss is not a page fault either: the page can be present and valid, and the only missing thing is the cached translation. The shortcut is not an optimisation bolted onto a working scheme; without it the scheme would cost several memory reads per access, and the machine would be too slow to use this way.

The step, not the slope

Coverage produces a cliff rather than a gentle decline. While the working set fits inside $r$ , entries stay resident across passes and translation is effectively free. Once the working set passes $r$ , entries are evicted before they are reused, each pass re-walks, and time per element jumps. The cost then flattens again: growing from just past the cliff to far past it does not make each miss much more expensive, because the miss was already the expensive event. This is why two benchmarks, one at 2 MB and one at 8 MB, can both look reasonable while the interesting change happened between them.

Larger blocks are the only response that needs no source change. A block is allocated whole whether it is used or not, so large blocks waste memory, and some systems require them to be reserved at boot. For a database buffer pool or one enormous allocation they are close to free money. They do not rescue a program that jumps randomly around a working set larger than the covered amount. Sequential access does better because one translation serves a whole block and thousands of following accesses are free; touching less memory is the real fix when the working set cannot fit.

Worth keeping

A TLB hit costs no page-table memory reads; a miss costs up to four on a four-level 64-bit page table.
A translation cache covers entries times block size, so 1,536 entries with 4 KB blocks cover 6 MB, while the same entries with 2 MB blocks cover 3 GB.
Performance is flat while the working set fits the covered memory and steps down once it does not, so benchmarks just inside and just outside the cliff can look wildly different.

Where this goes next

This question is one step of Memory, All the Way Down, a course that works through its subject from the beginning. The page that teaches this part of it is What Translation Costs, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course