CPU Cache Optimization for Hot Data Structures in C++

Every optimization decision in this piece traces back to one number: 64 bytes. That's the size of a cache line on x86-64 hardware, the atomic unit the memory subsystem moves between DRAM and the CPU. Touch a single byte, and the hardware pulls in the surrounding 64 bytes regardless of what the program asked for. Apple's M-series chips use a 128-byte line instead, same idea, bigger bucket, and that difference affects performance once code has to run on both. What follows is a discipline, not a bag of tricks: layout, padding, and traversal order all fall out of reasoning forward from that single constant, applied to hot loops where memory latency, not raw computation, decides how fast a program runs.

The cost cliff across the memory hierarchy

The numbers most engineers half-remember from a computer architecture course don't describe a gentle slope. L1 cache answers in roughly 4 to 5 cycles, about 1.1 nanoseconds. L2 costs something like 12 to 14 cycles, around 3.3 nanoseconds. L3 runs 40 to 50 cycles, near 12.8 nanoseconds. Main memory, DRAM, costs over 200 cycles, close to 62.9 nanoseconds. Lay those four numbers next to each other and the shape is a cliff. It's a cliff, with a drop-off severe enough that a single blog-cited figure sums it up well: main memory costs roughly 50 times what L1 costs.

That large a ratio is the whole argument for treating layout as a first-class optimization concern rather than an afterthought. No amount of algorithmic cleverness rescues a loop that reliably misses L1 and pays DRAM tax on every iteration; an O(n log n) algorithm with terrible locality will lose to an O(n²) algorithm that stays in cache, at least at the array sizes most real programs actually touch. Everyone already knows caches exist. Ignoring them costs an order-of-magnitude regression that appears as an unglamorous line in a profiler, a function that "should" be fast and isn't, and no obvious reason why until someone checks the access pattern.

How spatial and temporal locality translate the cache-line rule into layout requirements

Spatial locality has a plain-language definition: data used together should live together. Fetch one cache line, and you get the 64 bytes around whatever address you asked for, so if the next thing your loop needs is sitting in that same 64 bytes, it arrives for free. Temporal locality is the companion idea: touch the same address again soon, and it's still sitting in L1 or L2, no re-fetch required.

The failure modes make both principles concrete faster than the definitions do. Pointer-chasing, the kind of traversal a linked list or a tree of heap-allocated nodes forces on you, generates a fresh cache-line fetch at every single hop, because there's no guarantee the next node lives anywhere near the current one in physical memory. Striding through a large array with big gaps between accessed elements is nearly as bad: the hardware still pulls a full 64-byte line for each stride, and most of that line goes unused. Get the access pattern right, and the payoff is substantial: effective cache utilization through spatial and temporal locality can yield improvements in the range of 10 to 100 times over a poorly behaved access pattern. That range is wide because it reflects a ceiling, not a guarantee, and the achievable gain depends entirely on how badly the original access pattern behaved.

Struct layout decisions that follow directly from the 64-byte boundary

Start with something almost every C++ programmer has been bitten by without realizing it: member ordering inside a struct changes its size, because the compiler inserts padding to satisfy alignment rules. The canonical example: a struct holding a char, then an int, then a char, in that order, ends up at 12 bytes, even though the actual data is 6 bytes. Reorder it to int, then char, then char, and it shrinks to 8 bytes. The compiler pads for alignment either way, but the ordering determines how much padding it needs.

It's a packing argument. It's a packing argument. Fewer bytes per instance means more instances fit inside a single 64-byte line, and more of them arrive "for free" the moment the first one is fetched.

Hot and cold field splitting is the same logic applied at a coarser grain. A struct that mixes fields read on every iteration of a hot loop (position, velocity) with fields touched rarely (a texture pointer, some metadata) forces the cache to load the cold bytes every time it loads the hot ones, wasting line capacity on data the loop doesn't need yet. This isn't a novel observation. AMD's patent on the subject (US 8,910,135) describes peeling hot fields into their own structure and placing cold fields into a separate struct, touched only on demand. Chilimbi et al.'s earlier patent (US 6,330,556) formalizes the same idea with a field-affinity graph: fields accessed together get placed in the same cache block, and fields with low affinity to the hot set get split out. Both describe something a compiler can sometimes do automatically, but the reasoning behind it is exactly the kind of thing a programmer should be doing by hand when designing a hot struct, not waiting on a tool to discover it.

Then there's alignment. Misaligned data can straddle two cache lines on a single read, doubling the fetch cost for what should have been one access. The alignas keyword exists precisely to prevent that, forcing a type onto a specified byte boundary. Whether that's alignas(64) or alignas(128) depends on the target: the 128-byte cache line width mentioned earlier for a certain processor family is an actual branch in the design decision at this point, because code tuned for 64-byte lines on x86-64 doesn't automatically get the same benefit on that other architecture.

Order struct members from largest alignment requirement to smallest, split hot fields from cold ones, and check the result with sizeof and offsetof before ever touching a profiler. Verifying the layout costs nothing; guessing at it wastes a profiling session.

When each layout, Array-of-Structs or Struct-of-Arrays, earns its place

Array-of-Structs is the shape most object-oriented code reaches for by default, and it's the right shape when a loop needs every field of an object at once, since the whole struct is in cache together on a single fetch. Struct-of-Arrays flips that: each field gets its own contiguous array, which is the right shape when a loop only touches one or two fields across a large number of objects.

The particle-system example makes the tradeoff concrete. An AoS Particle struct with a Vector3 position, a Vector3 velocity, a float mass, and a Texture* packs the cold texture pointer right alongside the hot motion data, so every fetch during a position-update loop drags in bytes the loop never reads. Split it into std::vector<Vector3> positions, std::vector<Vector3> velocities, std::vector<float> masses, and std::vector<Texture*> textures; the update loop now touches only positions and velocities, so every byte in every fetched cache line is a byte the loop actually uses.

The measured gains back this up: one benchmarking-tool-based measurement puts SoA's improvement at 20 to 30% in specific use cases, and sequential access in general tends to run 5 to 10 times faster than random access. Still, SoA isn't a universal upgrade. It costs code clarity, since an object becomes indices scattered across four arrays instead of one addressable thing, and it makes fetching one complete object slower, since that now means four separate memory reads instead of one. SoA wins when the inner loop is field-uniform across a large population of objects. It loses when the code's natural access pattern is "give me object #42, all of it."

False sharing: when the cache-line boundary creates contention between threads

Layout problems get worse, not better, once threads enter the picture. False sharing happens when two threads each write to a different variable, but those two variables happen to sit inside the same 64-byte cache line. The cache coherency protocol doesn't track individual bytes, it tracks whole lines, so a write by either thread invalidates the entire line for the other core, forcing a reload across the interconnect on every single write.

What makes this bug particularly nasty is that it's invisible in the source. The code looks like clean, independent parallelism, two threads, two variables, no shared state in any logical sense. But the hardware sees one shared cache line and serializes access to it, so the program performs like a single thread with extra overhead, and nothing in a code review will reveal that.

The 128-byte M-series detail from earlier turns out to matter here specifically. Padding a shared variable to 64 bytes to separate it from its neighbor does nothing on a platform with 128-byte lines, both padded variables still land inside the same larger line, and the false sharing persists. C++17 gives a portable fix for exactly this: alignas(std::hardware_destructive_interference_size) on each independently written field. The standard defines destructive_interference_size as the minimum offset needed between two objects to avoid false sharing, and constructive_interference_size as the complementary figure, related to the size that can benefit from true sharing. Using the standard constant instead of a hardcoded 64 is what makes the fix portable across cache-line sizes in the first place.

Access patterns and prefetching when layout alone cannot hide memory latency

Good layout is necessary, but it's also the precondition for something else to work: the hardware prefetcher. Modern CPUs watch for sequential and regular-stride access and speculatively load upcoming cache lines before the program asks for them. A stride-1 walk over a std::vector is exactly the pattern the prefetcher is built to detect, but it only helps when the underlying data is actually laid out that way. Container choice is itself a layout decision, not a separate one.

std::vector is contiguous and prefetcher-friendly by default. std::list scatters nodes across the heap and is close to prefetcher-hostile. std::deque sits in between, chunked into blocks. std::map and std::unordered_map are node-based under the hood, pointer-chasing structures that give the hardware prefetcher nothing regular to latch onto. A sorted flat array searched with binary search often outperforms a tree-based map for read-heavy workloads despite the worse asymptotic elegance of a hash lookup. There's a further trick available for that flat-array case: the Eytzinger layout reorders array elements to better match the access pattern of binary search, turning what is naturally a scattered traversal into something meaningfully more cache-friendly.

Sometimes even that isn't enough, and the access pattern is one the hardware prefetcher genuinely can't anticipate. That's what __builtin_prefetch (available in GCC and Clang) is for: it explicitly loads a cache line ahead of the point where the computation will need it. One benchmark measured a roughly 23.5% speedup when summing elements of a large vector, 8,235,924 nanoseconds without prefetching against 6,301,400 nanoseconds with it. Getting that gain requires tuning: the prefetch has to be issued far enough ahead that the data has time to arrive, but not so far ahead that it gets evicted before the loop reaches it. That distance is workload-specific, and it has to be found empirically, there's no formula that hands it to you.

GCC exposes a coarser version of the same idea with -fprefetch-loop-arrays, which emits prefetch instructions inside loops automatically. It's enabled by default at -O3 and disabled at -Os, and it can be switched on manually at lower optimization levels if a specific loop calls for it.

Applying the discipline end-to-end: data-oriented design and ECS as a worked architecture

Traditional object-oriented design groups data by what it represents, an object's identity holds its fields together regardless of how those fields are actually used at runtime. That's the right call for correctness and for modeling a problem domain, but it's frequently the wrong call for cache behavior: deep inheritance hierarchies, heap-allocated component objects, and virtual dispatch all tend to scatter the data a hot loop needs across memory rather than packing it together.

Data-Oriented Design starts from a different question entirely: instead of asking what an object is, it asks how the data gets processed, and organizes storage around that answer. The cache line becomes the real unit of design.

Entity Component System architecture is DOD applied concretely. An entity is nothing more than a lightweight integer ID, no data and no behavior attached to it directly. Components are plain data structs, stored in contiguous arrays, one array per component type, which is SoA layout enforced at the architectural level rather than left to individual discretion. Systems are the loops: each one iterates over the specific component arrays it needs, touching only the fields relevant to its job, and those fields are already sitting contiguously because the architecture put them there.

Every earlier section's lesson recurs inside ECS, just relocated from struct design to system design. Hot and cold splitting becomes a matter of which component arrays exist: cold data like textures or metadata lives in its own array, never interleaved with hot transform data the physics system iterates every frame. SoA is a structural guarantee rather than a manual choice, since each component type simply is its own array by construction. False sharing gets handled the same way it would in any multithreaded code, partitioning entities per thread and padding shared boundaries with std::hardware_destructive_interference_size. And prefetch-friendly traversal falls out for free: system loops walk contiguous arrays sequentially, which is exactly the access pattern the hardware prefetcher is built to recognize and exploit.

None of this is a trick specific to game engines, even though ECS became popular there first. It's the same 64-byte reasoning from the opening section, carried all the way through to how an entire codebase gets structured. Start from the cache line, and the rest of the discipline, padding, splitting, SoA, alignment, prefetching, is the set of conclusions that constant forces on anyone willing to reason it through. It's the set of conclusions that constant forces on anyone willing to reason it through.