C++ Cache Optimization: Locality, False Sharing, SoA vs AoS

Why cache behavior dominates real-world C++ performance

Modern CPUs run at roughly 3–5 GHz, which means a core can execute an instruction every fraction of a nanosecond. Main memory (DRAM), by contrast, has a latency of somewhere around 60–100 nanoseconds for a full round trip. That gap — often called the “memory wall” — means a single cache miss can cost the equivalent of 200–300 wasted CPU cycles where the core sits idle waiting for data. No amount of algorithmic cleverness saves you if your data layout forces the CPU to stall on memory fetches constantly. This is why two implementations of the same algorithm, with the same asymptotic complexity, can differ in wall-clock time by 5–10x purely based on how their data is laid out in memory.

The CPU doesn’t fetch memory one byte or one variable at a time. It fetches whole cache lines — contiguous 64-byte chunks on virtually every modern x86-64 and ARM64 chip — into a hierarchy of L1 (fastest, smallest, per-core), L2 (per-core or shared per cluster), and L3 (shared across all cores, slowest of the three but still far faster than DRAM). Cache optimization, at its core, is about arranging your data and access patterns so that once a cache line is pulled in, you use as much of it as possible before it gets evicted, and so that multiple cores don’t fight over the same line.

Spatial locality: why iteration order changes everything

// ❌ Many cache misses (column-major stride in row storage)
for (int j = 0; j < cols; ++j) {
    for (int i = 0; i < rows; ++i) {
        sum += matrix[i][j];
    }
}
// ✅ Better spatial locality (row-major scan)
for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < cols; ++j) {
        sum += matrix[i][j];
    }
}

matrix[i][j] in a C++ 2D array (or a std::vector<std::vector<int>> flattened row by row) is stored row by row in memory. When the inner loop walks j, consecutive iterations touch adjacent bytes — the hardware prefetcher recognizes this stride-1 pattern and starts pulling in the next cache lines before you even ask for them. When the inner loop instead walks i while j is fixed, each access jumps cols * sizeof(int) bytes ahead, which for anything but a tiny matrix lands in a completely different cache line — often a different page — every single time. You pay a full cache miss on almost every access. For a 2048x2048 int matrix this single loop-order swap alone is commonly a 5-20x speedup, entirely from memory access pattern, with zero change to the actual arithmetic.

std::vector<int> v(1000);
// ✅ Sequential access
for (int i = 0; i < v.size(); ++i) {
    process(v[i]);
}
// ❌ Random access pattern
for (int i = 0; i < v.size(); ++i) {
    process(v[rand() % v.size()]);
}

The same principle applies to a flat std::vector. Sequential access lets the prefetcher stream ahead of you. Random access defeats prefetching entirely and, once the vector no longer fits in L2, turns every access into a potential DRAM round trip. The takeaway isn’t “always iterate sequentially” — sometimes your problem genuinely requires random access — but that you should be aware of the cost and, when the access pattern is under your control, prefer the one that keeps memory traffic sequential.

Measure first: don’t guess with cache behavior

Before you rewrite anything for “cache friendliness,” profile. Intuitions about cache behavior are frequently wrong, especially once you factor in the hardware prefetcher, TLB effects, and out-of-order execution hiding some of the latency behind other work. On Linux, perf stat -e cache-misses,cache-references,LLC-load-misses ./your_binary gives you hard numbers instead of guesses. perf record + perf report (or perf c2c specifically for false-sharing detection across cores) will point at the actual hot instructions. valgrind --tool=cachegrind simulates the cache hierarchy and gives you a miss-rate breakdown per function, which is invaluable when you don’t have access to hardware performance counters (e.g., in some virtualized CI environments). On other platforms, Intel VTune or AMD uProf give equivalent, often friendlier, visualizations. The point of all this tooling is that “cache-friendly” code that isn’t actually the hot path is wasted engineering effort — profile first, optimize the function that’s actually costing you cycles, and re-measure afterward to confirm the change helped rather than just changed the bottleneck.

Matrix Multiply, Struct Layout, Prefetching, and Tiling

Matrix multiply

// ❌ Cache-unfriendly (strided access into B)
void matmul_slow(int** A, int** B, int** C, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}
// ✅ Better with transposed B for sequential reads
void matmul_fast(int** A, int** B, int** C, int n) {
    int** BT = transpose(B, n);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                C[i][j] += A[i][k] * BT[j][k];
            }
        }
    }
}

In matmul_slow, the innermost loop over k walks B[k][j] — a fixed column, incrementing the row index. Because B is stored row-major, that means every iteration jumps n * sizeof(int) bytes, blowing through a fresh cache line almost every time for any reasonably sized n. Transposing B once up front (an O(n²) cost, negligible next to the O(n³) multiply) turns that inner-loop access into BT[j][k], which is now a sequential row scan — exactly the access pattern the cache hardware is built to reward. This is a textbook case of paying a small, fixed transformation cost to make the dominant cost sequential.

Struct layout

// ❌ Padding / cache-line waste
struct Bad {
    char a;
    int b;
    char c;
    long d;
};
// ✅ Tighter packing (example; align to your ABI needs)
struct Good {
    long d;
    int b;
    char a;
    char c;
};

The compiler inserts padding bytes between members so that each field starts at an address satisfying its own alignment requirement (an int typically needs 4-byte alignment, a long 8-byte). In Bad, char a (1 byte) is followed by 3 padding bytes before int b can start on a 4-byte boundary, and another few padding bytes creep in before long d. Reordering members from largest alignment requirement to smallest, as in Good, lets the compiler pack the two chars together at the tail, cutting padding significantly — on a typical 64-bit ABI, Bad is 24 bytes and Good is 16 bytes for the same four fields. Smaller structs mean more of them fit per cache line, which matters a lot when you’re iterating over a std::vector<Bad> versus std::vector<Good> — fewer cache lines touched per pass over N elements. That said, don’t chase this blindly: if a field genuinely needs a specific alignment for SIMD loads (alignas(32) for AVX, for instance), reordering to save four bytes isn’t worth breaking that. Use sizeof() and, if you want the compiler to tell you exactly where the gaps are, -Wpadded (Clang) or manual inspection with offsetof.

Prefetching

#include <xmmintrin.h>
void processWithPrefetch(int* data, int n) {
    constexpr int prefetchDistance = 64;

    for (int i = 0; i < n; ++i) {
        if (i + prefetchDistance < n) {
            _mm_prefetch(&data[i + prefetchDistance], _MM_HINT_T0);
        }
        process(data[i]);
    }
}

_mm_prefetch is a hint, not an instruction that blocks or guarantees anything — it asks the memory subsystem to start pulling a cache line in ahead of when you’ll actually need it, so that by the time execution reaches data[i], the line is already resident instead of triggering a miss. The prefetchDistance constant has to be tuned: too small and the data isn’t ready by the time you use it (the prefetch does nothing useful); too large and you evict cache lines you’ll need soon, or issue prefetches for data you’ll never reach if the loop exits early. In practice, manual prefetching earns its complexity in a narrower set of cases than people expect. Modern hardware prefetchers already detect simple sequential and even fixed-stride access patterns and prefetch automatically — so for a plain sequential scan like the one above, _mm_prefetch often measures as a wash or even a slight net negative because the extra instructions and the risk of cache pollution eat the gain. Manual prefetch earns its keep in less regular but still-predictable patterns: e.g., walking a fixed-stride array where the stride is larger than what the hardware prefetcher tracks, or software pipelining a linked structure where you know one hop ahead. Always A/B it with perf stat -e cache-misses before and after — I’ve seen manual prefetch calls left in codebases from years-old “optimization passes” that measurably do nothing on current hardware, because the microarchitecture that motivated them has since improved its automatic prefetcher.

Blocked (tiled) multiply

void matmul_blocked(int** A, int** B, int** C, int n, int blockSize) {
    for (int i = 0; i < n; i += blockSize) {
        for (int j = 0; j < n; j += blockSize) {
            for (int k = 0; k < n; k += blockSize) {
                for (int ii = i; ii < std::min(i + blockSize, n); ++ii) {
                    for (int jj = j; jj < std::min(j + blockSize, n); ++jj) {
                        for (int kk = k; kk < std::min(k + blockSize, n); ++kk) {
                            C[ii][jj] += A[ii][kk] * B[kk][jj];
                        }
                    }
                }
            }
        }
    }
}

Even with B transposed, a naive triple loop over a large matrix will still thrash the cache once the matrices no longer fit in L2 — you end up re-reading rows of A and B from further-out cache levels (or DRAM) repeatedly as the working set exceeds cache capacity. Blocking (also called tiling) restructures the iteration so that each block of blockSize x blockSize submatrices fits entirely within L1 or L2 while it’s being worked on, before moving to the next block. This trades a slightly more complex loop nest for a dramatically smaller working set per phase of computation — the CPU reuses data already sitting in a fast cache level instead of re-fetching it. Picking blockSize is itself an exercise in knowing your target cache size (a common starting point is choosing blocks so that 2-3 blocks’ worth of int data fit in L1, which is typically 32KB per core) and then measuring rather than assuming.

Aligning to the 64-Byte Cache Line

constexpr size_t CACHE_LINE_SIZE = 64;
alignas(CACHE_LINE_SIZE) int data[16];
struct alignas(CACHE_LINE_SIZE) Counter {
    std::atomic<int> value{0};
};

Aligning a hot data structure to the cache line boundary guarantees it starts at the beginning of a line rather than straddling two lines, which would otherwise force two separate fetches (and two potential misses) for what should be a single access. This matters most for structures accessed extremely frequently in tight loops or under contention — for a rarely-touched struct, the alignment gain is immaterial and the extra padding is pure waste.

Diagram: how false sharing bounces a cache line between cores

The mechanism behind false sharing is the cache-coherence protocol (MESI or a variant) that keeps every core’s view of memory consistent. When one core writes to any byte within a cache line, every other core holding a copy of that line has to invalidate it — even if the other core was reading or writing a completely different variable that just happens to share the line.

sequenceDiagram
    participant Core0
    participant CacheLine as Shared 64B Line
    participant Core1

    Core0->>CacheLine: Write counters[0]\n(line loaded Exclusive)
    CacheLine->>Core1: Invalidate cached copy
    Core1->>CacheLine: Write counters[1]\n(must re-fetch line first)
    CacheLine->>Core0: Invalidate cached copy
    Core0->>CacheLine: Write counters[0] again\n(re-fetch, still contended)
    Note over Core0,Core1: Line ping-pongs between cores\neven though counters[0] and counters[1]\nare logically independent

Both cores are doing “independent” work on their own counters, yet the hardware has to serialize every write because they physically share one 64-byte block — this is the entire false-sharing problem in one picture, and it’s why the fix is purely about memory layout, not logic.

False Sharing, Large Strides, AoS vs SoA, and SIMD Alignment

False sharing

// ❌ false sharing
std::atomic<int> counters[4];
// ✅ pad to separate cache lines
struct alignas(64) PaddedCounter {
    std::atomic<int> value{0};
};
PaddedCounter counters[4];

Four std::atomic<int> packed tightly into an array easily fit within a single 64-byte cache line (4 bytes each, 16 bytes total). If four different threads each increment one of those counters, every single increment invalidates the line for the other three threads, even though none of them are logically touching each other’s data — you get the memory-traffic cost of heavy contention with none of the actual data dependency that would justify it. Padding each counter out to its own cache line via alignas(64) fixes this at the cost of memory: 4 counters now occupy 256 bytes instead of 16. That tradeoff — burn cache footprint to eliminate contention — is almost always worth it for anything incremented from multiple threads at high frequency; it’s a bad idea for counters accessed rarely, where the wasted cache footprint has a real cost (more lines competing for the same L1/L2 capacity) and no offsetting benefit.

Large stride

for (int i = 0; i < n; i += 1000) {
    process(data[i]);
}

A stride large enough that consecutive accesses land in different cache lines (and often different pages) defeats both spatial locality and the hardware prefetcher’s stride detection once the stride exceeds what it tracks. If the algorithm genuinely needs to sample sparsely, there’s often nothing to fix; the pitfall is when a large stride is an accident of data layout (e.g., iterating a “column” of a row-major structure) rather than a real requirement — in that case, the fix is usually to change the layout, not the loop.

AoS vs SoA

// ❌ AoS: may scatter hot fields
struct Particle {
    float x, y, z;
    float vx, vy, vz;
};
std::vector<Particle> particles;
// ✅ SoA: sequential access per field
struct Particles {
    std::vector<float> x, y, z;
    std::vector<float> vx, vy, vz;
};

Array-of-structs (AoS) is the natural, object-oriented way to model a particle, and it’s the right default: it’s easier to read, easier to pass a single particle around, and if your code touches most fields of each particle together (e.g., a full physics update per particle), AoS actually has better locality — one cache-line fetch gets you x, y, z, vx, vy, vz all at once. Struct-of-arrays (SoA) wins when your hot loop only touches one or two fields across the whole collection — e.g., a pass that only updates x positions from vx velocities. With AoS, that pass would fetch entire Particle structs into cache and use only a fraction of each cache line’s bytes, wasting bandwidth. With SoA, the x and vx arrays are each fully packed and sequential, so every byte fetched is used, and the layout is also directly amenable to SIMD vectorization (loading 8 floats into an AVX register from a contiguous x array is trivial; doing the same from an AoS layout requires a gather). The real-world rule of thumb: default to AoS for readability, and only convert to SoA for specific hot loops once profiling shows the field-scattering cost is real — converting a whole codebase to SoA preemptively is a readability and maintenance cost you often don’t need to pay.

Alignment for SIMD

float* alignedData = (float*)aligned_alloc(32, 100 * sizeof(float));
__m256 v = _mm256_load_ps(alignedData);

AVX’s aligned load intrinsics (_mm256_load_ps) require 32-byte alignment and will fault (or, on some older compilers/paths, silently do something wrong) on unaligned data — the unaligned counterpart _mm256_loadu_ps works on any address but can be measurably slower on older microarchitectures, though the gap has narrowed considerably on recent Intel/AMD chips. aligned_alloc (C++17, <cstdlib>) gives you a guaranteed-aligned allocation; for std::vector, you’d need a custom aligned allocator since the default std::allocator doesn’t guarantee anything beyond alignof(T).

Hot/cold splitting: keep the fields you loop over together

A struct often mixes fields that are read on every iteration (position, velocity, an active flag) with fields that are touched rarely (a name, debug info, creation time). When the loop only needs the hot fields, every cache line it loads is still mostly filled with cold data, so the effective bandwidth drops by the ratio of cold to hot bytes. Hot/cold splitting moves the rarely used fields into a separate struct, reached through an index or pointer, so the array the hot loop walks contains only what it reads:

struct ParticleCold { std::string name; std::chrono::system_clock::time_point created; };
struct Particle {           // 16 bytes: four per 64-byte cache line
    float x, y, vx, vy;
};
std::vector<Particle> hot;       // walked every frame
std::vector<ParticleCold> cold;  // same index, touched rarely

It is a milder form of the SoA transformation: the object stays an object from the code’s point of view, but its memory is arranged around the access pattern. Measure before and after, as with every change in this article. Splitting helps when the hot loop dominates and the cold part is large; it costs an extra lookup whenever code needs both parts.

Cache-hostile data structures: why pointer-chasing hurts

A std::list<T> or a naively pointer-linked std::map/binary tree is, from a cache-locality standpoint, close to a worst case. Each node is a separate heap allocation, and there is no guarantee — usually there’s an active guarantee against — consecutive nodes being anywhere near each other in physical memory. Walking such a structure means each ->next or child pointer dereference is a fresh, unpredictable address that the prefetcher has no way to anticipate; you pay close to a full cache-miss latency per node. Compare that to std::vector<T> or std::deque<T>, where advancing to the next element is almost always already in cache because it was just fetched alongside the current element.

This is the well-known reason std::vector frequently outperforms std::list even for workloads that look, on paper, tailor-made for a linked list — frequent middle insertions and removals. The O(1) insertion of std::list is real, but each of those O(1) operations is a cache miss, while std::vector’s O(n) shift is a tight, sequential memmove that the CPU executes at close to memory-bandwidth speed with excellent prefetching. Unless N is large enough and insertion-heavy enough that the asymptotic advantage actually overcomes the constant-factor cache penalty — which in practice takes a surprisingly large N — std::vector wins the benchmark. The same logic extends to trees: a cache-friendly B-tree-like structure (grouping several keys per node so a single cache-line fetch does more comparison work) routinely beats a classic binary search tree for exactly this reason, which is part of why std::map’s red-black tree loses microbenchmarks against flat, sorted-vector-based associative containers (like absl::btree_map or a hand-rolled sorted vector + binary search) for read-heavy workloads.

Branch prediction and cache effects compound

Cache misses don’t happen in isolation from branch mispredictions — they interact. A CPU executing speculatively past a predicted branch can be doing useful prefetching work (effectively hiding cache latency behind speculative execution) if the prediction is correct, but a misprediction throws away that speculative work and forces a pipeline flush right as a cache miss may also be resolving, compounding the stall. Code with unpredictable branches and poor cache locality (e.g., traversing a tree with data-dependent branches inside a loop over scattered heap nodes) suffers a multiplicative penalty, not merely additive — the CPU can’t hide the cache latency behind speculation because it doesn’t know which way the next branch goes. This is one reason branch-free, data-oriented rewrites (replacing an if-heavy dispatch with a lookup table or arithmetic, laid over contiguous data) sometimes deliver bigger wins than either optimization alone would predict.

When cache optimization conflicts with readability

Not every hot path deserves this treatment, and treating “more cache-friendly” as an unconditional good is itself a mistake. Manually reordering struct members to save padding, converting AoS to SoA, or hand-writing blocked loops all cost future readers comprehension time and cost you maintenance risk (SoA in particular tends to spread what was one logical entity across five parallel arrays that must always stay in sync — a bug class AoS simply doesn’t have). The standard “premature optimization” caution applies directly here: profile to find out whether the function is actually hot enough, on your actual data sizes, for the cache effect to matter; a struct that lives in a std::vector of 20 elements accessed once per frame does not need cache-line surgery, no matter how satisfying the micro-benchmark on a synthetic 10-million-element array looks. Reserve these techniques for code that profiling has already identified as both hot and memory-bound (as opposed to compute-bound or I/O-bound, where cache layout changes won’t move the needle at all).

From production: a false-sharing bug that only showed up under real concurrency

I once spent the better part of a day chasing a throughput regression in a multi-threaded stats-collection module. Four worker threads each incremented their own std::atomic<uint64_t> counter in a tight per-request hot path, and the code looked completely reasonable — no shared mutable state, no locks, no obvious contention. Yet the number of requests processed per second dropped noticeably as soon as we scaled from one worker thread to four, which made no sense for what should have been perfectly parallel, independent work. perf stat -e cache-misses on the four-thread run showed a cache-miss rate several times higher than the single-thread baseline scaled by four, which was the first hint something structural was wrong rather than a logic bug. Running perf c2c (cache-to-cache) confirmed it directly: the four counters were declared as a plain std::atomic<uint64_t> counters[4] — 32 bytes total, comfortably inside one 64-byte cache line — so every increment from any thread invalidated the line for the other three. The fix was exactly the padding pattern shown earlier in this post: wrapping each counter in an alignas(64) struct. Throughput on the four-thread run went up by roughly 3x after that one change, with literally zero change to the actual counting logic. What stuck with me from that debugging session is how innocent the original code looked — nothing in a code review would have flagged std::atomic<uint64_t> counters[4] as wrong, because the bug isn’t in the logic at all, it’s purely in the physical memory layout relative to how the hardware cache-coherence protocol works. That’s exactly the class of bug you can’t spot by reading code; you need a profiler that understands cache-line-level behavior to even see it.

On a separate occasion, we tried the opposite move — converting a hot particle-simulation loop from AoS to SoA, expecting a clean win because the loop only touched position and velocity fields, not the particles’ other metadata. The SIMD-friendly SoA version was indeed faster in isolation, but it made a different part of the pipeline — a per-particle collision callback that needed several unrelated fields together — noticeably slower, because that code now had to gather values from five separate arrays instead of reading one contiguous struct. Net effect on the full pipeline was close to a wash, and we reverted it after profiling the whole frame rather than just the microbenchmarked loop. That’s the concrete lesson behind the “measure the whole system, not just the hot loop you’re staring at” advice above — SoA is a layout decision that affects every consumer of the data, not just the one loop you’re trying to speed up.

FAQ

Q1: What is cache optimization?

A: Arranging data layout and access patterns so the CPU reuses cache-resident data instead of stalling on DRAM fetches — the goal is minimizing cache misses on the paths that actually run hot.

Q2: What is spatial locality?

A: Accessing nearby memory addresses in sequence, so that once a cache line is fetched, subsequent accesses land inside the same line instead of triggering new fetches.

Q3: What is false sharing?

A: Independent variables that happen to sit on the same cache line get invalidated by each other’s writes across cores, even though there’s no real data dependency — fix with padding or per-thread-line layout.

Q4: AoS vs SoA — which should I default to?

A: AoS (array of structs) for readability and when most fields are touched together; SoA (struct of arrays) for SIMD-heavy hot loops that only touch a subset of fields across the whole collection — measure before converting.

Q5: When does manual prefetching actually help?

A: Mainly for predictable-but-irregular access (fixed strides larger than the hardware prefetcher tracks, or one-hop-ahead linked traversal). For plain sequential loops, the hardware prefetcher usually already has it covered — verify with perf stat before keeping a manual prefetch call.

Q6: How do I know whether a function is even cache-bound before optimizing it?

A: Profile with perf stat -e cache-misses,cache-references or valgrind --tool=cachegrind first. If cache-miss rate is low or the function is compute-bound (CPU-bound on arithmetic, not memory), cache-layout changes won’t help and aren’t worth the readability cost.

Related articles

• C++ memory alignment, padding, and false sharing
• C++ Custom Allocators for STL Containers: Pool, Stack, Tracking Allocators and PMR
• Cache-Friendly C++: Data Locality, Struct Layout, AoS vs SoA and False Sharing
• Profiling C++ Before Optimizing: perf, gprof, Flame Graphs and Finding the Real Bottleneck