Cache Hierarchy, Locality and Performance
Main memory is roughly a hundred times slower than the processor.
Learning Objectives
Describe the register–cache–RAM hierarchy, cache lines, hits and misses, and spatial and temporal locality.
Explain direct-mapped, set-associative and fully associative mapping, replacement policies, write-through/write-back and write-allocate/no-write-allocate.
Explain cache coherence, false sharing, bandwidth versus latency, prefetching and cache-line alignment.
Choose data layouts (AoS versus SoA, data-oriented design) and traversal orders for locality.
Benchmark and profile correctly, use performance counters, avoid misleading microbenchmarks, and decide when optimization is worthwhile.
Handle embedded cache maintenance and DMA coherency.
Plain-Language Explanation
Main memory is roughly a hundred times slower than the processor. Caches hide that gap by keeping copies of recently used memory in small, fast storage next to the core. They move data in lines of 64 bytes. If your program uses data that is close together (spatial locality) or reuses the same data soon (temporal locality), almost every access hits a cache. If it jumps around randomly, the CPU spends most of its time waiting. Often the biggest speed-up in a program comes not from a cleverer algorithm but from arranging data so the cache can help.
Precise Technical Explanation
Registers, L1/L2/L3 caches and RAM The build machine (Intel Core i5-8300H) reports: L1 data 32 KiB per core (8-way), L1 instruction 32 KiB, L2 256 KiB per core (4-way), L3 8 MiB shared (16-way), 64-byte lines everywhere. Typical latencies on such cores: L1 ~4–5 cycles, L2 ~12, L3 ~40, DRAM ~200+ cycles.
The unit of transfer and coherence: 64 bytes on x86 and most Arm cores (128 on Apple M-series L2 and some POWER chips). Reading one byte brings its whole line in.
Using addresses near ones recently used — sequential array traversal. One miss brings 64 bytes, so the next 15 ints hit.
Reusing the same addresses soon — loop variables, hot structures, blocking a matrix so a tile is reused while it is in cache.
Cache hits and misses Misses are classified as compulsory (first access), capacity (working set larger than the cache) and conflict (too many lines mapping to the same set).
Cache mapping: direct-mapped, set-associative and fully associative
An address splits into tag | set index | line offset. A direct-mapped cache has one line per set (fast, conflict-prone); an N-way set-associative cache has N lines per set; a fully associative cache lets any line go anywhere (used for TLBs and small buffers). The 32 KiB, 8-way, 64-byte L1 has 32768 / 64 / 8 = 64 sets: 6 offset bits, 6 index bits.
Replacement policies overview When a set is full, the cache evicts a line: LRU (least recently used), pseudo-LRU (tree bits), random, or adaptive policies (RRIP) in modern L3s.
Write-through and write-back Write-through caches send every store to the next level immediately (simple, more traffic). Write-back caches mark the line *dirty* and write it only on eviction (less traffic — the norm for CPU data caches).
Write-allocate and no-write-allocate On a store miss, write-allocate brings the line into the cache first (usually paired with write-back); no-write-allocate writes around it. Non-temporal / streaming stores (movnt*) bypass caches for large one-off writes.
Two threads write *different* variables that happen to share one cache line; the coherence protocol bounces the line between cores on every write, as if they shared data. Fix: pad or align per-thread data to separate lines (measured below).
Cache coherence basics Hardware keeps all cores' caches consistent with a protocol such as MESI: a line can be Modified, Exclusive, Shared or Invalid in each cache; a write invalidates other copies. Coherence makes caches invisible to correctness (on CPUs) but not to performance.
Memory bandwidth and latency Latency limits dependent accesses (linked lists: each load waits for the previous one). Bandwidth limits streaming (summing a huge array). The cures differ: latency is hidden with locality, prefetching and independent work; bandwidth is saved by compact data and fewer passes.
Hardware prefetchers detect sequential and strided streams and fetch lines ahead of use. Software can hint with __builtin_prefetch. Random and pointer-chasing patterns defeat prefetchers.
Alignment and cache-line boundaries An object that straddles two lines needs two line fills. Align hot structures and per-thread data to 64 bytes (alignas(64), std::hardware_destructive_interference_size in C++17).
Array of Structures (AoS) versus Structure of Arrays (SoA) A loop that reads only mass touches one useful float per 64-byte particle in AoS, but 16 useful floats per line in SoA (measured below). SoA also vectorises naturally.
Organise data by how it is *processed*, not by conceptual objects: hot fields together, cold fields elsewhere, arrays instead of pointer graphs, batch processing of homogeneous data. Common in game engines and high-performance systems.
Strided access and traversal order Stride = distance between consecutive accesses. Stride ≤ 64 bytes reuses lines; larger strides use one element per line; strides that are multiples of sets × line size (4 KiB for the L1 above) map to the same set and cause conflict misses.
Branch and data locality Code has locality too: hot loops should fit in the I-cache and the µop cache; rarely executed code (error handling) can be moved out of line (__builtin_expect, [[unlikely]], __attribute__((cold))).
Measure the real workload or a faithful kernel; warm up; repeat and report the distribution (median, spread), not one number; control CPU frequency and background load; keep the compiler from deleting the work (use results); compare equal work; state hardware, compiler and flags.
Profiling and performance counters Sampling profilers (perf record, VTune, Instruments, Visual Studio profiler) show *where* time goes; hardware counters (perf stat -e cache-misses,L1-dcache-load-misses,LLC-load-misses) show *why*. Inside some VMs (including the build machine's WSL2) counters are unavailable — then time controlled experiments, as below.
Avoiding misleading microbenchmarks Pitfalls: the optimizer removing unused work; data that fits in cache in the benchmark but not in production; timing one run with cold caches; turbo/thermal effects; comparing debug builds; measuring the timer. Always sanity-check results against a model ("is 0.3 ns per element plausible?").
Cache behavior on multicore systems L1/L2 are private, L3 shared. Shared read-only data is cheap; shared written data costs coherence traffic; contended atomics and locks serialize on one line. Partition data per thread and merge results at the end.
Embedded cache maintenance Cortex-M7 and Cortex-A cores have caches that software must manage around DMA and self-modifying code: SCB_CleanDCache_by_Addr, SCB_InvalidateDCache_by_Addr (CMSIS), or MPU regions marked non-cacheable.
DMA/cache coherency issues Module 8: clean before a DMA engine reads memory the CPU wrote; invalidate before the CPU reads memory a DMA engine wrote; align buffers to cache lines.
When optimization is worthwhile Only for code that profiling shows is hot *and* where the gain matters to users or cost. Locality improvements are often the cheapest big wins; micro-tuning cold code is wasted effort and harms readability.
struct ParticleAoS { float x, y, z, mass; char name[48]; } particles[N]; /* AoS */
struct ParticlesSoA { float x[N], y[N], z[N], mass[N]; char name[N][48]; }; /* SoA */Why It Matters in Real Systems
Matrix libraries, databases (column stores), game engines (entity-component systems), network packet processing and machine-learning kernels are all designed around cache behavior. A 3–10× difference between two "O(n)" loops is common.
Key Terms
64-byte unit of transfer and coherence Spatial / temporal locality Using nearby / recently used data Data found / not found in a cache
Number of places a line can go in its set Write-back / write-through
Defer / propagate writes to the next level Coherence (MESI) Protocol keeping caches consistent
Independent data sharing a line, causing coherence traffic Fetching lines before they are needed
Array of structures / structure of arrays Distance between successive accesses
Memory Layout and Execution Flow
32 KiB, 8-way, 64-byte lines → 64 sets
address bits: [ tag (rest) | set index (6 bits) | offset (6 bits) ]
0x7ffd5e2c3a1c → offset 0x1c, set (0x3a1c >> 6) & 63 = 40Syntax
_Alignas(64) struct Counter { long value; }; /* C11: one counter per cache line */
__builtin_prefetch(&a[i + 16]); /* GCC/Clang prefetch hint */
long line = sysconf(_SC_LEVEL1_DCACHE_LINESIZE); /* glibc extension */struct alignas(std::hardware_destructive_interference_size) Counter { std::atomic<long> v; };Complete Runnable Example
The specification's row-major traversal, measured against column-first order, plus strided access and AoS versus SoA. GCC 11.2 -O2, i5-8300H under WSL2. Timings are *one run on one machine*: the shape matters, not the numbers.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ROWS 4096
#define COLS 4096
static int matrix[ROWS][COLS]; /* 64 MiB: far larger than every cache */
static double now(void)
{
struct timespec t;
clock_gettime(CLOCK_MONOTONIC, &t);
return (double)t.tv_sec + (double)t.tv_nsec * 1e-9;
}
struct ParticleAoS { float x, y, z, mass; char name[48]; }; /* 64 bytes per particle */
#define NP (1 << 20)
int main(void)
{
double t0 = now();
for (int r = 0; r < ROWS; ++r) /* row-major: consecutive addresses */
for (int c = 0; c < COLS; ++c)
matrix[r][c] = r + c;
double t1 = now();
long long sum = 0;
for (int c = 0; c < COLS; ++c) /* column-first: 16 KiB jumps */
for (int r = 0; r < ROWS; ++r)
sum += matrix[r][c];
double t2 = now();
long long sum2 = 0;
for (int r = 0; r < ROWS; ++r)
for (int c = 0; c < COLS; ++c)
sum2 += matrix[r][c];
double t3 = now();
printf("write row-major : %6.1f ms\n", (t1 - t0) * 1e3);
printf("sum column-first: %6.1f ms (sum %lld)\n", (t2 - t1) * 1e3, sum);
printf("sum row-majo
…Line-by-Line Explanation
matrix is 64 MiB — larger than L3 — so every pass streams from DRAM.
The first loop writes row by row: addresses increase by 4 bytes, each 64-byte line serves 16 ints, and the prefetcher streams ahead.
The column-first loop jumps COLS × 4 = 16 KiB per access: every access is to a different line (and a different page every time), so each line is used once per 16 columns, TLB pressure is high, and conflict misses are common.
The stride loop does the same number of accesses for each stride; beyond 16 ints (64 bytes) each access needs its own line.
AoS reads 4 useful bytes per 64-byte line; SoA reads 64 useful bytes per line.
Expected Output
Output (one real run — your numbers will differ):
Column-first traversal does exactly the same additions as row-major and is several times slower. Cost per access rises with stride: up to 16 ints (64 bytes) neighbouring accesses share lines; beyond that every access needs its own line, and at larger strides the prefetcher and TLB help less and less. SoA beats AoS by a wide margin for a single-field pass. Do not quote these ratios as constants: they depend on CPU, memory, compiler and system load.
write row-major : 91.8 ms
sum column-first: 223.4 ms (sum 68702699520)
sum row-major : 12.2 ms (sum 68702699520)
stride 1 ints ( 4 bytes): 0.95 ns per access (acc 2139095040)
stride 4 ints ( 16 bytes): 2.34 ns per access (acc 2139095040)
stride 16 ints ( 64 bytes): 7.75 ns per access (acc 2139095040)
stride 64 ints (256 bytes): 13.10 ns per access (acc 2139095040)
sum of mass, AoS (64-byte structs): 52.0 ms (31457220)
sum of mass, SoA (float array) : 15.2 ms (31457220)Step-by-Step Execution Trace
Row-major, first line of matrix[0]:
matrix[0][0]: miss (compulsory) → fetch line 0 ([0][0]…[0][15]).
matrix[0][1] … [0][15]: 15 hits.
matrix[0][16]: miss — but the prefetcher has usually started fetching it already.
Column-first: matrix[0][0] miss, matrix[1][0] (16 KiB later) miss, matrix[2][0] miss … after 4096 rows the first line has long been evicted, so matrix[0][1] misses again.
Interactive Visualization
Choose line size, capacity, associativity and an access pattern (sequential, strided, random, row-major, column-major) and watch hits, misses and evictions. Results are simulator outputs for the chosen model, not hardware measurements.
Common Mistakes and Failure Modes
Traversing matrices against their storage order; mixing row-major C with column-major Fortran/BLAS without transposing parameters.
Pointer-heavy data structures (linked lists, trees of small nodes) on hot paths.
Per-thread counters in one array (false sharing).
Benchmarks whose data fits in L1 when production data does not.
"Optimising" by padding everything to 64 bytes, multiplying memory use.
False sharing, measured with two threads incrementing their own counters:
Output (one real run):
The threads never touch each other's counter, yet sharing a line made the same work about twice as slow in this run (the ratio varies with CPU and load; on many-core servers it is often much larger).
#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
#include <time.h>
#define ITERS 20000000L
struct Packed { atomic_long a; atomic_long b; }; /* same cache line */
struct Padded { _Alignas(64) atomic_long a; _Alignas(64) atomic_long b; }; /* separate lines */
static struct Packed packed;
static struct Padded padded;
static void *bump(void *counter)
{
atomic_long *c = counter;
for (long i = 0; i < ITERS; ++i) atomic_fetch_add_explicit(c, 1, memory_order_relaxed);
return NULL;
}
static double run(atomic_long *x, atomic_long *y)
{
struct timespec t0, t1;
pthread_t a, b;
clock_gettime(CLOCK_MONOTONIC, &t0);
pthread_create(&a, NULL, bump, x);
pthread_create(&b, NULL, bump, y);
pthread_join(a, NULL);
pthread_join(b, NULL);
clock_gettime(CLOCK_MONOTONIC, &t1);
return (double)(t1.tv_sec - t0.tv_sec) * 1e3 + (double)(t1.tv_nsec - t0.tv_nsec) / 1e6;
}
int main(void)
{
printf("sizeof Packed=%zu, Padded=%zu\n", sizeof packed, sizeof padded);
double t_packed = run(&packed.a, &packed.b);
double t_padded = run(&padded.a, &padded.b);
printf("same line (false sharing): %7.1f ms, counts %ld %ld
…sizeof Packed=16, Padded=128
same line (false sharing): 387.2 ms, counts 20000000 20000000
separate lines (padded) : 190.0 ms, counts 20000000 20000000Corrected / Safe Pattern
/* traverse in storage order */
for (r = 0; r < R; ++r) for (c = 0; c < C; ++c) use(m[r][c]);
/* split hot and cold data; process hot arrays in tight loops */
struct Hot { float x, y, z, mass; } hot[N];
struct Cold { char name[48]; } cold[N];
/* per-thread state padded to a line, merged at the end */
struct alignas(64) PerThread { long count; };Debugging and Diagnostic Techniques
On bare-metal Linux: perf stat -e cycles,instructions,L1-dcache-load-misses,LLC-load-misses ./prog, perf c2c (false sharing), Valgrind cachegrind (simulated), Intel VTune "Memory Access", AMD uProf.
echo "L1d line size: $(getconf LEVEL1_DCACHE_LINESIZE) bytes, L1d $(( $(getconf LEVEL1_DCACHE_SIZE) / 1024 )) KiB $(getconf LEVEL1_DCACHE_ASSOC)-way"
echo "L2 $(( $(getconf LEVEL2_CACHE_SIZE) / 1024 )) KiB $(getconf LEVEL2_CACHE_ASSOC)-way, L3 $(( $(getconf LEVEL3_CACHE_SIZE) / 1024 / 1024 )) MiB $(getconf LEVEL3_CACHE_ASSOC)-way"
lscpu | grep -E '^(Model name|CPU\(s\)|Thread|L1d|L1i|L2|L3)'L1d line size: 64 bytes, L1d 32 KiB 8-way
L2 256 KiB 4-way, L3 8 MiB 16-way
CPU(s): 8
Model name: Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
Thread(s) per core: 2
L1d cache: 128 KiB (4 instances)
L1i cache: 128 KiB (4 instances)
L2 cache: 1 MiB (4 instances)
L3 cache: 8 MiB (1 instance)Performance Implications
Locality typically matters more than instruction count once data exceeds L2. Contiguous layouts, storage-order traversal, blocking (tiling) for reuse, SoA for field-wise passes, compact types, and avoiding shared written lines between threads are the main levers. Every change must be measured on representative data and hardware.
Security and Safety Implications
Caches leak information through timing: cache side channels (Prime+Probe, Flush+Reload) can recover keys from table-based cryptography and, combined with speculation, cross isolation boundaries (Spectre). Constant-time code avoids secret-dependent memory addresses and branches. On MCUs with caches, missing maintenance around DMA is a correctness and safety bug.
Platform and Language Caveats
Cache sizes, line sizes, associativity and policies vary by CPU; query them (getconf, lscpu, CPUID, /sys/devices/system/cpu/cpu0/cache).
Java, C#, JavaScript and Python control layout less directly: arrays of primitives are contiguous, arrays of objects are arrays of references (pointer chasing); value types (C# struct, Java Valhalla, NumPy arrays) restore control.
Compilers may interchange or tile loops at higher optimization levels (-O3, -floop-interchange), changing results of naive benchmarks.
Real-World Application
BLAS libraries tile matrices for L1/L2/L3; column-oriented databases (ClickHouse, DuckDB) store SoA; game ECS frameworks process components in arrays; high-frequency trading pads per-thread state; the Linux kernel annotates ____cacheline_aligned data; Cortex-M7 firmware places DMA buffers in non-cacheable regions.
Best Practices Checklist
[ ] Prefer contiguous arrays; traverse in storage order.
[ ] Keep hot data compact and separate from cold data.
[ ] Use SoA for field-wise bulk processing.
[ ] Pad or separate data written by different threads.
[ ] Benchmark with production-sized data; repeat and report variance.
[ ] Profile with counters where available before optimising.
[ ] On MCUs, manage caches around DMA.
Exercises
E1 · Beginner. How many 4-byte ints share one 64-byte cache line? What fraction of loaded bytes does a stride-16-int loop use?
Answer: 16 ints. Stride 16 ints = 64 bytes, so each access uses 4 of the 64 loaded bytes: 1/16.
E2 · Intermediate. For the 32 KiB, 8-way, 64-byte L1 above, which set does address 0x12345 map to? How many addresses 4 KiB apart can be cached at once?
Answer: Set = (0x12345 >> 6) & 63 = 0x48D & 0x3F = 13. Addresses 4 KiB apart share the same set index (4096 = 64 sets × 64 bytes), so only 8 (the associativity) fit at once.
E3 · Advanced challenge. Write a blocked (tiled) matrix transpose and compare it with the naive transpose for a 4096×4096 int matrix. Choose the tile size and explain it.
Answer: Transpose B×B tiles: for each tile, read rows of the source tile and write columns of the destination tile. Choose B so two tiles fit in L1 (e.g. 32×32 ints = 4 KiB each, or 64×64 = 16 KiB each with 32 KiB L1 — 32 is safer). Within a tile both source rows and destination lines stay cached, so each line is loaded once instead of once per element; expect several-fold speed-ups — measure them.
Quiz
? Why is column-first traversal of a large C matrix slow?
- It performs more additions. :: The arithmetic is identical.
+ Consecutive accesses are far apart, so each uses a different cache line (and page) and lines are evicted before reuse. :: Poor spatial locality.
- C stores matrices column-major. :: C is row-major; that is the point.
- The compiler cannot vectorise additions. :: Vectorisation is secondary to the memory pattern.
? What is false sharing?
+ Different threads writing different variables that lie in the same cache line. :: Coherence traffic bounces the line.
- Two threads sharing a variable without a lock. :: That is a data race.
- A cache returning stale data. :: Coherence prevents that on CPUs.
- Sharing memory between processes. :: Unrelated.
? Which improve spatial locality? (select all that apply)
+ Storing a hot field in its own contiguous array (SoA) :: Every loaded byte is useful.
+ Traversing arrays in storage order :: Consecutive accesses share lines.
- Replacing an array with a linked list :: Nodes are scattered.
+ Splitting rarely used fields out of a hot struct :: More hot structs per line.
? A microbenchmark shows a loop taking 0.01 ns per iteration.
…Summary
Caches move 64-byte lines and reward spatial and temporal locality. Mapping, associativity and replacement decide which lines survive; coherence keeps cores consistent at a cost when lines are shared for writing. Storage-order traversal, contiguous data, SoA, hot/cold splitting and per-thread padding are the main tools — always confirmed by careful measurement on real hardware and data.
References and Further Reading
Ulrich Drepper, "What Every Programmer Should Know About Memory".
Hennessy & Patterson, *Computer Architecture: A Quantitative Approach*, chapter 2.
Intel® 64 and IA-32 Architectures Optimization Reference Manual.
Mike Acton, "Data-Oriented Design and C++" (CppCon 2014).