Question 2 of 5 · staff level

How do page tables and the TLB work — and when does translation cost show up in real workloads?

🎤 Say this first

A flat page table for a 64-bit space is impossible, so tables are multi-level radix trees (4–5 levels on x86-64): each translation walks 4–5 memory accesses — ruinous if done every load. The TLB caches recent translations (~1,500 entries), turning >99% of translations into ~1 cycle. TLB reach is tiny though (1,500 × 4KB ≈ 6MB), so big-memory random-access workloads (databases, JVM heaps) miss constantly — which is exactly what huge pages (2MB) fix: 500× the reach, fewer walk levels. -XX:+UseTransparentHugePages and database THP guidance are this exact story.

The full picture

Walk anatomy (x86-64): CR3 → PML4 → PDPT → PD → PT → frame; each level indexes 9 bits of the VPN. Hardware walks it on TLB miss; the walked result is cached (plus mid-level 'paging structure caches').
Context switches flush translation state (mitigated by ASID/PCID tagging) — part of why switches cost more than the register copy suggests.
Huge pages trade-offs: 2MB pages cut misses and walk depth, but risk internal fragmentation and (with transparent HP) latency spikes from khugepaged compaction — why some databases say THP=never while JVMs often benefit from explicit/THP-madvise setups. The nuanced answer is 'huge pages yes, transparent defrag carefully'.
When you'd notice: perf counters dTLB-load-misses high on a 100GB-heap service or a hash-join-heavy database — the fix (huge pages) can be worth 10–20% wall time. Also: iterating a 2D array column-major vs row-major is a TLB story as much as a cache story.

🔄 Likely follow-up questions

Why 4KB pages historically, and what breaks if you just make all pages 1GB?
What are inverted page tables and where are they used?
How does EPT/nested paging double translation cost in VMs?