Last time we translated 0x03d4 with a table lookup and a concatenate. That has to run on every load and store, so it has to be nearly free. Except the table lives in memory. To read one byte you first go to memory for the PTE, then go to memory for the data. Every access became two. (Pages)
The extra trip
You've doubled the cost of memory, which is a spectacular way to destroy performance.
The fix is the TLB, translation lookaside buffer. It's a small, highly associative cache of recently used PTEs, and critically it sits inside the MMU itself, on the SoC , not in RAM, and not in L1 either. Separate structure. Tiny. Fast.
Before walking the page table, check the TLB:
- TLB hit: the translation is already on-chip. No page-table access at all.
- TLB miss: walk the page table, then cache the result for next time.
If the TLB is set-associative, the VPN splits the same way any cache key does: TLBI (index: which set) and TLBT (tag: did we get the right entry). Many L1 TLBs are so small they are highly associative, or fully associative, and just match the VPN (plus an address-space id) which is Same idea, cache translations, not bytes.
And it works very well, for the same reason all caching works: locality.
- Temporal locality — if you used something recently, you'll probably use it again soon.
- Spatial locality — if you used something, you'll probably use what's next to it.
A loop over an array hits the same page hundreds of times in a row. One TLB entry covers an entire page (4 KiB or 16 KiB). A well written programs hit in the TLB the overwhelming majority of the time.
Two more pieces.
Where do the CPU caches sit? Translation happens, then you have a physical address, then you look in the data caches. L2 and L3 are physically addressed. L1 is often virtually indexed, physically tagged (VIPT): it can start the set lookup from the virtual address in parallel with the TLB, and it confirms the line with the physical tag once the TLB answers. Either way, you do not wait for DRAM to know "which page" before the cache even begins.
virtual address
↓
TLB ──hit──→ physical address
│ ↓
miss L1 → L2 → L3
↓ ↓
walk page table DRAM
And what makes a TLB miss not that costly? The page table is data in memory like any other data, so PTEs get cached in L1 and L2 like anything else. A TLB miss usually doesn't mean a trip to DRAM. It means a trip to L1.
One thing the last post left hanging: when the kernel writes CR3 / TTBR, those TLB entries were for the old table. Historically that write flushed the TLB. Modern chips tag entries with an ASID (ARM) / PCID (x86), so you can keep the other process's translations around instead of throwing them away on every switch.
The flat table ?
let take a case , Start modest: a 32-bit address space, 4 KiB pages, 4-byte PTEs. That's 2^20^ pages which is about a million , times 4 bytes, so 4 MiB of page table. Per process. Fully resident, all the time, even for a program that touches three pages and exits.
Now 64-bit. Even restricting to the 48 bits typical x86-64 actually implements, a flat table with 8-byte PTEs is 2^(48-12) × 8 bytes = 512 GiB. Per process. To describe a program using eight kilobytes. (The full 64-bit space is worse. Five-level / 57-bit x86 is the "hundreds of terabytes" version.)
The absurdity has an obvious cause when you name it: address spaces are overwhelmingly empty. Your program has some code down low, a heap growing up, a stack growing down, some libraries mapped in the middle, and between those regions, nothing mapped. Astronomically much nothing. A flat table dutifully allocates an entry for every page of that nothing.
The fix is a hierarchy. Instead of one enormous table, a small top-level table whose entries either point to a second-level table or are null.
And there's the win: if an entire region of the address space is unused, its top-level entry is null and the lower-level table for that region is never created at all. The empty parts cost one null entry each, not millions of PTEs. Only the top level must always be resident; the levels below get created on demand, and can themselves be paged out like ordinary data.
x86-64 uses four levels, each indexed by a 9-bit slice of the VPN, with the physical address of the top table in CR3. (2^9^ = 512 entries per table, times 8 bytes, is exactly 4 KiB — one page. The page table is made of pages. Everything is pages.) Apple Silicon with 16 KiB pages uses a different split: three levels of 11 bits over a 14-bit offset, because the page size changes the arithmetic. 2^11^ × 8 bytes = 16 KiB. Same trick. The principle is identical.
The obvious objection: doesn't a four-level table mean four memory accesses per translation instead of one? Yes. That's exactly what the TLB is for. On a hit, you walk zero levels.
Right. Go home.
Except the MMU reads a PTE and the valid bit is 0. The hardware cannot proceed. That is a page fault, and the name is a lie. That's next.