Data layout and mechanical sympathy: the cache

By Lesson 07 you can express ownership in the type — who frees a resource, and when, is now answered. This lesson answers a different question the high-level languages also hid: where, physically, does your data sit, and what does it cost to reach it? The new idea is mechanical sympathy — that the CPU is not a uniform-cost machine that treats every memory access the same. It has a layered memory system, and code that respects the layout of that system runs ten to a hundred times faster than code that ignores it, with identical big-O. This is the lesson that turns "where does the memory live?" from a correctness question into a performance one — and it is the reason a vector beats a list (Lesson 13).

1 · Struct layout: alignment and padding

In Lesson 02 you learned that every object is a typed region of storage with a size you can query with sizeof. A struct (a record type that groups several members) is laid out by placing its members in declaration order at increasing addresses. But the members are not packed tightly. Each type has an alignment requirement: a constraint that an object of that type must start at an address that is a multiple of some number (its alignment). On a typical 64-bit machine an int (4 bytes) must start at an address divisible by 4, a double or pointer (8 bytes) at one divisible by 8, a char (1 byte) anywhere. Hardware wants this because an aligned load fits in a single memory transaction; a misaligned one can take two.

To satisfy alignment, the compiler inserts unused bytes called padding between members (and at the end). Padding is dead weight — it inflates sizeof, wastes cache, and you usually never asked for it. The fix is free: reorder members from largest alignment to smallest, so each one falls naturally on its boundary with no gaps.

// As declared: char, double, int — alignment forces gaps.
struct Bad {
    char  a;   // offset 0,  1 byte
    // 7 bytes of PADDING here, so 'b' lands on an 8-aligned address
    double b;  // offset 8,  8 bytes
    int    c;  // offset 16, 4 bytes
    // 4 bytes of PADDING at the end, so an array of Bad keeps b aligned
};               // sizeof(Bad) == 24

// Reordered: largest alignment first. No internal gaps.
struct Good {
    double b;  // offset 0,  8 bytes
    int    c;  // offset 8,  4 bytes
    char   a;  // offset 12, 1 byte
    // 3 bytes of PADDING at the end -> total is a multiple of 8 (the
    //   largest member alignment), so arrays stay aligned.
};               // sizeof(Good) == 16

You can verify any of this: static_assert(sizeof(Good) == 16); compiles, static_assert(sizeof(Bad) == 24); compiles, and alignof(double) is 8. The rule to internalize: order struct members from largest to smallest alignment. It costs nothing and often shrinks the type.

2 · The memory hierarchy: not one memory, but five

A high-level language presents memory as a flat, uniform array of bytes — every access the same cost. That is a lie of convenience. Real hardware has a memory hierarchy: a stack of progressively larger and slower storage, each level a cache for the one below it. The CPU's registers (a few dozen named slots inside the core, where arithmetic actually happens) are fastest; then three levels of on-chip cache (L1, L2, L3 — small, fast SRAM holding recently-used data); then main memory, DRAM — large, cheap, and dramatically slower. Rough numbers for a modern desktop core:

The headline: a load that hits L1 is roughly 100 times faster than one that misses all the way to DRAM. (These numbers vary by CPU; the ratios are the durable part.) Put it in human scale: if an L1 hit took one second, a DRAM access would take about a minute and a half. The CPU does not stand idle for that minute and a half if it can help it — but when it genuinely needs a value that is only in DRAM, it stalls, doing nothing useful while the bytes travel. Performance work is, to a first approximation, the work of avoiding those stalls. Big-O counts operations; mechanical sympathy counts where the operands were.

3 · The cache line: reading one byte pulls in 64

The cache does not move individual bytes. It moves cache lines — fixed-size blocks, almost universally 64 bytes, aligned to 64-byte boundaries. When you read a single char and it is not already cached, the CPU fetches the entire 64-byte line containing it from DRAM into L1. So one byte's worth of intent costs one line's worth of traffic — but the 63 neighbours come along for free, already in fast cache.

This single fact explains nearly all of performance layout. If your next access is to a neighbouring byte, it is already in cache — a hit. If your next access jumps to a random faraway address, it is a fresh line fetch — a miss. So the question that decides speed is: does my access pattern stay within lines I've already pulled in? Sixteen ints (16 × 4 = 64 bytes) fit in one line: one miss buys you fifteen free hits. This is why the Good struct from §1 matters — a smaller struct packs more useful elements per line and wastes fewer bytes on padding that the CPU still has to drag through cache.

4 · Contiguous beats pointer-chasing — and the prefetcher

Contiguous data means the elements sit one after another in memory, no gaps — like the elements of an array or a std::vector's backing block. Walking it touches address p, then p+stride, then p+2·stride — a steady linear march. The hardware has a second weapon for exactly this pattern: the prefetcher, a unit that watches the stream of addresses, detects "this code is marching forward at a fixed stride," and fetches the next lines into cache before the program asks. With a working prefetcher, a linear scan of an array can run with almost no stalls at all — the data arrives just in time.

Pointer-chasing is the opposite. A linked structure — say a std::list — stores each element in its own separately-allocated node, and you reach the next element by following a pointer stored in the current one. The addresses are scattered across the heap (each node came from a separate allocation, Lesson 04). Three things go wrong at once: (1) every node is likely a fresh cache miss, because nodes are not neighbours; (2) the prefetcher cannot help — it cannot predict the next address, because that address is the data it hasn't fetched yet (you must load node N to learn where node N+1 is — a dependency chain); and (3) each node carries pointer overhead (16+ bytes of next/prev per element) that bloats the footprint and wastes cache lines. A linked list is a machine for generating cache misses.

5 · Array-of-Structs vs Struct-of-Arrays

When you store many records, you have a layout choice the language makes explicit. Array-of-Structs (AoS) is the obvious one: a single array where each element is a full record. Struct-of-Arrays (SoA) splits each field into its own contiguous array. Same data, transposed.

struct Particle { float x, y, z;  float vx, vy, vz;  float mass; };

// AoS: one array, fields of a record interleaved in memory.
std::vector<Particle> aos;        // ...x y z vx vy vz mass | x y z ...

// SoA: one array per field, each contiguous.
struct Particles {
    std::vector<float> x, y, z, vx, vy, vz, mass;
};
Particles soa;                    // x x x x ... | y y y y ... | ...

Which wins depends entirely on the access pattern. Suppose a step of physics needs to update only the positions from the velocities — it touches x,y,z,vx,vy,vz but never mass. With AoS, every cache line you pull in to get a particle's x also drags in that particle's mass — bytes you will not use this pass, wasting a slice of every 64-byte line. With SoA, the x array is pure positions, packed tight: every byte of every fetched line is data you will actually touch, so you get the maximum useful elements per line, and SIMD vector instructions (which want 4/8/16 contiguous floats) apply cleanly. Here SoA wins — often markedly — because it raises the fraction of each cache line that is useful.

The deciding question is always the same cache-line question from §3: of the 64 bytes a fetch pulls in, how many will this loop actually use? AoS and SoA are two answers; you pick by access pattern, not by taste.

6 · Worked payoff — sum an array vs a linked list of the same N

Make the abstraction concrete with the simplest possible task: sum N = 1,000,000 integers, stored two ways.

long sum_vec(const std::vector<int>& v) {        // contiguous
    long s = 0;
    for (int x : v) s += x;                       // linear march, prefetchable
    return s;
}

long sum_list(const std::list<int>& lst) {        // pointer-chasing
    long s = 0;
    for (int x : lst) s += x;                      // follow next-pointer each step
    return s;
}

Now the cache-miss arithmetic. An int is 4 bytes, so a 64-byte line holds 16 of them.

So the list does about 16× more cache-line fetches, and worse, none of them prefetch — the loop sits stalled ~100 ns at each node waiting to learn where the next node is. In practice the vector sum runs on the order of 10–50× faster, despite both loops being textbook O(n) with one add per element. The work is identical; the memory walk is not. This — plus the padding arithmetic of §1 — is the whole content of "mechanical sympathy," and it is precisely why Lesson 13 makes std::vector the default container and treats std::list as a special-case tool.

Common mistakes / failure modes

Checkpoint exercise

Where this points next

We now have the cost of reaching data. The next question is the cost of abstracting it: when you wrap data in a class with methods, do you pay for the wrapper? Lesson 09 makes the zero-overhead principle concrete at the call level — it shows that a non-virtual method is compiled into a plain function call with a hidden this pointer, no slower than a free function, so encapsulation in C++ is genuinely free. That sets up Lesson 10, where we meet the one form of abstraction you do pay for — the virtual call — whose cost, fittingly, includes the cache miss this lesson just taught you to fear.

Interview prompts

• A struct has a char, a double, and an int in that order — what is its size and how do you shrink it? (§1 — 24 bytes due to padding; reorder largest-alignment-first (double, int, char) to get 16; trailing padding keeps array elements aligned.)
• Why is an L1 hit ~100× faster than a DRAM access, and what does the CPU do meanwhile? (§2 — L1 is small fast on-core SRAM (~1 ns / ~4 cycles) vs large slow off-chip DRAM (~100 ns); on a genuine miss the core stalls, doing no useful work, until the bytes arrive.)
• What is a cache line and why does it matter for loops? (§3 — a 64-byte aligned block; the unit of transfer. Reading one byte fetches all 64, so accessing neighbours is free — locality turns one miss into ~15 hits.)
• Why is iterating a std::list so much slower than a std::vector at the same O(n)? (§4, §6 — list nodes are scattered separate allocations → ~1 miss per element, no prefetch (next address unknown until the node loads), plus pointer overhead; vector is contiguous → ~1 miss per 16 ints, fully prefetchable.)
• When does Struct-of-Arrays beat Array-of-Structs? (§5 — when you sweep one/few fields across all records; SoA packs that field contiguously so every fetched line is useful and vectorizes cleanly. AoS wins when you process whole records.)
• What is the prefetcher and why can't it help a linked list? (§4 — hardware that detects a fixed-stride linear access pattern and fetches upcoming lines early; it fails on lists because the next address is data you haven't loaded yet — a dependency chain it cannot predict.)
• What is false sharing, and how is it related to this lesson? (Preview/§3 — two threads writing different variables on the same 64-byte line force cache-coherence ping-pong even with no logical sharing; it is the cache line returning as a concurrency cost — Lesson 17.)