Beyond the TLB: Co-Designing Data-Oriented Layout and Hardware Prefetch for Latency-Critical Paths

Beyond the TLB: Rethinking the Memory Wall for Latency-Critical Code

For decades, the Translation Lookaside Buffer (TLB) has been the go-to bottleneck for latency-sensitive applications. Teams spend weeks aligning page boundaries, using huge pages, and optimizing virtual-to-physical mappings. While TLB misses are costly, they are increasingly not the dominant stall in modern workloads. The real latency culprit often lies deeper: in the interplay between data layout and hardware prefetchers. A data structure that triggers TLB hits but defeats prefetchers can add hundreds of cycles per access. This guide addresses the core pain point: how to co-design data layouts so that hardware prefetchers work with you, not against you, on latency-critical paths.

Why TLB Optimization Alone Falls Short

A common scenario: a team optimizes a hash table lookup by using 2MB huge pages, reducing TLB misses by 80%. Yet the lookup latency barely improves. Why? Because the access pattern is random—each lookup jumps to a different bucket, and the hardware prefetcher cannot detect a stride. The prefetcher is left idle, and the data must be fetched from DRAM on every miss. TLB pressure was masking the real problem: poor data locality from the prefetcher's perspective. The lesson is that TLB and prefetch are coupled; fixing one without the other often yields diminishing returns.

The Prefetcher Blind Spot: Pointer Chasing and Irregular Access

Hardware prefetchers are remarkably good at detecting regular strides—sequential, strided, or even some sparse patterns. But they fail spectacularly on pointer-chasing traversals (linked lists, trees) and hash tables with random access. In these cases, each load address depends on the previous load's data, making prediction impossible. The prefetcher either remains silent or, worse, speculatively fetches garbage data that pollutes the cache. The solution is not to fight the prefetcher but to redesign the data layout so that access patterns become predictable or prefetch-friendly.

When the Prefetcher Becomes a Liability

There is a darker side: aggressive prefetchers can harm latency-critical paths by evicting useful data. For instance, a prefetcher that detects a sequential pattern in a rarely-used array might pull those lines into the L2 cache, evicting hot data from the critical path. This is known as prefetcher-induced cache pollution. Teams often disable hardware prefetch entirely on latency-sensitive cores, but that is a blunt instrument. A better approach is to isolate hot and cold data physically, so the prefetcher only sees hot regions. This is where hot/cold splitting becomes a co-design strategy, not just a data layout trick.

Practical Guidance: Start with Access Pattern Analysis

Before touching code, profile your critical path with tools like perf stat -e l2_rqsts.all_demand_data_rd,prefetch_data_rd on x86. Look for a high ratio of demand loads to prefetch loads—this indicates the prefetcher is idle. On ARM, use perf stat -e l1d_cache_rd,prefetch similarly. If you see many L2 cache misses but few prefetch requests, your data layout is likely defeating the prefetcher. The next step is to examine the access pattern: is it sequential, strided, random, or pointer-based? Each pattern demands a different co-design approach, which we explore next.

Core Concepts: Why Data Layout Dictates Prefetcher Success

Hardware prefetchers are not magical—they rely on pattern recognition at the cache line granularity. A prefetcher monitors the addresses of demand loads and looks for repeating deltas (strides). If it sees load addresses 0x1000, 0x1008, 0x1010, it predicts the next will be 0x1018 and speculatively fetches that line. This works beautifully for arrays and contiguous structures. But if the data is packed in a struct-of-arrays (SoA) layout, the prefetcher sees a stream of addresses that jump across different arrays—each access is to a different base address, breaking stride detection. The 'why' is fundamental: the prefetcher sees physical addresses, not logical structures. Your job is to arrange data so that the physical address stream exhibits regularity.

The Stride Detector: How It Really Works

Modern Intel processors have a stride prefetcher that tracks up to 32 independent load streams. Each stream records the last two addresses and computes the delta. If the delta repeats twice, the prefetcher predicts the next address and fetches it into the L2 cache. AMD's prefetcher works similarly but with different heuristics for sparse patterns. ARM's prefetcher (e.g., Cortex-X series) uses a more sophisticated temporal correlation table. The key insight: the prefetcher needs at least two consecutive same-stride loads to engage. If your code only accesses each cache line once (e.g., a single pass over a linked list), the prefetcher never activates because it never sees a repeat stride.

Cache Line Granularity: The 64-Byte Prison

Every memory access brings in a 64-byte cache line. If your data structure is a struct with 8 bytes of hot data and 56 bytes of cold data, you waste 87.5% of the cache line. Worse, the prefetcher will fetch adjacent lines hoping for a stride, but those lines contain only cold data. This is a double penalty: wasted bandwidth and cache pollution. The solution is to pack hot fields together in contiguous memory, so each cache line contains multiple hot items. This is the essence of data-oriented design: align layout with access frequency, not with logical grouping.

False Stride Detection: A Real-World Trap

Consider an array of structs (AoS) where each struct has a frequently accessed 'id' field and a rarely accessed 'description' string. If you iterate over the array to find an ID, the prefetcher sees a stride of sizeof(struct). It will fetch subsequent structs into cache, but the description fields are useless. Worse, if the description strings are long, the stride might be hundreds of bytes, causing the prefetcher to fetch lines that are never used. This is false stride detection—the prefetcher thinks it has found a pattern, but the pattern is misleading. The fix is SoA: place all 'id' fields in a contiguous array, and the prefetcher will see a stride of 4 or 8 bytes, fetching only useful data.

The Temporal Prefetcher: A Hidden Opportunity

Some processors (e.g., Intel's PECI, ARM's FEAT_MPAM) include temporal prefetchers that remember access patterns over time, not just space. If you access a pointer chain in the same order repeatedly, a temporal prefetcher can learn the sequence and prefetch the next pointer before it is needed. This is a game-changer for pointer-chasing workloads, but only if the data remains in the same physical addresses across runs. ASLR and memory allocation variability can defeat this. Co-designing for temporal prefetching means ensuring deterministic memory layout—using pools, arenas, or pre-allocated buffers to keep addresses stable.

Method Comparison: Three Prefetch-Aware Layout Strategies

Choosing the right strategy depends on your access pattern, hardware, and refactoring budget. We compare three widely used approaches: AoS-to-SoA transforms, pointer-chasing elimination via indirection arrays, and hot/cold splitting with explicit prefetch hints. Each has distinct trade-offs in terms of code complexity, memory overhead, and latency improvement. The table below summarizes the key differences, followed by detailed analysis.

AoS to SoA: When to Use and When to Avoid

The struct-of-arrays transform is the gold standard for data-oriented design. Instead of an array of structs, you have a struct of arrays. This packs hot fields contiguously, allowing the prefetcher to stride over them efficiently. Use this when your critical path iterates over many instances and accesses only a subset of fields. Avoid it when the codebase is deeply coupled with AoS interfaces (e.g., legacy APIs) or when the hot fields are not accessed sequentially. A common mistake is applying SoA to random-access patterns—if you access elements by index in arbitrary order, SoA offers no prefetch benefit because the stride is broken by random jumps.

Pointer-Chasing Elimination via Indirection Arrays

Linked lists are the nemesis of prefetchers. Each node access depends on the previous, so the prefetcher cannot look ahead. The fix is to replace pointers with indices into a flat array. For example, a tree node might have left/right child indices instead of pointers. Traversing the tree becomes an array walk with a predictable stride? No—the stride is still irregular because the indices are not sequential. However, the array itself is contiguous, so the prefetcher can fetch adjacent nodes speculatively. This works best if the tree is stored in breadth-first order or heap-like layout. The key insight: the indirection array itself is accessed sequentially, so the prefetcher fetches the next batch of indices, which then point to random data. This is not perfect, but it reduces latency by 40-70% compared to pointer chasing.

Hot/Cold Splitting with Software Prefetch Hints

When refactoring is too expensive, hot/cold splitting is a pragmatic middle ground. Separate frequently accessed fields from rarely accessed ones into different cache lines. Use padding to align hot fields to cache line boundaries. Then insert software prefetch hints (_mm_prefetch on x86, __builtin_prefetch on GCC) a few iterations ahead. This works well for loops with a known iteration count. The downside: software prefetch hints are architecture-specific and may be ignored on older hardware. Also, overuse can cause pipeline stalls. Best practice: use hints only for the first few iterations to 'warm up' the prefetcher, then let hardware take over.

Step-by-Step Guide: Co-Designing Layout and Prefetch

This guide assumes you have a latency-critical code path identified through profiling. Follow these steps to co-design your data layout with hardware prefetch behavior. Each step includes concrete checks and common pitfalls.

Step 1: Profile the Critical Path with Prefetch Metrics

Run your workload under perf stat and capture both cache miss and prefetch metrics. Key events on x86: l2_rqsts.all_demand_data_rd (demand loads that miss L2), l2_rqsts.pf_hit (prefetch hits), l2_rqsts.pf_miss (prefetch misses). Calculate the prefetch hit ratio: if it is below 20%, your layout is likely prefetch-unfriendly. Also look at l1d_pend_miss.pending to see how many cycles are spent waiting for data. On ARM, use l1d_cache_rd and prefetch events. Record the baseline latency in cycles using perf stat -e cycles,instructions.

Step 2: Identify the Access Pattern

Examine the source code of the critical loop. Is the access pattern sequential (e.g., for(i=0;i