Every walk's a hit: making page walks single-access cache hits

Memory grew 100× in a decade while TLBs merely tripled, so big-data applications drown in page walks — four dependent memory accesses each, up to 24 under virtualization — and this paper attacks both factors of the cost, merging pairs of 4 KB page-table levels into single 2 MB nodes so a walk needs fewer indirections (one access with walker caches, opportunistically and with graceful fallback when big allocations fail), and biasing cache replacement to keep page-table entries during high-TLB-miss phases (when data caching was failing anyway, and the whole table fits in the LLC) — together making most walks single-access cache hits for +9.2% native, +14.0% virtualized, and 8.7% less dynamic cache energy.

Why this problem is worth solving

Address translation is the tax every single memory access pays. When the

Virtualization compounds the tax brutally. The guest’s page table maps guest-virtual to guest-physical, but every guest-physical address — including the addresses of the guest page table’s own nodes — must itself be translated by the host’s table. The result is the

What people did before, and where it broke

• Page walker caches (the baseline, and genuinely excellent). Intel-style paging-structure caches remember upper-level entries by virtual-address prefix, letting walks skip to the lowest cached level. They already cut native walks from 4 accesses to about 1.5 (2.5 for random-access workloads) and virtualized walks from 24 to 4.4. Any new proposal must beat this, not the naive 4 — a bar several prior papers measured themselves without.
• POM_TLB / CSALT. A large set-associative TLB in DRAM, with cache prioritization for its entries. Avoids OS changes, but adds a shared cross-VM structure with interference and security questions — and CSALT, tuned for large pages and very frequent context switches, delivers just +0.3% here.
• ASAP. Prefetch the lower table levels while the upper ones are accessed. But PWCs already skip the upper levels, leaving little to overlap (+1.7%), and prefetching without pointer chasing requires the kernel to lay table nodes out contiguously — a guarantee fragmented systems cannot make.
• Elastic Cuckoo Hashing. Replace the radix tree with hash tables: no pointer chasing at all. But each lookup issues three to four parallel accesses (against flattening’s single access), costing net performance (−5.9%) and 32% more cache energy — and growing the hash tables requires large contiguous allocations, again without a fallback.
• The pattern. Designs that require contiguity fail exactly when systems are busiest; designs that bolt on new structures fight the PWC instead of building on it.

How it works

The idea

Split the cost into number-of-accesses × latency-per-access, and notice different tools fit each factor. Flattening is an access-count weapon: the radix tree’s depth is a design choice from an era of small memories, and merging levels just spends a little of today’s abundant capacity (2 MB nodes instead of 4 KB) to halve it. Prioritization is a latency weapon: it cannot make walks shorter, but it can make the one remaining access hit in SRAM instead of DRAM. The factorization also explains the headline asymmetry — natively, PWCs already crushed the access count (1.5), so flattening alone adds just 2.3% and the latency lever dominates (6.8%); under virtualization the 2D walk re-inflates the access count (4.4), and flattening’s share triples (7.1%). Knowing which factor is currently binding is the analysis; the mechanisms are almost mundane.

Opportunistic beats guaranteed. The deep deployability insight is about allocation: any translation scheme that requires large contiguous physical memory (ECH’s hash regions, ASAP’s sequential layouts) inherits a failure mode the kernel cannot paper over — and the paper’s own stress test quantifies it at up to 12% allocation failures. Because flattening exploits the radix structure, every 2 MB node has an exact 4 KB-pair equivalent, so the kernel flattens when it can and shrugs when it cannot, per subtree, at runtime. The same flexibility handles large data pages (selectively un-flatten those regions) and even devices that have never heard of flattening (walk through the glue table). Graceful degradation is not a bolt-on here; it is why the design can exist in a real kernel at +614 lines.

Spend cache on metadata exactly when data caching is failing. Naively, reserving LLC space for page tables robs the application. The paper’s counter-observation: phases of high TLB miss rate are phases of high data miss rate — the same poor locality causes both. In those phases the data was not going to hit anyway (95% L2 miss), while the page table is 512× smaller than the data and therefore the only thing with genuine reuse. The bias costs 4.7 points of extra L2 data misses and saves 36.2 points of walk misses — an easy trade, gated by hardware counters so well-behaved phases pay nothing. A quick real-machine hack (a helper thread touching a graph benchmark’s page table to keep it LLC-resident on an i7) already yields 5%, grounding the simulated 6.8%.

One TLB miss, before and after

baseline average: ~1.5 accesses per walk (2.5 for random-access patterns)
the research bar is beating THIS, not the naive 4-access walk

Why it works

• A radix tree’s depth is spent one 9-bit slice at a time → merging two levels consumes 18 bits per step using nothing but a bigger node → depth halves, and the existing L3 PWC (now matching 18-bit prefixes) eliminates the root access, leaving exactly one.
• Every flattened node has an exact conventional equivalent (2 MB node ↔ one L2 node + 512 L1 nodes) → the kernel can decide per subtree, at allocation time, with one bit in the parent entry → no guaranteed-contiguity assumption, so fragmentation degrades performance smoothly instead of breaking the design.
• High TLB miss rate and high data miss rate share a cause (poor locality over a large footprint) → during exactly those phases, cache space moved from data to page table costs little (the data was missing) and pays much (the table, 1/512th the size, actually fits and reuses) → walk latency falls from 50.9 to 29.1 cycles.
• Virtualization multiplies walk accesses (each guest level needs host translation) → shrinking either table shrinks the product, and the guest table is the large, poorly-cached factor → flattening gains triple under virtualization (2.3% → 7.1%), and the techniques stack to +14.0%.
• Fewer memory-system accesses and more SRAM hits are also energy wins → −8.7% dynamic cache and −4.7% DRAM energy virtualized — no new structures to power, unlike DRAM-TLB or hashed-table proposals.

What it costs

• Page-table bloat, bounded. A flattened leaf node allocates all 262,144 entries even if sparse regions would have skipped 4 KB nodes — about 2 MB of extra table for an 8 GB app (18 MB vs 16 MB). Negligible against the data, but real for tiny processes, which is why flattening is per-table opportunistic rather than default.
• Large data pages need care. Flattened L2+L1 cannot express a 2 MB data mapping directly (512 replicated entries otherwise); the fix — selectively not flattening 1 GB regions with 32+ large pages — works but adds a heuristic threshold the kernel must manage.
• Prioritization steals from data, deliberately. The 4.7-point rise in L2 data misses is a fine trade during TLB-miss storms, but the mechanism leans on phase detection; in mixed workloads, shared caches need the per-context partition tags to avoid cross-process theft. At extreme scale (4 TB footprints, 0.2% of the table cacheable) the bet may stop paying — the authors say so.
• Simulation-heavy evidence. Performance numbers come from gem5 system-call-emulation mode (no OS interference modeled) plus an industrial simulator; the real-hardware signals are indirect (the helper-thread experiment, the kernel stress test).
• Recursion needs the glue table. Self-referencing tables (Windows) require the embedded L4* sub-table and a walker tweak — small, but a real compatibility surface beyond Linux.

The evaluation

Two simulators (academic gem5 with a faithful Skylake-style PWC, plus an industrial Arm mobile-core simulator), a real kernel prototype stress-tested under memory pressure, three fragmentation scenarios (0%, 50%, 100% large pages), native and virtualized runs, multicore mixes, and head-to-head reimplementations of three prior systems.

Check yourself

Sources

• ACM DL: Every Walk’s a Hit: Making Page Walks Single-Access Cache Hits — ASPLOS 2022 (open access)