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.
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 memory whose translations can be resident at once, and it is not the number anybody quotes. Exceeding it does not by itself mean missing: what decides that is how many different pages have to stay translated between one use and the next, which is why the loop above keeps missing at sixty-five pages and stops missing after one pass at sixty-four.
| 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 has to walk the table whenever more than that must stay translated between uses |
| 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 | stated | real buffers are often 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 | stated | 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 changes the numbers here, and none of them is modelled, so the clean collapse on this page belongs to the fully associative model.
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 now has a readable author-hosted copy. The passage read for this page describes an associative memory retaining the most recently used page-table entries. The ACM Digital Library route still returned a sign-in page; that was a failure of that route, not evidence that the paper could not be read. This is a check of that passage, not a revalidation of the whole survey. The Atlas citation's bibliographic details were checked against Crossref; that metadata check does not establish its mechanism claims.
Sources
- Tom Kilburn, David B. G. Edwards, Michael J. Lanigan and Frank H. Sumner, One-Level Storage System, IRE Transactions on Electronic Computers EC-11(2):223-235, April 1962.
- Peter J. Denning, Virtual Memory, ACM Computing Surveys 2(3):153-189, September 1970.
- Peter J. Denning, Virtual Memory, 1970, author-hosted PDF. Readable copy of the survey cited above; its mapping-table discussion describes associative registers for recently used page translations.
- Logical Art, the studio this belongs to.