Data layout

Chapter 0.6 showed that the order you visitbytes swings performance by an order of magnitude. But you don't always get to choose the visiting order: the algorithm chooses it. What you always choose is the order the bytes are laid down in the first place. Declaring a struct, picking array-of-structs versus struct-of-arrays, even sequencing fields: each is a locality decision, made before the first instruction runs, that determines which bytes share the 64-byte lines of chapter 0.5. The cache line is the smallest unit of data that moves between cache and memory, so cache-friendly layout means thinking in lines, not variables.¹

First, a rule the compiler enforces behind your back: any primitive object of K bytes must sit at an address that is a multiple of K. A char can live anywhere; a short wants a multiple of 2; an int or float a multiple of 4; a long, double, or pointer a multiple of 8.² The reason is fetch granularity: a processor that always reads aligned 8-byte chunks can service any aligned double with one memory operation. Let the value straddle two chunks (recall the fence-post arithmetic of 0.1) and one access becomes two.³

A subtlety worth knowing: on x86-64, unaligned data still works; the hardware handles it, and alignment is Intel's performance recommendation, not a correctness rule. The historical exception was SSE: its 16-byte vector loads faulted on unaligned addresses, which is why malloc and stack frames guarantee 16-byte alignment to this day.⁴

Both padding rules come straight from the compiler's contract: gaps inside the struct keep each field aligned, and trailing padding keeps every element of an array of the struct aligned.⁵ The fix costs one line of diff: declare fields in decreasing size order. Put b at 0, c at 8, a at 12: every field lands aligned with 3 tail bytes instead of 11. Bakhvalov shows the same transformation shrinking a {bool; int; short} struct from 12 bytes to 8.⁶

Size order is not the only ordering that matters. When a struct is bigger than one line, group the fields that are used together: if the hot loop reads attack, defense, and health, but health was declared 64 bytes away, that phase of the program pays two cache lines per object instead of one. Reordering so co-accessed fields share a line is the same locality argument at field granularity, and modern tooling (Linux perf mem data-type profiling) exists precisely to find these opportunities.⁷

SourcesCS:APP 3e §3.9.3 · pp. 309–312Bakhvalov 2e §8.1.3–8.1.4 · pp. 195–197

Padding is the small version of the layout decision. The big one: you have a million particles, each with position, velocity, and mass. Array-of-structs(AoS) keeps each particle's fields together: natural to write, and right when you use all fields of a particle at once. Struct-of-arrays (SoA) keeps one array per field: all the masses contiguous, all the x-positions contiguous.

Now run a pass that reads only the mass, one 4-byte field of a 24-byte struct. In AoS, a mass appears every 24 bytes, so every 64-byte line of the whole array contains one: the walk drags all 24 MB of struct data through the cache to consume 4 MB of masses. In SoA, the masses are the byte run: 4 MB touched, 4 MB used, the pure stride-4 row-walk from 0.6. Same computation, 6× less memory traffic, from a declaration-site choice.

The practitioner's middle ground is structure splitting: carve the hot fields into their own compact struct and banish the cold ones to a second array. Splitting Point into PointCoords + PointInfo means a coordinates-only pass loads nothing but coordinates: more points per cache line, no rewrite of the whole program into SoA.¹⁰ And when even the fields themselves are bigger than their information content, packing (bitfields) trades a few shift-and-mask instructions for fewer bytes moved, worth it exactly when compute is cheaper than the memory transfers it saves, which after 0.4 you know is most of the time.¹¹

This exact picture is why ML frameworks store tensors as struct-of-arrays (a tensor is SoA taken to its logical conclusion), and it is the idea that becomes GPU coalescing in chapter 2.4, where 32 threads read 32 neighboring values and the hardware fuses them into a handful of line fetches, but only if the layout put those values adjacent.

SourcesBakhvalov 2e §8.1.3–8.1.5 · pp. 195–198CS:APP 3e §6.5 · p. 669