Cache-Friendly Programming
Cache & Performance · Memory & Systems track
7 min read
In this module
Writing Code the Cache Will Love
Caches run on two principles: temporal locality (recently accessed data is probably about to be accessed again) and spatial locality (data near recently accessed data is probably about to be accessed too). Code that obeys both runs fast. Code that ignores both runs slowly. This lesson is the recipe book for keeping your data in cache.
Cache-friendly code touches data in the order it sits in memory and reuses what's already loaded. Cache-hostile code skips around or thrashes — the algorithm can have the right Big-O and still lose to a worse algorithm with better locality.
Spatial Locality: Sequential Access Patterns
The simplest cache optimisation is just walking memory in order. Cache lines are 64 bytes, so a sequential scan loads chunks of 64 bytes at a time and uses every single one. Random access loads a full 64-byte line but reads only the few bytes you actually wanted, throwing the other 60 in the bin.
// Good: sequential access (row-major traversal of row-major array)for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) sum += matrix[i][j]; // adjacent elements are in same cache line
// Bad: strided access (column-major traversal of row-major array)for (int j = 0; j < N; j++) for (int i = 0; i < N; i++) sum += matrix[i][j]; // each access jumps N elements forwardFor a 1000x1000 matrix of ints, the column-major traversal misses the cache on nearly every access. Each matrix[i][j] sits 4000 bytes from matrix[i+1][j], far beyond a 64-byte cache line. The row-major version, by contrast, keeps slamming into the same cache line for 16 consecutive accesses (64 bytes / 4 bytes per int).
The heatmap below is a scaled-down picture of the bad loop: a 16×16 matrix stored row by row, with the cache-line boundaries drawn in every four cells. It starts in strided mode with a stride of 16, which is the column-major walk: straight down column 0, then column 1, and so on. Play it and watch how it touches one cell per cache line and moves on, so by the time it wanders back for the line's next cell, a real cache with many other lines in play may well have evicted it. Then switch the pattern to sequential, the row-major walk, and watch it finish each line before starting the next.
Memory Access Heatmap
Time it yourself. This sums a 4096×4096 int array (64 MiB) in both orders and times each pass with clock(). Same additions, same answer, different order.
Temporal Locality: Reuse Before Eviction
Temporal locality is about using data again before the cache evicts it. Loop tiling (also called blocking) restructures loops so the working set fits in cache and gets fully chewed through before you move on.
Classic example - matrix multiplication:
// Naive: poor temporal locality for Bfor (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) C[i][j] += A[i][k] * B[k][j];
// Interchanged (i, k, j): the inner loop now walks B and C along rowsfor (int i = 0; i < N; i++) for (int k = 0; k < N; k++) for (int j = 0; j < N; j++) C[i][j] += A[i][k] * B[k][j];
// Tiled: B's block stays in cache across multiple i iterationsfor (int ii = 0; ii < N; ii += BLOCK) for (int jj = 0; jj < N; jj += BLOCK) for (int kk = 0; kk < N; kk += BLOCK) for (int i = ii; i < min(ii+BLOCK, N); i++) for (int j = jj; j < min(jj+BLOCK, N); j++) for (int k = kk; k < min(kk+BLOCK, N); k++) C[i][j] += A[i][k] * B[k][j];In the naive order the innermost loop reads B[k][j] down a column, the same strided walk as the bad sum above. Swapping the j and k loops is the cheap first fix: same arithmetic, but now the inner loop streams along rows of B and C. Tiling goes further for matrices too big to fit in cache. Choose BLOCK so a block fits in L1 (~32KB), and each block of B gets loaded once, then reused across every computation that needs it. The speedup can be 10x or more for large matrices.
Data-Oriented Design
Traditional object-oriented design clusters related fields together inside objects. Fine in theory. But if you iterate over a thousand objects and only ever read one field, you're hauling all the other fields into cache and burning the capacity.
Array of Structs (AoS): [{x,y,z}, {x,y,z}, {x,y,z}, ...] - each object's fields are contiguous. Good when you access all fields of one object together.
Struct of Arrays (SoA): {[x,x,x,...], [y,y,y,...], [z,z,z,...]} - each field's values are contiguous across all objects. Good when you iterate over many objects accessing one field. SoA enables SIMD vectorisation, improves cache utilisation for single-field operations, and is the standard layout in game engines and scientific computing.
Entity Component System (ECS) architecture, popular in game development, takes data-oriented design to its logical extreme. Game entities are nothing but IDs. Components (position, velocity, health) live in contiguous arrays indexed by entity ID. Systems walk component arrays, touching only the components they care about. The result is brutal cache efficiency for hot-loop operations like physics updates.
False Sharing
False sharing is the kind of multi-threaded performance bug that hides in plain sight. When two threads on different cores write to different variables that happen to share a cache line, the coherence protocol forces that line to ping-pong between cores on every single write.
// Bad: counters likely share a cache linestruct { long counter_thread_0; // byte 0-7 long counter_thread_1; // byte 8-15 (same cache line!)} counters;
// Good: pad to separate cache linesstruct { long counter_thread_0; char padding[56]; // ensure each counter is on its own cache line long counter_thread_1;} counters;C11/C++11 give you alignas(64) for cache-line alignment. Java has @Contended. Always pad per-thread data to cache-line boundaries in performance-critical concurrent code.
Predict: two threads each increment their own counter 100 million times, once with the bad struct and once with the padded one. Which run finishes first? And does padding[56] alone keep each counter on a line of its own?
The padded run, often by several times. Before a core can write, it needs the line in the Modified state. With both counters in one line, every increment drags the line away from the other core, so the two threads spend most of their time waiting on coherence traffic instead of adding. Padded, each core keeps its own line in L1 and the increments run at full speed.
The padding does keep the two counters apart: they sit 64 bytes from each other, and no 64-byte line can hold both. What it can't control is the neighbours. If the struct doesn't start on a line boundary, counter_thread_0 can share a line with whatever sits just before the struct, and counter_thread_1 with whatever comes after it. Putting alignas(64) on each counter fixes both ends, and the compiler adds the padding for you.
The in-browser runner can't start threads, so try this one on your own machine.
Prefetching
Modern CPUs ship with hardware prefetchers that watch your access patterns and preload data before you ask for it. They're good at detecting sequential access (forwards and backwards) and strided access (every Nth byte). Anything more exotic — pointer chasing through a linked list, for instance — defeats them entirely.
When the hardware can't see the pattern, you can drop hints yourself with software prefetch instructions (__builtin_prefetch in GCC/Clang, _mm_prefetch with intrinsics). The sweet spot is regular access patterns the hardware misses, like walking a precomputed schedule of addresses.
for (int i = 0; i < N; i++) { __builtin_prefetch(&array[i + 16], 0, 1); // prefetch 16 iterations ahead process(array[i]);}Measuring Cache Behaviour
Measure before you optimise. perf stat -e cache-references,cache-misses gives you overall miss rates. perf record -e cache-misses pinpoints which code lines are the worst offenders. Cachegrind (under Valgrind) does detailed per-line simulation. Only reach for these techniques once the data confirms cache misses are actually your bottleneck.