Virtual memory means every single memory access your program makes — every load, every store, every instruction fetch — names an address that doesn’t physically exist. Something has to translate it, every time. That something is a four-level tree walk through memory, which sounds ruinously expensive because it would be: done naively, one load becomes five. The reason it isn’t is a cache you can’t see in any profiler by default, and whose misses are one of the great hidden taxes in large-memory workloads.

The Radix Tree

x86-64 translates 48-bit virtual addresses (57 with five-level paging on recent CPUs) through four levels of tables, each indexed by 9 bits of the address:

text
  virtual address:  [ 9b PGD | 9b PUD | 9b PMD | 9b PTE | 12b offset ]

  CR3 ─▶ PGD ─▶ PUD ─▶ PMD ─▶ PTE ─▶ physical frame + offset

Each level is a 4 KB table of 512 entries; the leaf entry holds the physical frame number plus the permission/dirty/accessed bits. The tree shape is the point: a flat table for 48 bits of address space would need 512 GB per process, but the tree only materializes paths that are actually mapped — a small process touches a handful of 4 KB tables. This is also what fork copies (the tables, not the memory), and what the kernel edits on mmap/mprotect.

A full walk is four dependent memory accesses. If every user access paid that, memory would be ~5× slower.

The TLB

The Translation Lookaside Buffer caches recent translations — virtual-page → physical-frame, permissions included. Typical shape on a modern core: 64–128 entries L1 dTLB, ~1.5–2K entries shared L2 TLB. A hit is free (checked in parallel with the L1 cache lookup). A miss triggers the hardware page-table walker: those four dependent loads, 20–100+ cycles, potentially missing in the data cache themselves.

Do the coverage math, because it’s grim: 1,500 entries × 4 KB = 6 MB of address space covered. Your L3 cache is bigger than your TLB reach. Any workload that strides randomly through more than a few MB — graph analytics, large hash tables, databases, JVM heaps — misses in the TLB before it misses in cache. That’s the hidden tax: people tune for cache misses and never measure

bash
perf stat -e dTLB-loads,dTLB-load-misses,dtlb_load_misses.walk_active ./app

A dTLB miss rate over ~1% on a memory-bound workload is worth acting on; walk_active cycles tell you directly what fraction of runtime the walker is eating.

Huge Pages: Buying Reach

The lever is page size. A 2 MB huge page uses one PMD-level entry instead of 512 PTEs: one TLB entry now covers 512× the memory, and walks are one level shorter. 1 GB pages go further still. Two ways to get them:

  • Explicit hugetlbfs (mmap with MAP_HUGETLB): reserved at boot or via /proc/sys/vm/nr_hugepages, guaranteed, never swapped — the database way (PostgreSQL huge_pages=on, also the standard fix for TLB-thrashy VM guests via KVM).
  • Transparent huge pages (THP): the kernel opportunistically back-fills anonymous memory with 2 MB pages (madvise mode is the sane default; khugepaged compacts in the background). Free wins for big heaps — with the known caveat that always-mode THP plus jemalloc-style allocators produced legendary latency-spike and memory-bloat incidents at Redis/MongoDB scale. Measure with grep AnonHugePages /proc/meminfo.

Typical results on TLB-bound code: 10–30% wall-time improvement for flipping THP/huge pages on a random-access 10+ GB working set. It’s one of the few order-nothing optimizations left.

Two Footnotes That Bite

Context switches: the TLB is per-address-space state. Old x86 flushed it all on CR3 write; modern CPUs tag entries with a PCID so switches don’t nuke translation state — one reason the indirect cost of context switching fell. Meltdown mitigation (KPTI) doubled down on this machinery: kernel and user now use separate tables, and PCIDs are what keep the syscall path from being a full TLB flush each way.

Shootdowns: on munmap/mprotect, stale entries on other cores must die. The kernel sends IPIs — inter-processor interrupts — and every core pauses to invalidate. An application that maps/unmaps frantically across a 64-core box can spend whole percents of machine time in TLB shootdowns (/proc/interrupts, the TLB row). Allocators that madvise(MADV_FREE) instead of unmapping exist partly for this reason.

Takeaways

  • Every access translates through a 4-level radix tree; the TLB is why that’s survivable.
  • TLB reach is ~6 MB with 4 KB pages — smaller than L3. Big random working sets are TLB-bound; perf stat -e dTLB-load-misses proves it either way.
  • 2 MB huge pages multiply reach 512×; THP-madvise is the low-risk default, hugetlbfs the guaranteed one.
  • Frequent unmapping on many-core machines pays in TLB-shootdown IPIs.
  • PCID/KPTI made “context switch flushes the TLB” only half-true — the cost moved, it didn’t vanish.