Expert · Module 23
Cache-aware data structures
Design for the memory hierarchy: cache lines, prefetching and data layout.
Big-O counts steps and treats every memory access alike, but a cache miss costs about a hundred times an L1 hit, so how bytes are arranged can decide how fast a correct algorithm really runs. The four lessons cover the levers: how cache lines and prefetching reward some access patterns over others, how struct-of-arrays and array-of-structs layouts change the traffic a loop pulls in, how hash tables can be laid out to stay inside one array, and how to benchmark and count cycles so you know whether any of it helped.
- 1Cache lines and prefetchingPro — members onlyMemory moves in 64-byte lines, not four-byte integers. Count the lines a sequential walk, a stride-3 walk and a linked-list walk each touch, and see why the processor can hide some of those waits but not others.13 min
- 2Struct of arrays vs array of structsPro — members onlyLaying out the same fields in two orders changes how many cache lines a one-field loop pulls in. Count the fills for both layouts and learn when each one wins.12 min
- 3Cache-friendly hash tablesPro — members onlyOpen addressing keeps a whole probe run inside one array, often inside one cache line. See what clustering, group probing, tombstones and load factor do to that run.14 min
- 4Benchmarks and performance countersPro — members onlyA stopwatch reports a number, not a verdict. Warm-up, outliers, dead-code elimination and the wrong statistic can each invent an improvement; hardware counters show where the cycles actually went.13 min