Cache Deep Dive IV — TLB, Huge Pages, and Memory-Level Parallelism

Earlier parts examined the performance characteristics of sequential and random access under single-threaded execution, and noted in passing the destructive effect of random access on the TLB. This part devotes full attention to the TLB: what it is, why a TLB miss is more severe than a cache miss, why a page table walk constitutes one of the longest dependency chains a CPU can encounter, how huge pages fundamentally alter TLB reach, and where memory-level parallelism falters in the face of TLB misses.

Page Boundaries: Where the Prefetcher Halts

Part III, in its discussion of prefetchers, noted a hard constraint: a prefetcher must not cross page boundaries on its own authority. The operating system manages virtual memory in units of pages (typically 4 KB, i.e., 64 cache lines). When a program reaches the end of one page and is about to step into the next, the prefetcher cannot proceed. The reason is that the next page may not reside in physical memory (it may have been swapped out to disk), or it may be an entirely invalid virtual address — if the prefetcher were to speculatively initiate an access to the next page, it would trigger a page fault: the OS would have to suspend the process and swap the page in from disk; in the case of an invalid address, the OS would terminate the process outright. From a security standpoint, the prefetcher neither can nor is permitted to autonomously cross page boundaries without TLB approval. Hence a performance brake appears every 4 KB — even when traversing an array sequentially, after every 64 cache line accesses the prefetch pipeline must pause and await confirmation of an address translation.

This is not to say that modern CPU prefetchers are completely unable to cross pages. Intel's Next Page Prefetcher and AMD's equivalent mechanism can consult the TLB when approaching a page boundary — if the address mapping for the next page is already registered in the TLB, the prefetcher receives clearance to continue prefetching across the boundary. But if the next page is not in the TLB (as happens the first time that page is traversed), the prefetcher must wait in place for the TLB fill to complete. This brings us to the central question of this section: what is the cost of a TLB miss itself?

TLB: The Cache for Address Translation

Every time the CPU issues a virtual address to access memory, that address must first be translated into a physical address. The mapping table from virtual to physical addresses — the page table — resides in main memory and is maintained by the OS. If every memory access required walking the page table in main memory, program performance would be unacceptable — a single virtual address translation would itself entail several main memory accesses. The TLB (Translation Lookaside Buffer) is designed precisely for this purpose: it is a dedicated cache for address translation, storing recently used mappings from virtual page numbers to physical page numbers.

The TLB's hierarchical structure is conceptually similar to that of data caches, but with far smaller capacity:

L1 TLBs are fully associative — unlike L1 data caches, TLB entry counts are tiny, and a fully associative lookup across a few dozen entries is entirely feasible. The reach of the L1 TLB, calculated with 4 KB pages, is roughly 256–512 KB (64–128 entries × 4 KB), which falls neatly between the capacities of the L1d and L2 caches. The L2 TLB's reach at 4 KB works out to roughly 16–32 MB, just matching the typical capacity of the L3 cache.

The effective capacity of a TLB is usually measured not in entry count, but in TLB Reach:

TLB Reach = TLB entry count × page size

It represents "the largest working set a program can access while bypassing page table walks by hitting the TLB directly." For a 4,096-entry L2 TLB paired with 4 KB pages, TLB Reach = 16 MB. This means that once a program's random-access working set exceeds about 16 MB, the L2 TLB begins to suffer sustained capacity misses — every first access to a new page incurs the cost of a page table walk. This is a recurring bottleneck metric in discussions of NUMA, in-memory databases, and large-memory systems. The essence of huge page optimization is not to make an individual address translation faster, but to expand the reach of the address translation cache — pulling TLB Reach from 16 MB up to 8 GB.

It is worth emphasizing that the TLB also follows the Harvard architecture: at the L1 level it is split into the D-TLB (data side) and I-TLB (instruction side), each independent. Instruction fetch and data read use separate L1 TLBs, which prevents data-intensive loops from contending with scattered, large-volume code for TLB entries. The L2 TLB, however, is unified — instruction and data mappings share the same cache space.

The Page Table Walk: The True Cost of a TLB Miss

A TLB miss by itself is not an immediate disaster — if the target page table data already resides in a processor-internal cache, refilling a TLB entry costs only a dozen or so cycles. But if the relevant page table levels are absent from every cache, the hardware page table walker must traverse the full page table hierarchy.

Consider x86-64's 4-level page table:

CR3 → PML4 → PDPT → PD → PT → physical page

When a TLB miss occurs and every page table level misses every cache, the hardware must complete 4 serial memory reads: read the PML4 entry → read the PDPT entry → read the PD entry → read the PT entry. Notice that the address at each step depends on the result of the previous step — this is what makes the page table walk unique among memory operations: it is a built-in dependency chain. Parts I and III, when discussing MLP, pointed out that independent memory accesses can overlap on the bus; but a single page table walk is intrinsically non-parallelizable — until the PML4 entry is read, the hardware does not know where the PDPT entry is located. In the worst case, if every level of the page table misses the TLB, the PWC, and all data caches, a 4-level page table walk requires 4 serial DRAM reads, with a total latency potentially approaching 800 cycles; and if the target data likewise resides in DRAM, an additional main memory access is layered on top. It is worth stressing that in real program execution, page table data has extremely strong spatial locality (a single 4 KB page holds many consecutive page table entries), and page table data at every level frequently resides in the L2/L3 caches — thus the actual cost of most TLB misses is far lower than this worst-case figure.

Modern CPUs insert an extra buffer between the L2 TLB and main memory: the Page Walk Cache (PWC; Intel calls it the Paging-Structure Cache). The PWC caches the mappings at intermediate levels of the page table (e.g., the PML4→PDPT mapping, the PDPT→PD mapping, etc.), so that only those levels that miss the PWC need to be walked. For example, if the PD→PT mapping is already in the PWC, the 4-level walk is reduced to 2 levels (PML4→PDPT→PWC hit), compressing the latency dramatically. The presence of the PWC is the reason that most conventional programs' TLB misses do not cost 800+ cycles each time.

Huge Pages

All of the preceding analysis assumes the default page size of 4 KB. Enlarging the page expands the address range covered by each TLB entry, thereby multiplying the TLB's effective capacity by the corresponding factor. This is the fundamental motivation for huge pages.

Linux/x86-64 supports two huge page sizes:

• 2 MB huge pages: the page offset is 21 bits; a single TLB entry covers 512 of the 4 KB pages. With a 4,096-entry L2 TLB, reach goes from 16 MB to 8 GB (2 MB × 4,096).
• 1 GB huge pages: the page offset is 30 bits; a single TLB entry covers 262,144 of the 4 KB pages. With a 4,096-entry L2 TLB, reach can reach 4 TB. But the granularity is very coarse, making this useful only in very few scenarios with enormous contiguous allocations (e.g., virtual machine memory passthrough, giant pre-allocated buffer pools in in-memory databases).

With huge pages enabled, the page table hierarchy is also shortened: a 2 MB page table has only 3 levels (PML4→PDPT→PD, mapping directly to a physical page — no PT required), and a 1 GB page table has only 2 levels (PML4→PDPT). This simultaneously reduces the depth of the page table walk and lowers the worst-case cost of a TLB miss.

There are three paths to using huge pages in a program:

1. Explicit reservation: use the mmap system call with the MAP_HUGETLB flag to reserve a specified number of huge pages and map a virtual address region directly onto them. The libhugetlbfs library provides wrappers to simplify usage.
2. Transparent Huge Pages (THP): the Linux kernel, via the khugepaged background thread, periodically scans the address spaces of processes and, upon detecting large stretches of contiguous 4 KB pages, attempts to collapse them into 2 MB huge pages. Applications benefit without any code changes. THP is recommended for the vast majority of server workloads.
3. Active hinting: via madvise with MADV_HUGEPAGE, the program explicitly tells the kernel that a particular address region is a good candidate for huge pages, giving THP a priority hint for collapsing. Allocators such as jemalloc and tcmalloc can automatically issue this hint for the heap regions they manage.

Common commands for verifying that huge pages are in effect:

grep Huge /proc/meminfo          # view global huge page statistics
cat /proc/smaps | grep KernelPageSize   # view the actual page size for a specific process
perf stat -e dTLB-loads,dTLB-load-misses ./program  # compare TLB miss rate before and after enabling

Side Effects of Huge Pages

Huge pages are not without cost. There are three known side effects that should be evaluated before deciding whether to enable them.

First, amplified copy-on-write on fork. A child process created by fork shares the same set of memory pages with the parent (COW semantics). When the parent subsequently writes, the OS must make a physical copy of that page. With 4 KB pages, the copy is barely perceptible; with 2 MB or 1 GB huge pages, the OS must copy an entire page on a single COW trigger. Services such as Redis, which rely on fork for persistence, have long recommended disabling THP — one of the primary reasons being that huge pages amplify COW latency. In a latency-sensitive online service where every second counts, this effect can cause client-perceived connection timeouts.

Second, internal fragmentation. The fragmentation issue with THP is not that a single object directly occupies 2 MB — malloc(10) does not immediately receive a 2 MB page — but rather that fine-grained allocations steadily degrade the effective utilization within a collapsed huge page: a single 2 MB huge page may contain hundreds of small objects and large unused holes, driving up overall memory consumption.

Third, the compaction cost of THP. The khugepaged kernel thread periodically scans the address spaces of processes, looking for sequences of contiguous 4 KB pages that are suitable to collapse into a 2 MB huge page. On systems under high load and with large memory, the CPU consumption and memory bandwidth occupation of khugepaged can themselves become a bottleneck — when its scanning speed cannot keep up with the allocation rate, vast numbers of 4 KB pages linger in an intermediate "waiting to be collapsed" state, neither enjoying the TLB benefits of huge pages nor sparing the page table walk from the extra steps caused by page table fragmentation.

Given these side effects, choosing a huge page strategy requires identifying the characteristics of the workload: for applications with continuous allocation, stable memory footprints, and insensitivity to fork latency (e.g., pre-allocated regions in in-memory databases), explicit huge pages are the optimal choice; for workloads with fluctuating memory footprints, fork requirements, or extremely fine-grained allocation, THP's passive collapsing is more appropriate — but CPU usage of khugepaged should be monitored.

I-TLB: The Instruction Side Is Not Immune

The preceding discussion has focused on the data-side TLB (D-TLB). The I-TLB obeys the same physical principles: instruction addresses emitted by the fetch unit likewise require TLB translation. When a program's code footprint exceeds the I-TLB reach and the execution path is scattered across a large number of pages, the instruction fetch stage will suffer stalls just as severe as those on the data side.

Typical warning signs include: a C++ program that instantiates template functions across numerous headers, or one that relies heavily on virtual functions and indirect calls such that the compiler cannot lay out the code paths compactly. When each function call lands in a different 4 KB page, the instruction fetch pipeline must first wait for the I-TLB translation to complete. The instruction side likewise has prefetch mechanisms (Instruction Prefetcher / Next-Line Prefetcher), which on simple paths of sequential fetch can trigger I-TLB fills ahead of time; but their predictive horizon is far narrower than the data-side prefetcher. Faced with numerous indirect branches (virtual function calls, function pointers, jump tables of switch statements) and scattered code layouts, I-TLB misses remain difficult to hide effectively. perf stat -e iTLB-load-misses can quantitatively detect the problem.

Compiler optimizations offer indirect help for the I-TLB: -Os or -Oz (optimization levels that prioritize code size) not only shrink the overall size of the .text section, but also reduce the number of pages spanned by the code, indirectly lowering the I-TLB miss rate. [[likely]] and [[unlikely]] hint the compiler to move cold path code into separate sections so that hot path code is concentrated in a small number of pages — a topic that will be examined in detail when Part VII discusses code layout.

MLP Revisited: Why TLB Misses Are Lethal

Part I, when first introducing memory-level parallelism (MLP), stressed that it allows the CPU to have multiple independent memory requests in flight on the bus simultaneously, thereby partially overlapping the latencies of multiple accesses. Part III showed how random access undermines MLP: dependency chains prevent independent memory-accessing instructions from being issued in parallel.

A TLB miss inflicts a third, and the most thorough, form of destruction on MLP. The interior of a single page table walk is a dependency chain — each read of the 4-level page table depends on the result of the previous step, and the finite state machine within the hardware must complete them serially. In modern Intel/AMD processors, the hardware page table walker can handle multiple mutually independent TLB misses concurrently (e.g., two unrelated load instructions each triggering their own page table walks) — this is known as page-walk-level parallelism; but the progress of any single walk is not accelerated by this. More critically, when a load instruction is stalled because its page has not yet been cached by the TLB, every instruction in the ROB that directly or indirectly depends on that load's result is frozen as well — meaning it is not only that one instruction waiting on the TLB, but an entire dependency subtree locked in place.

This explains why random-access performance degradation under small pages (4 KB) is exponential rather than linear: when the dataset doubles, not only does the cache hit rate smoothly descend along the random-access ramp curve, but the number of pages not cached by the TLB also doubles — and every one of those accesses incurs hundreds of extra cycles for the page table walk. This accelerated degradation only eases when the working set shrinks to within L2 TLB reach, or when huge pages expand the TLB's effective capacity.

The relief huge pages provide for this problem is twofold: they reduce the total number of pages requiring TLB translation, and they shorten the page table walk depth after each TLB miss. For big-data applications with working sets reaching tens or even hundreds of gigabytes — such as in-memory analytics engines, graph processing frameworks, and real-time bidding systems — the two levels of TLB together total only a few thousand entries, which against millions of 4 KB pages is little more than a drop in the bucket. After switching to 2 MB huge pages, the page count drops to 1/512 of the original, and the TLB reach stretches from ~16 MB to ~8 GB, providing the only sustainable address translation path for these applications.

The next part will discuss write policies: how write policies manage dirty data, how the Store Buffer buffers writes inside the pipeline, and how the hardware nature of memory barriers derives from the existence of the write buffer.