The TLB
A program's addresses are not the machine's. Each one is translated through a table that lives in memory like everything else, so reading a word can mean reading five. A small store of recent translations makes almost every access cost one again. This page is about what it costs when it does not, and about how little memory that store actually covers.
New to virtual memory? Start here
A program's addresses are not the machine's addresses. Each one has to be translated, and the table doing the translating lives in memory like everything else, so the translation is itself a memory access. On x86-64 the table usually has four levels, so reading one word can mean five reads. The depth is not universal: it varies by architecture and by how much address space the system is configured for.
That would be intolerable, so the recent translations are kept in a small dedicated store searched all at once. Almost every access hits it and costs one read. This page is about what happens when they do not, and about how much memory that little store can actually cover, which is far less than its size suggests.
Fast and forgetful, or slow and permanent
Memory is quick and loses everything when the power goes. A disk keeps what it was given and is slower by a factor with several zeroes in it. No single part is both, and no amount of engineering has made one.
So nearly every design in this topic is buying one with the other. Keep it in the fast part and you are quick until the lights go out. Write it to the slow part first and you are safe but waiting. The machines here are the arrangements people found in between, and each of them is honest about which half it gave up.
The machine for this idea on its own is Write-Ahead Log, if you would rather press it than read about it.
Every address has to be translated first
1 What one memory access costs when the translation has to be fetched first
What one memory access costs, by how many levels the page table has. Held means the buffer had the translation; missing means it did not, and the table has to be walked before the data can be fetched.
| levels | held | missing |
|---|
2 A loop the buffer can hold, and the same loop one page larger
A loop that walks a working set in order, ten times over. Move the working set across the buffer's capacity and watch what happens at the boundary. Both replacement policies see the identical access sequence.
| policy | hit rate | reads each |
|---|
3 How far a buffer actually reaches, and what a bigger page does to it
How far the buffer reaches: entries multiplied by page size. This is the number that decides whether a program misses, and it is not the number anybody quotes.
| page size | memory covered | against 4 KiB |
|---|
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| with a four-level page table, one missed translation costs five memory accesses | yes | a single access to a cold buffer took 5 reads: 4 to walk the table and 1 for the data itself |
| and the second access to the same page costs one | yes | two accesses to one page cost 6 reads in total, so the translation was found the second time |
| a loop over exactly as many pages as it holds hits every time after the first pass | yes | 64 pages, 10 passes: 64 misses, all in the first pass, then 576 hits |
| one more page than it holds, and least-recently-used never hits once | yes | 65 pages over 10 passes: 0 hits out of 650. Each page is evicted exactly before it is needed again, because scanning in order is the worst thing you can do to least-recently-used |
| replacing at random does not collapse on the same access pattern | yes | the identical loop with random replacement gets 570 hits, a rate of 87.7%; here the cleverer policy is the worse one |
| sixty-four entries of 4 KiB pages reach a quarter of a megabyte, and no further | yes | 64 x 4 KiB = 256 KiB of memory that can be reached without walking the table; a program touching more than that is missing, whatever its access pattern looks like |
| the same buffer with 2 MiB pages reaches 512 times as far, and this is why huge pages exist | yes | 128 MiB against 256 KiB, from the same 64 entries; nothing about the hardware changed except what one entry stands for |
| hits, misses and memory accesses account for each other exactly | yes | 1295 hits and 3705 misses over 5000 accesses come to 19820 memory reads, which is 3.96 per access |
| nothing here is timed, and the buffer is fully associative | yes | real buffers are set-associative, split by page size, often two-level, and their timings depend on hardware a browser cannot measure; accesses are counted instead, and the counting is what carries the argument |
| the mechanism is Atlas in 1962, and the name is not Atlas's | yes | Kilburn, Edwards, Lanigan and Sumner describe an associative store of page address registers searched in parallel; the phrase translation lookaside buffer came later and this page does not claim to know who coined it |
What is real here, and what is not
Nothing here is timed
A missed translation costs a walk whose real price depends on whether those table entries are themselves cached, on the memory controller, and on what else the machine is doing. None of that is measurable from a browser. Memory accesses are counted instead, and the counting is what carries the argument: five accesses instead of one is a fact about the structure, not about a particular chip.
The buffer here is fully associative and real ones usually are not
This model searches every entry, so a page can live anywhere. Real hardware is often set-associative, split into separate stores for different page sizes, and increasingly arranged in two levels with a small fast one in front of a larger slower one. Each of those makes the behaviour worse than modelled here in ways that do not change the direction of any claim on this page.
The collapse is a property of the access pattern, not a law about buffers
Walking a working set in order, repeatedly, is the worst possible input for least-recently-used replacement, and that is why the hit rate goes to zero rather than declining. A different pattern does not do this. The point is not that least-recently-used is bad; it is that a policy which looks obviously correct has an ordinary input it handles worse than choosing at random.
Real replacement policies are not either of these two
Hardware rarely implements true least-recently-used, because tracking exact recency across many entries is expensive. Approximations are used instead, and they do not collapse in quite this way. The two policies here are the clean cases that show the effect; treat them as the ends of a range rather than as what a processor does.
The mechanism is 1962 and the name is not
Kilburn, Edwards, Lanigan and Sumner describe Atlas holding its page translations in an associative store searched in parallel, which is this machine. They do not call it a translation lookaside buffer. That phrase came into use later and this page does not claim to know who coined it, because saying so without a source would be exactly the kind of tidy story this site tries not to repeat.
Which of these sources were actually read
Denning's 1970 survey is cited for the virtual-memory context and was not read here: the ACM Digital Library answers with its sign-in page. The Atlas paper is the one this machine rests on, and its details are checked against Crossref. Where a citation was not retrieved, this site says so rather than letting it sit beside one that was.