Why Struct Size and Memory Layout Can Make Loops 30x Faster

Algorithmic complexity tells only part of the performance story. A simple O(N) loop can vary dramatically in real-world speed depending on how data is laid out relative to CPU cache lines, which on most modern hardware are 64 bytes wide. When a program reads one byte, the CPU pulls in the surrounding 64 bytes, so packing only the fields you actually iterate over into contiguous memory lets a single fetch cover dozens of records instead of one.

The canonical example is Array of Structs versus Struct of Arrays. Iterating an array of 64-byte Monster structs to check a single is_alive byte burns an entire cache line per record. Splitting the data so is_alive lives in its own contiguous array lets 64 booleans ride in one cache line, and the hardware prefetcher streams the next line before it is needed. Benchmarks show up to 30x speedups once structs grow to roughly 1 KiB; gains shrink for tiny structs because several already fit per line.

For random access patterns — hash maps, trees, pointer chasing — the prefetcher is useless, so the working set size dictates which cache tier you land in. Doubling a struct from 64 to 128 bytes can push 512 records out of L1d (~3 ns) into L2 (~11 ns), producing a staircase latency curve that shifts left as structs grow. The practical takeaway: count your bytes, measure your working set, and treat memory layout as a first-class performance lever alongside algorithmic choice.