The TLB, Associativity, and What a Miss Actually Costs

The page-table walk is correct and unusable as a per-access mechanism. A processor executing a load every few cycles cannot afford four dependent memory reads to translate one address, so hardware keeps a cache of recent translations. The cache is small, holds a few dozen to a few thousand entries depending on the design, and its behaviour explains a large fraction of the performance difference between two programs that touch the same amount of memory.

An Entry Covers a Page, Not a Byte

A translation cache entry holds the page-number half of a virtual address and the corresponding frame number plus the permission bits that applied when the entry was filled. The split that produces that page number is fixed by the page size and leaves the offset bits untouched, as described in splitting an address into page number and offset. An entry therefore covers 4096 bytes of address space, or 2 MiB if it describes a large page. An entry for a large page does the work of 512 ordinary entries, which is the entire reason large pages matter.

The number of entries is the number of distinct pages that can be translated without a walk. With a few hundred entries for ordinary pages, a program’s translation reach is on the order of a megabyte or two. With large pages, the same entries cover hundreds of megabytes. This arithmetic, rather than any property of the cache itself, is what drives the interest in superpages for databases, virtual machines, and anything else with a footprint measured in gigabytes.

Why It Is Small and Associative

A translation cache sits in the critical path of every access, so it must answer in the same cycle the access is issued. That rules out a large structure. It also rules out a structure that indexes by virtual address bits the way a data cache does, because the index bits would come from the page number, and two processes with the same virtual page number must be able to hold different translations simultaneously.

The usual solution is a fully associative or highly associative array searched in parallel by comparators. Every entry compares its stored tag against the incoming page number in one cycle, and any match drives the frame number onto the address bus. Fully associative designs avoid conflict misses entirely: an entry is evicted only when the array is full and a policy selects a victim, not because two pages happened to collide. The cost is that the comparators and the tag array consume area and power proportional to the entry count, which is why the count stays in the hundreds rather than the thousands.

Some designs split the structure by function. Instruction translations and data translations are looked up separately, which doubles the effective reach for code that loops over instructions while streaming data. Some designs also have a second-level unified array that is larger and slower, consulted only when the first level misses. The hierarchy mirrors the data cache hierarchy and has the same consequence: a first-level miss is cheap if the second level hits, and expensive if it does not.

The Walk That Follows a Miss

On a miss, the hardware reads the page-table root register and performs the walk described in the multi-level page table walk. Two implementation strategies exist. The first is a hardware page-table walker, which is a small state machine that issues the dependent loads itself and fills the cache entry when it reaches a valid leaf. The second is a software-managed scheme, used on some architectures, where a miss raises a trap and the kernel’s handler performs the walk and inserts the entry.

The hardware walker is faster because it avoids the trap and the kernel entry, and it can overlap the walk with other work on an out-of-order machine. The software scheme is more flexible: the kernel can implement arbitrary page-table layouts, handle faults inside the walk, and change policy without new silicon. Architectures with software-filled translation caches pay a trap on every miss, which makes the miss cost an order of magnitude higher and makes the hit rate correspondingly more important.

Either way, the miss cost is measured in the chain of table accesses. If the tables are in cache, a walk is tens of cycles. If the walk misses to DRAM at one or more levels, it is hundreds. The commonly quoted figure for a full miss is a few hundred cycles, which is roughly the cost of a DRAM access plus the delay incurred when the processor stalls on the load. Statements about exact costs are architecture-specific and change between generations; the ordering, not the number, is what designs are built around.

What Destroys the Hit Rate

Three access patterns account for most translation misses.

The first is a large sequential footprint. Streaming through a gigabyte touches 262,144 distinct pages. Each new page evicts some other entry, and because the pages are visited once, there is no reuse to recover the loss. The cache provides no benefit for the stream itself and is left full of entries that will never be used again. This is the case where large pages help most: 512 pages become one entry, and the stream fits in the cache’s reach.

The second is many mappings with poor spatial locality. A program that touches one page in each of a thousand separately mapped regions, repeatedly, cycles through a working set larger than the cache. Each round of access produces a miss per region. The fix is to reduce the number of distinct pages in the working set or to make the regions contiguous, and neither is always possible.

The third is context switching. Translations are tagged, on architectures that support tagging, by an address-space identifier so that entries from different processes can coexist. Without tagging, every context switch must flush the entire cache, and the new process begins with nothing. With tagging, a switch costs nothing in translation terms until the identifier space is exhausted and the kernel must recycle an identifier, which requires flushing the entries belonging to the recycled one. The cost of that flush is proportional to the number of entries, and a workload that switches between many processes with large footprints will pay it repeatedly. The mechanics of the switch itself are covered in kernel page table isolation and its cost, which is where the flushing rules become visible in a modern design.

Invalidation Is a Correctness Requirement

A cache of translations is only sound if it is invalidated whenever the underlying mapping changes. Changing a page-table entry while a stale translation remains cached produces a processor that reads the old frame, which is a correctness failure, not a performance one.

The rules are therefore strict. After modifying a page-table entry, the kernel must invalidate the corresponding translation before the modification can be relied upon. On x86 the instruction is INVLPG for a single page, and writing the root register reloads the entire translation context. On ARMv8 the operations are TLBI variants with the same split between single-entry and whole-address-space. The invalidation must be performed on every processor that might hold the entry, which turns a local mapping change into an inter-processor operation: the kernel sends a request to the other cores and waits for acknowledgement before returning.

The batching of these operations is a substantial part of kernel memory-management design. Invalidating a whole range page by page is slower than reloading the entire context, so a kernel that unmaps a large region chooses between the two based on the size of the range. The threshold is empirical and varies by architecture, and the choice has to account for the fact that a full reload also discards translations that were still valid.

There is a hardware subtlety that catches the unwary: some processors are permitted to cache a translation derived from a page-table entry even when the entry is not marked present, or to speculate a walk ahead of the instruction that needs it. The architectural invalidation instructions are specified to cover these cases, which is why the rule is to use the instruction rather than to assume that clearing a present bit is enough. Documentation for each architecture states the exact ordering requirements between the store to the entry, the invalidation, and the subsequent access.

Measuring the Reach of the Cache

Because the cache is small, its effect is visible in counters. Processors expose counts of translation misses and of walks, and a program whose miss rate is high relative to its page-touch rate is paying for translation on every page. Comparing the miss count against the number of distinct pages touched over an interval gives the reuse factor, and a reuse factor near one means the cache is doing nothing for that workload.

The practical consequence for software is that the number of distinct pages in the working set is a first-class performance property, alongside the number of cache lines. Two data structures with the same byte footprint can differ by an order of magnitude in translation misses if one packs its elements into few pages and the other scatters them. That is the same reasoning that motivates arena allocation and structure-of-arrays layouts, applied one level below the data cache, and it is why the page size, the mapping count, and the access order interact rather than acting independently.