Cache Miss Anatomy: Tuning Memory Layout for Prefetch-Dominated Workloads

Hardware prefetchers are the silent workhorses of modern CPUs—they hide latency so well that many developers forget they exist. But when a workload is prefetch-dominated, meaning most memory accesses are speculative and issued by the hardware rather than explicit loads, the cache miss profile changes radically. Demand misses become rare; instead, we see prefetch-induced pollution, bandwidth saturation, and a surprising number of L2 and L3 misses that look like they shouldn't happen. This guide is for engineers who have already tuned the obvious things—loop order, alignment, and basic padding—and now need to understand why their memory layout still causes stalls. We'll walk through the anatomy of these misses, then show how to reshape data structures to cooperate with the prefetcher instead of fighting it.

The Real Context: Where Prefetch-Dominated Workloads Show Up

Prefetch-dominated workloads aren't rare. They appear in any code that streams through large, contiguous arrays with predictable access patterns: video decoding, database scan operators, linear algebra kernels, and packet processing pipelines. The common thread is that the CPU's prefetcher—usually the next-line and stride-based prefetchers in modern Intel and AMD cores—correctly predicts most addresses before the program explicitly loads them. This means the L1 data cache hit rate can be very high (>90%), but the L2 and L3 hit rates might still be poor because the prefetcher is filling those caches with lines that the program will only touch once, evicting data that could have been reused.

Consider a typical hash join in a database engine. The build phase creates a hash table with entries scattered in memory; the probe phase reads those entries in a pattern that depends on the hash values. Hardware prefetchers struggle with random lookups, so the probe phase is demand-miss dominated. But the input stream—the probe tuples themselves—is often scanned sequentially, triggering aggressive prefetching that fills the cache with tuple data that is read once and discarded. The real cost is not the miss itself, but the eviction of hash table entries that were about to be used. This is the signature of a prefetch-dominated workload: the prefetcher is working hard, but on the wrong data.

Another classic scenario is breadth-first graph traversal. Each level of the BFS touches a new set of vertices, and those vertices are usually stored in a flat array indexed by vertex ID. The CPU's stride prefetcher detects the sequential access pattern on the array and starts pulling in cache lines ahead of the current read. But the actual traversal also follows adjacency lists, which are irregular and pointer-heavy. The prefetcher fills the cache with vertex metadata that won't be used again soon, while the adjacency data suffers cold misses. Teams often blame the graph structure, but the real fix is to separate hot and cold fields so that the prefetcher's bandwidth is spent on data that will actually be consumed.

Foundations: What Most Engineers Get Wrong About Prefetch Behavior

The first mistake is assuming that prefetchers only help. In reality, they consume memory bandwidth and cache capacity speculatively, and when the speculation is wrong, the cost can exceed the benefit. The second mistake is treating all prefetchers as identical. Intel's L2 streamer and L1 stride prefetcher have different trigger conditions and different degrees of aggressiveness. On recent architectures, the L2 prefetcher can issue up to two cache line fills per cycle, which is enormous bandwidth. If your data layout causes it to prefetch useless lines, you're wasting a significant fraction of your memory subsystem capacity.

Another common misunderstanding is the difference between temporal and spatial locality. Prefetchers exploit spatial locality—they assume that if you access address X, you'll soon access X+64 (the next cache line). But if your data structure has a sparse access pattern (e.g., every 128 bytes), the prefetcher will fetch the intermediate lines unnecessarily. This is the root cause of many "mystery" L2 misses: the line was prefetched but never used, so it's evicted without being touched, and then a demand access later misses again. The solution is to pack your hot data densely so that the prefetcher's stride matches your actual access stride.

Finally, many engineers underestimate the impact of TLB misses in prefetch-dominated code. When the prefetcher runs ahead, it can generate TLB misses for pages that haven't been touched yet. This is especially painful with 4 KB pages because the prefetcher can easily outrun the TLB coverage. Huge pages (2 MB or 1 GB) help, but they also change prefetch behavior because the stride prefetcher tracks page boundaries differently. We've seen workloads where switching to huge pages reduced L2 misses by 15% simply because the prefetcher stopped resetting its stride at 4 KB boundaries.

How Prefetchers Interact with Cache Levels

Modern CPUs have multiple prefetchers at different cache levels. The L1 data prefetcher is conservative—it only issues one or two lines ahead. The L2 prefetcher is more aggressive, often fetching multiple lines per access. The L3 prefetcher (on some architectures) is even more aggressive but has longer latency. Understanding which prefetcher is causing the pollution is key. For example, if you see many L2 misses but few L1 misses, the L2 prefetcher is likely filling lines that are evicted before use. Profiling tools like perf can show you prefetch efficiency metrics (e.g., "L2_RQSTS.PF_MISS") to isolate the problem.

The Role of Cache Line Alignment

Alignment matters more in prefetch-dominated code than in general-purpose code because misaligned accesses can cause the prefetcher to fetch two lines instead of one. If your hot fields straddle a cache line boundary, a single access triggers two line fills, doubling the prefetch traffic. The fix is to align your hot fields to 64-byte boundaries, but that can waste space. A better approach is to reorder struct fields so that hot fields are contiguous and aligned within a single cache line, leaving cold fields in separate lines that the prefetcher won't touch.

Patterns That Work: Structuring Data for Prefetch Cooperation

The most effective pattern is cache-line splitting: separate hot and cold fields into different cache lines, and align the hot fields so that they fall into as few cache lines as possible. For example, if you have a struct with a frequently accessed ID and a rarely used timestamp, put the ID in a dedicated cache line and let the timestamp share a line with other cold data. This reduces the number of cache lines that the prefetcher must pull in for each access.

A related pattern is array of structures (AoS) to structure of arrays (SoA) conversion, but with a twist: you don't have to convert everything. Only the hot fields that are accessed together in a tight loop should be in a separate array. The cold fields can remain in a parallel array or a separate struct. This is often called "SoA with hot-cold splitting". For instance, in a particle simulation, position and velocity are accessed every frame, while mass and charge are accessed rarely. Store position and velocity in separate SoA arrays, and keep mass and charge in a single AoS array that is only accessed when needed.

Another effective technique is prefetch-aware padding. If you know your access stride is 32 bytes (e.g., every other int in an array), pad the array to 64-byte alignment so that each cache line contains two elements, but the prefetcher's stride matches the element stride. This sounds counterintuitive—padding usually wastes space—but it prevents the prefetcher from fetching lines that contain only one useful element. We've seen cases where adding 32 bytes of padding between elements reduced cache miss rates by 20% because the prefetcher stopped fetching useless lines.

Using Software Prefetching as a Fallback

When hardware prefetchers can't handle the pattern (e.g., irregular strides or indirect accesses), software prefetching with __builtin_prefetch or _mm_prefetch can help, but only if the layout is already optimized. Software prefetching works best when you know the exact address of the next access several iterations ahead. Combine it with cache-line splitting: prefetch only the hot cache line, not the entire struct. For example, in a linked list traversal, you can prefetch the next node's hot fields while processing the current node, but only if those hot fields are in a predictable location within the node.

Batch Processing and Tiled Access

For workloads that process large datasets in passes (e.g., graph processing or matrix multiplication), tiling is a well-known technique, but it's rarely tuned for prefetch behavior. The tile size should be chosen so that the working set of hot data fits in L2 cache (typically 256 KB to 1 MB per core). This ensures that the prefetcher's fills stay within the tile and don't pollute the cache with data from other tiles. We've found that tile sizes that are multiples of the page size (e.g., 2 MB) work well because they align with the prefetcher's page-aware behavior.

Anti-Patterns: Why Teams Revert to Slower Layouts

The most common anti-pattern is overzealous packing. Engineers see the benefits of cache-line splitting and SoA conversion, and they apply it everywhere, including to data structures where the hot fields are already small and the cold fields are never accessed. The result is code that is harder to maintain and often slower, because the overhead of managing multiple arrays (pointer indirection, allocation fragmentation) outweighs the cache benefits. We've seen teams revert to AoS after a "SoA refactor" because the code became too complex and the performance gain was marginal.

Another anti-pattern is false sharing in multithreaded code. When two threads write to different fields that happen to be in the same cache line, the cache coherence protocol forces constant invalidations. This is well-known, but it's especially dangerous in prefetch-dominated workloads because the prefetcher can amplify the problem. If one thread is writing to a cache line that another thread is reading, the prefetcher may fetch the line just before it's invalidated, wasting bandwidth. The fix is to pad hot fields to 64-byte boundaries, but this increases memory usage. A better approach is to use per-thread data structures that are cache-line-aligned from the start.

A third anti-pattern is ignoring allocation order. When you allocate objects with malloc, they are placed in memory in an order that depends on the allocator's free list. If you then access them in a different order (e.g., by sorting a list of pointers), the access pattern becomes random, and the prefetcher cannot help. The solution is to allocate objects in the order they will be accessed, or to use a custom allocator that places objects contiguously. We've seen teams spend weeks tuning cache misses only to find that a simple change from malloc to a pool allocator halved the miss rate.

When Pointer Chasing Defeats Prefetching

Pointer-heavy data structures like trees and linked lists are the worst case for prefetchers. Each node access is a pointer dereference, and the addresses are unpredictable. The only way to make prefetching work is to linearize the structure (e.g., store tree nodes in a breadth-first array) or to use software prefetching with a stride that matches the node layout. Many teams try to fix this by adding prefetch intrinsics, but if the node layout is not cache-line-optimized, the prefetch is wasted. The better fix is to change the data structure itself.

Maintenance, Drift, and Long-Term Costs

Cache layout tuning is not a one-time optimization. As code evolves, new fields are added to structs, access patterns change, and the carefully tuned layout drifts. The most common long-term cost is layout rot: after a few refactors, the hot fields are no longer contiguous, the alignment is broken, and the prefetcher is back to fetching useless lines. To prevent this, we recommend adding compile-time assertions (e.g., static_assert in C++) to enforce that hot fields are within the first 64 bytes and that the struct size is a multiple of 64. Documentation alone is not enough—teams forget.

Another cost is portability. Prefetcher behavior differs across CPU generations and vendors. A layout that works well on an Intel Skylake may be suboptimal on an AMD Zen 4 or an ARM Neoverse. For example, ARM's prefetchers are generally less aggressive and more sensitive to access stride. If your code runs on multiple architectures, you may need to profile on each one and use conditional compilation or runtime detection to select the best layout. This adds complexity and testing burden.

Finally, there is the cost of debugging prefetch issues. Standard profiling tools like perf stat show cache miss rates, but they don't tell you which lines were prefetched and evicted. You need to use hardware performance counters that track prefetch requests (e.g., L2_LINES_IN.PF on Intel) and compare them to demand accesses. This requires careful scripting and interpretation, and many teams don't have the expertise. The long-term solution is to build a performance regression test that monitors prefetch efficiency and alerts when it drops.

Automating Layout Validation

We've seen teams adopt tools like pahole (for struct layout analysis) and custom scripts that check for alignment and hot-cold separation. Integrating these into CI prevents drift. For example, you can write a Python script that parses debug info and verifies that all hot fields are within the first cache line of each struct, and that the struct size is a multiple of 64. If a commit violates the rule, the build fails. This is heavy-handed, but it works.

When NOT to Use This Approach

Cache-line splitting and SoA conversion are not universal solutions. They add complexity, increase memory usage (due to padding and separate allocations), and can hurt performance if the prefetcher is not the bottleneck. Avoid these techniques when:

• The working set fits in L1 cache. If all your hot data fits in 32 KB per core, there's no need to split. The prefetcher will be idle anyway.
• Access patterns are truly random. If your access pattern has no spatial locality (e.g., random hash table lookups), prefetchers cannot help, and layout changes will have minimal effect. Focus on reducing the number of accesses instead (e.g., using bloom filters).
• The code is not performance-critical. If the function runs once per second or less, the optimization effort is better spent elsewhere. Profile first.
• The platform is embedded or has limited memory. Padding and separate allocations waste memory. On systems with tight memory budgets, the trade-off may not be worth it.
• You are using a garbage-collected language. In Java or Go, the runtime controls object layout and allocation order, and you have limited control. You can use value types (e.g., Java's record or Go's structs) but the GC may move objects, breaking alignment assumptions.

Another important caveat: don't optimize for a single microbenchmark. Many teams have tuned their code to run well on a synthetic test that uses a small dataset, only to see worse performance on production data. Always test with representative data sizes and access patterns.

Alternatives to Layout Tuning

If the conditions above apply, consider other approaches: algorithm changes (e.g., using a hash table instead of a tree), data compression (to reduce working set size), or prefetcher control (e.g., disabling the L2 prefetcher on Intel via MSR). Disabling prefetchers is a last resort, but it can help when the prefetcher is doing more harm than good—for example, in pointer-chasing workloads where the prefetcher fills the cache with useless lines.

Open Questions and FAQ

Q: How do I know if my workload is prefetch-dominated?
A: Look at the ratio of prefetch requests to demand requests. On Intel, use perf stat -e l2_rqsts.pf_hit,l2_rqsts.pf_miss. If prefetch misses are a significant fraction of total L2 misses (>30%), the prefetcher is likely causing pollution. Also check if L1 hit rate is high (>95%) but L2 hit rate is low (<80%).

Q: Does hyperthreading affect prefetch behavior?
A: Yes. Two logical cores sharing an L2 cache can cause prefetch interference. The prefetcher on one thread may fill lines that the other thread needs, or evict lines from the other thread. In hyperthreaded environments, consider pinning threads to separate physical cores if possible, or use per-thread data structures that are cache-line-aligned.

Q: Should I use huge pages for prefetch-dominated workloads?
A: Usually yes. Huge pages reduce TLB misses and allow the prefetcher to run further ahead without TLB pressure. However, they can also increase prefetch pollution because the prefetcher has a larger address space to speculate into. Test both 2 MB and 1 GB pages.

Q: How do I measure prefetch efficiency?
A: Compare the number of prefetch requests that result in a cache hit vs. a miss. On Intel, l2_rqsts.pf_hit and l2_rqsts.pf_miss give you this ratio. Also look at l2_lines_in.pf to see how many lines are filled by prefetch. A high hit rate (>90%) means the prefetcher is working well; a low hit rate (<50%) means it's polluting.

Q: Can I use the same layout for both Intel and AMD?
A: Not always. AMD's prefetchers are generally less aggressive and more sensitive to stride patterns. We've seen cases where an Intel-optimized layout (with aggressive padding) performed worse on AMD because the prefetcher didn't fill enough lines. Profile on both platforms if your code runs on heterogeneous hardware.

Common Mistakes in Practice

One mistake is applying SoA conversion to every struct without measuring. Another is forgetting to update the allocator: if you switch to SoA but still use malloc for each array, the arrays may be scattered in memory, defeating the purpose. Use a custom allocator that places the arrays contiguously. Finally, many engineers forget about alignment: even if you split hot and cold fields, if the hot fields are not 64-byte aligned, they may still span two cache lines. Always check alignment with alignof and offsetof.

Summary and Next Experiments

Cache miss anatomy in prefetch-dominated workloads is about understanding what the hardware prefetcher is doing with your memory layout—and then reshaping that layout to feed it the right data. The three key actions are: (1) separate hot and cold fields into different cache lines, (2) align hot fields to 64-byte boundaries, and (3) ensure allocation order matches access order. Start by profiling your current code to identify which cache level has the most prefetch misses, then apply one change at a time and measure.

Next experiments to try:

• Add padding to your hot structs to make the access stride match the cache line size (64 bytes). Measure L2 miss rate before and after.
• Convert one critical struct from AoS to SoA with hot-cold splitting. Profile L1 and L2 misses.
• Use huge pages (2 MB) and compare prefetch miss rates.
• Disable the L2 prefetcher (via MSR) and measure the change in total runtime—this tells you if the prefetcher is helping or hurting.
• Add compile-time assertions to prevent layout drift, and integrate them into your CI pipeline.

The goal is not to eliminate all cache misses—that's impossible—but to ensure that every prefetched line is actually used. With the techniques in this guide, you can turn the prefetcher from a liability into an asset.