CPU Cache Misses: How Data Layout Causes 6.8x Slowdowns and How to Fix Them

Why CPU Cache Drags Performance

CPU arithmetic takes ~1 cycle, but L1 cache access costs ~4 cycles, L2 ~12 cycles, L3 ~40 cycles, and main memory ~200 cycles — a two-order-of-magnitude latency gap known as the "memory wall." At 2 GHz, a 200-cycle main-memory access stalls the pipeline for ~100 ns. Modern CPUs mitigate this with out-of-order execution and memory-level parallelism, but caches exist to serve recently used and adjacent data with lower latency.

Caches are finite and organized in cache lines (typically 64 bytes). On a miss, the CPU fetches an entire line, not just the requested bytes. This enables spatial locality : sequential access lets subsequent operations reuse the loaded line. Random, strided access wastes bandwidth and increases misses.

Solving Cache Line Conflicts: False Sharing

A 2019 multi-core pipeline used an int results[8] array where each core wrote to its own slot. Single-core throughput was 900M ops/sec, but four cores dropped to 120M ops/sec. No locks were needed (distinct indices), and -O2 was enabled. perf revealed cache-line contention: the 8 integers (32 bytes) fit in one 64-byte line, causing false sharing . Under MESI, each core's write forced the line to bounce between cores.

Fix: Pad each slot to a full cache line:

#define CACHE_LINE 64

struct __attribute__((aligned(CACHE_LINE))) result_slot {
    int value;
    char padding[CACHE_LINE - sizeof(int)];
};

struct result_slot results[8];

Key points: aligned(CACHE_LINE) forces 64-byte alignment; padding expands each struct to 64 bytes so adjacent elements start on separate lines. After the change, four-core throughput rose to 820M ops/sec (~6.8x). The aligned attribute is a GCC extension; verify the target platform's cache-line size.

2.1 Cache Hierarchy Overview

Typical hierarchy (illustrative): per-core L1d/L1i (32 KB, ~4 cycles), per-core L2 (256 KB, ~12 cycles), shared L3 (12 MB, ~40 cycles), main memory (DDR4/5, ~200 cycles). Deeper levels have higher capacity and latency. L1/L2 are usually private; L3 is shared. Exact topology varies by processor.

Analogy: L1 = desk (few books), L2 = nearby shelf, L3 = library, memory = warehouse. Frequent trips to the warehouse kill productivity.

Writing Cache-Friendly Code

1. Don't Put "Fat" Fields in Hot Structs

Embedded sensor struct with a 512-byte log field (8 cache lines) but 99% accesses only temperature. Traversing an array of such structs loads a line per object, mostly unused log data. Splitting hot and cold fields improves cache-line utilization:

// Bad: hot and cold mixed
struct SensorBad {
    uint32_t id;
    float temperature;
    float humidity;
    char log[512];
    uint64_t timestamp;
};

// Good: separate hot and cold
struct SensorHot {
    uint32_t id;
    float temperature;
    float humidity;
    uint64_t timestamp;
};

struct SensorCold {
    uint32_t id;
    char log[512];
};

On x86-64, SensorBad is ~536 bytes (alignment padding), SensorHot ~24 bytes. Traversing temperatures now loads only hot lines. Cold data still cached when accessed, but less frequent. Must maintain correlation via id.

2. Traverse Arrays Row-Major, Not Column-Major

For a 1024×1024 float matrix (row-major, 4 KB/row = 64 cache lines), row-wise loops access contiguous memory, enabling hardware prefetch and full line reuse. Column-wise loops stride 4 KB per access, using only 4 bytes per loaded line. With matrix > L1, column traversal causes many more misses. Measured speed difference can be multiple times, but exact factor depends on hardware, compiler, cache size, and bandwidth. Always benchmark both patterns under identical conditions.

3. Choose SoA vs AoS Based on Access Pattern

10,000 points with x, y, z. AoS : struct Point { float x,y,z; } points[10000]; SoA : separate all_x[10000], all_y[10000], all_z[10000].

If a kernel only reads x, SoA scans a dense all_x array — higher useful data density, better prefetch, easier SIMD vectorization. AoS loads x, y, z together; with 12-byte structs, a 64-byte line holds ~5.33 points, so only ~1/3 of loaded bytes are useful x values. However, if the algorithm needs x, y, z simultaneously per point, AoS keeps them contiguous and may be better. No universal winner; match layout to access pattern. Author learned this through GPU and CPU optimization pain.

Locating Cache Misses

Use perf stat with hardware counters:

perf list | grep -Ei 'L1-dcache|LLC|dTLB'
perf stat -e L1-dcache-loads,L1-dcache-load-misses,LLC-loads,LLC-load-misses,dTLB-load-misses -- ./my_program

Event availability varies by CPU. Focus on L1 load misses, LLC load misses, dTLB load misses. Compute miss ratios, but no universal miss-rate threshold exists . Sequential workloads tolerate higher L1 miss rates; latency-sensitive dependency chains suffer even at low miss rates. Combine counters with wall-time, throughput, and CPU utilization.

High dTLB-load-misses indicates TLB pressure (virtual-to-physical translation misses), not necessarily memory fragmentation. Causes: working set size, page size, access pattern, TLB capacity.

4.1 Finding False Sharing with perf c2c

On supported hardware:

perf c2c record -- ./my_program
perf c2c report

Shows cache-line contention across cores (HITM events). Helps pinpoint which lines cause coherence traffic. Not all CPUs/OSes expose this.

4.2 Cachegrind for Simulated Cache Analysis

Valgrind's Cachegrind simulates I1, D1, LL caches and annotates source lines:

valgrind --tool=cachegrind --cachegrind-out-file=cachegrind.out ./my_program
cg_annotate cachegrind.out

Simulation, not real hardware counts. Good for understanding access patterns; cannot replace on-CPU measurement. madvise hints OS about page access patterns (sequential/random), not direct CPU cache control.

4.3 __builtin_prefetch Usage

Manual prefetch hint:

for (size_t i = 0; i < N; i++) {
    if (N - i > 16) {
        __builtin_prefetch(&data[i + 16], 0, 1);
    }
    data[i] = process(data[i]);
}

Offset 16 means 16 elements ahead (64 bytes for 4-byte elements, 128 bytes for 8-byte). Second arg 0 = read hint, third 1 = low temporal locality. No guarantee of L1 placement or speedup. Optimal distance depends on latency, loop speed, prefetcher, bandwidth. Test multiple distances under identical conditions. Prefetch too early → eviction; too many → bandwidth waste.

A Real Painful Story (2015 ECU)

Signal-processing algorithm (FFT, FIR, filtering) used malloc 'd intermediate buffers with no alignment. CPU usage hit 87%. Two changes: (1) replace malloc with static array + __attribute__((aligned(64))); (2) place FIR coefficients and current data frame in same cache line. CPU dropped to 51% with unchanged algorithm. Demonstrates layout and access impact. Requires before/after benchmarks to attribute gains.

Final Thoughts

Cache is the foundation of high-performance C/C++. Fancy algorithms fail if data layout ignores locality. Author mandates perf stat after coding; if L1 miss rate exceeds team's 10% heuristic, investigate. But 10% is not a universal rule.

System layers (DB, kernel, app) often ignore cache effects. Yet data layout, access order, and sharing at upper layers propagate down to cache behavior. Deep understanding reveals where to save effort and where to invest.

"Your code is not written for the CPU; it's written for the cache." CPU is just the execution engine. Before writing a loop, sketch how data sits in a cache line — five minutes that can save weeks of debugging.