The Memory Hierarchy and Caches
A CPU core can execute several instructions per nanosecond, but main memory (DRAM) needs around 100 ns to deliver data.
Concept
Why a Hierarchy A CPU core can execute several instructions per nanosecond, but main memory (DRAM) needs around 100 ns to deliver data. The solution is a hierarchy of memories, each smaller and faster than the next:
L1 cache (per core, separate instruction/data) ~4 cycles (~1 ns) L2 cache (per core) ~12 cycles (~3 ns) L3 cache (shared) ~40 cycles (~10–20 ns) It works because of locality:
Temporal locality — recently used data is likely to be used again soon (loop variables, hot functions).
Spatial locality — data near recently used data is likely to be used soon (arrays, sequential code).
A cache stores memory in lines (blocks), usually 64 bytes. An address is split into:
Where a line can go Exactly one place (one line per set) Simple, fast; conflict misses N-way set associative Any of N lines in one set
Fewer conflicts; compares N tags in parallel (L1: 8–12 ways) Fully associative No conflicts; expensive (used for TLBs)
Replacement: LRU or approximations (pseudo-LRU). Writes: *write-through* (update memory immediately) or *write-back* (mark the line dirty, write when evicted — the norm), with *write-allocate* on a write miss.
The Three Cs of Misses Compulsory — first access to a line.
Capacity — the working set is larger than the cache.
Conflict — too many lines map to the same set.
Average memory access time = hit time + miss rate × miss penalty. Hardware prefetchers detect sequential or strided access and fetch lines before they're needed — which is why sequential access is so fast and random access so slow.
| tag | index (which set) | offset (byte within the line) |Why It Matters
For most real programs, memory access — not arithmetic — dominates run time. Data layout (arrays vs linked lists, row vs column order, struct field order) often changes performance by 10× or more without changing the algorithm.
Syntax
getconf LEVEL1_DCACHE_LINESIZE Cache line size Size, associativity, sharing of each level perf stat -e cache-misses./prog
Cache-miss counters (on bare-metal Linux)
Example
18.1 Measuring the hierarchy: latency vs working-set size The program follows a chain of pointers arranged in a random cycle, so every load depends on the previous one and the prefetcher can't help. The time per load reveals which level holds the working set.
18.2 The same computation, two traversal orders 18.3 A cache simulator: tag, index, offset and conflict misses
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* Pointer chasing through a random cycle: every load depends on the previous one,
so the time per step is the latency of whichever level of the hierarchy holds the data. */
static double chase(size_t bytes)
{
size_t n = bytes / sizeof(void *);
void **a = malloc(n * sizeof(void *));
size_t *order = malloc(n * sizeof(size_t));
for (size_t i = 0; i < n; i++) order[i] = i;
srand(42);
for (size_t i = n - 1; i > 0; i--) { /* random permutation defeats the prefetcher */
size_t j = (size_t)rand() % (i + 1), t = order[i];
order[i] = order[j]; order[j] = t;
}
for (size_t i = 0; i < n; i++) a[order[i]] = &a[order[(i + 1) % n]];
void **p = &a[order[0]];
long steps = 20000000;
for (long i = 0; i < n; i++) p = *p; /* warm up */
struct timespec t0, t1;
clock_gettime(CLOCK_MONOTONIC, &t0);
for (long i = 0; i < steps; i++) p = *p;
__asm__ volatile("" : : "r"(p) : "memory"); /* keep the loop between the two clock reads */
clock_gettime(CLOCK_MONOTONIC, &t1);
volatile void *sink = p; (void)sink;
free(a); free(ord
…#include <stdio.h>
#include <stdlib.h>
#include <time.h>
enum { N = 4096 };
static int m[N][N];
static double ms(struct timespec a, struct timespec b) { return (b.tv_sec - a.tv_sec) * 1e3 + (b.tv_nsec - a.tv_nsec) / 1e6; }
int main(void)
{
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) m[i][j] = i ^ j;
struct timespec t0, t1, t2;
long s1 = 0, s2 = 0;
clock_gettime(CLOCK_MONOTONIC, &t0);
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) s1 += m[i][j]; /* row by row: sequential */
clock_gettime(CLOCK_MONOTONIC, &t1);
for (int j = 0; j < N; j++) for (int i = 0; i < N; i++) s2 += m[i][j]; /* column by column: 16 KB stride */
clock_gettime(CLOCK_MONOTONIC, &t2);
printf("sum %ld == %ld\n", s1, s2);
printf("row-major traversal %6.1f ms\n", ms(t0, t1));
printf("column-major traversal %6.1f ms (%.1fx slower)\n", ms(t1, t2), ms(t1, t2) / ms(t0, t1));
return 0;
}"""A cache simulator: address split into tag / index / offset, direct-mapped vs 2-way set associative (LRU)."""
LINE = 16 # bytes per cache line -> 4 offset bits
LINES = 8 # total lines in the cache (128 bytes)
def split(addr, sets):
offset_bits = LINE.bit_length() - 1
index_bits = sets.bit_length() - 1
return addr >> (offset_bits + index_bits), (addr >> offset_bits) & (sets - 1), addr & (LINE - 1)
def simulate(addresses, ways, verbose=False):
sets = LINES // ways
cache = [[] for _ in range(sets)] # each set: list of tags, most recently used last
hits = 0
for a in addresses:
tag, index, off = split(a, sets)
s = cache[index]
if tag in s:
hits += 1; s.remove(tag); s.append(tag); result = "hit"
else:
if len(s) == ways:
s.pop(0) # evict the least recently used line
s.append(tag); result = "MISS"
if verbose:
print(f" addr {a:#06x} tag {tag:#x} set {index} offset {off:2d} {result}")
return hits
# Two arrays whose elements map to the same set in a direct-mapped cache (they are 128 bytes apart)
…Expected Result
The steps line up with this CPU's caches (32 KB L1d per core, 256 KB L2 per core, 8 MB shared L3): about 1 ns up to 32 KB, about 3 ns up to 256 KB, 10–35 ns within the L3, and 90–130 ns once the data only fits in DRAM — a factor of more than 100 between the fastest and slowest level. (The gradual rise inside each level comes from TLB misses and the random access pattern; your numbers will differ.)
Both loops add the same 16 million numbers. Row-major order walks memory sequentially (each 64-byte line serves 16 ints, and the prefetcher streams lines in); column-major order jumps 16 KB between accesses, touching a new line — often a new page — every time.
In the direct-mapped cache both arrays map to set 0 and evict each other on every access: 0 hits although only 2 lines are in use — pure conflict misses. With 2 ways the same cache holds both lines. The sequential scan shows spatial locality: one miss per line, then hits for the rest of the line.
working set ns per load
8 KB 1.1
16 KB 1.2
24 KB 1.1
64 KB 2.4 #
128 KB 2.9 #
192 KB 3.5 #
512 KB 10.3 #####
1024 KB 12.5 ######
4096 KB 18.0 ########
6144 KB 35.7 #################
16384 KB 88.9 ############################################
65536 KB 111.6 #######################################################
262144 KB 131.3 #################################################################sum 34351349760 == 34351349760
row-major traversal 10.1 ms
column-major traversal 303.1 ms (30.0x slower)direct-mapped, 8 lines of 16 bytes:
addr 0x0000 tag 0x0 set 0 offset 0 MISS
addr 0x0080 tag 0x1 set 0 offset 0 MISS
addr 0x0004 tag 0x0 set 0 offset 4 MISS
addr 0x0084 tag 0x1 set 0 offset 4 MISS
addr 0x0008 tag 0x0 set 0 offset 8 MISS
addr 0x0088 tag 0x1 set 0 offset 8 MISS
addr 0x000c tag 0x0 set 0 offset 12 MISS
addr 0x008c tag 0x1 set 0 offset 12 MISS
addr 0x0000 tag 0x0 set 0 offset 0 MISS
addr 0x0080 tag 0x1 set 0 offset 0 MISS
addr 0x0004 tag 0x0 set 0 offset 4 MISS
addr 0x0084 tag 0x1 set 0 offset 4 MISS
addr 0x0008 tag 0x0 set 0 offset 8 MISS
addr 0x0088 tag 0x1 set 0 offset 8 MISS
addr 0x000c tag 0x0 set 0 offset 12 MISS
addr 0x008c tag 0x1 set 0 offset 12 MISS
-> 0/16 hits (conflict misses: both arrays fight over set 0)
2-way set associative, same size: 14/16 hits
sequential scan of 256 bytes (64 ints), direct-mapped: 48/64 hits -> 1 compulsory miss per 16-byte line, then 3 hits (spatial locality)Common Mistakes
Traversing 2-D arrays in the wrong order (C is row-major; Fortran and MATLAB are column-major).
Using linked lists or pointer-heavy structures for data scanned sequentially.
Measuring with tiny inputs that fit in L1 and extrapolating to large data.
Assuming "RAM access" has a single cost.
Best Practices
Keep hot data compact and contiguous (arrays of structs or structs of arrays, depending on access pattern).
Process data in cache-sized blocks (loop tiling / blocking for matrix operations).
Put fields used together next to each other; move rarely used fields out of hot structs.
Measure with realistic sizes; use perf or VTune to count misses.
Interview Relevance
Very high: "explain the memory hierarchy", "what is locality?", "direct-mapped vs set-associative?", "the three Cs", "why is iterating a 2-D array column-wise slow in C?", "write-back vs write-through?", "compute the tag/index/offset bits for a given cache".
Practice Questions
A 32 KB, 8-way cache with 64-byte lines and 48-bit addresses: how many sets, and how many tag, index and offset bits?
Compute the average memory access time for hit time 1 ns, miss rate 5%, miss penalty 100 ns.
Implement blocked matrix multiplication and compare it with the naïve triple loop for N = 1024.
Add a 4-way configuration to the simulator and test the conflict pattern again.
Quick Quiz
Q1. (Multiple choice) Which kind of miss disappears when associativity increases (same size)? A) Compulsory B) Capacity C) Conflict D) Coherence
Answer: C (verified: 0/16 hits direct-mapped, 14/16 with 2 ways).
Q2. (Predict the output) Row-major vs column-major sum of a 4096 × 4096 int matrix — which is faster and by roughly how much?
Answer: Row-major; about 30× faster on the test machine (verified).
Q3. (True/False) A cache line is typically 64 bytes on x86-64 and ARM64.
Answer: True. Q4. (Find the bug) for (j = 0; j < N; j++) for (i = 0; i < N; i++) a[i][j] = 0; is slow.
Answer: The inner loop jumps a whole row between accesses; swap the loops so the inner loop walks j (contiguous memory).
Coding Challenge
Write a program that computes the number of sets and the tag/index/offset bit widths for a cache given its size, associativity, line size and address width, and apply it to a 32 KB 8-way cache with 64-byte lines and 48-bit addresses.
#include <stdio.h>
static int log2i(unsigned long x) { int n = 0; while (x > 1) { x >>= 1; n++; } return n; }
int main(void)
{
unsigned long size = 32 * 1024, ways = 8, line = 64;
int address_bits = 48;
unsigned long sets = size / (ways * line);
int offset = log2i(line), index = log2i(sets), tag = address_bits - index - offset;
printf("%lu sets; offset %d bits, index %d bits, tag %d bits\n", sets, offset, index, tag);
return 0;
}