The Memory Hierarchy

The memory hierarchy is not a design choice — it is a physical constraint. To understand it, you need one piece of semiconductor physics: access latency scales with transistor size and capacitance, and density scales inversely with transistor size.

SRAM (Static RAM), used in registers and caches, stores a bit using 6 transistors that hold their state as long as power is applied. Reading is fast because it only involves sensing a voltage differential — no charge needs to move far. The price: 6 transistors per bit means low density and high power per bit.

DRAM (Dynamic RAM), used in main memory, stores a bit as a charge in a capacitor alongside a single access transistor. One transistor per bit means extremely high density and low cost. The price: the capacitor leaks charge and must be refreshed thousands of times per second, and reading requires a slow sense-amplifier cycle that destroys the stored charge (it must be rewritten). A single DRAM read involves: row activation (~15 ns), column access (~15 ns), precharge (~15 ns), plus the bus transfer. That is why RAM is ~100× slower than L1 cache.

Flash storage (NVM/SSD) stores bits as charge trapped in floating-gate transistors. You can pack many bits per cell (MLC = 2 bits, TLC = 3 bits, QLC = 4 bits), giving enormous density at low cost. Writing requires high-voltage quantum tunneling to inject charge, which is why writes are slower than reads and why flash cells wear out.

Hard disk drives store bits as magnetic domains on spinning platters. To read data you must wait for the platter to rotate to the right sector (rotational latency ~4 ms at 7200 RPM) and for the arm to seek to the right track (~5–10 ms). These are mechanical delays — utterly incompatible with nanosecond computing.

So the hierarchy is not an arbitrary engineering choice. It is the only way to build a practical computer: use the fastest storage closest to the CPU for the hottest data, and spill to progressively slower but cheaper storage for the rest.

Peter Norvig and Jeff Dean popularized a list of latency numbers that every programmer should have memorized. Here is a precise, current version anchored to a modern x86-64 processor (e.g., Intel Ice Lake or AMD Zen 3) running at ~3–4 GHz. One CPU cycle is roughly 0.3 ns at 3.3 GHz.

The key insight is the gaps are multiplicative, not additive:

• L1 → DRAM: ~30–100×
• DRAM → NVMe SSD: ~1000×
• DRAM → HDD: ~100,000×

Think of it this way: if an L1 cache hit takes 1 second on a human time scale, a RAM access takes 3 minutes, an NVMe read takes 3 days, and a hard disk seek takes 18 months.

These numbers are not trivia. A loop that should run in 10 ms can take 1 second if it repeatedly misses the cache and hits RAM. A database query that should complete in 1 ms can take 100 ms if it triggers random disk I/O.

/* Measure L1/L2/L3/RAM latency via pointer chasing.
   Compile: gcc -O2 -o lat lat.c && ./lat
   The pointer-chase pattern defeats hardware prefetchers. */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define STEPS 100000000UL

static long bench(size_t array_bytes) {
    size_t n = array_bytes / sizeof(size_t);
    size_t *arr = (size_t *)malloc(array_bytes);
    if (!arr) return -1;

    /* Build a random permutation (pointer chase) */
    for (size_t i = 0; i < n; i++) arr[i] = i;
    for (size_t i = n - 1; i > 0; i--) {
        size_t j = rand() % (i + 1);
        size_t t = arr[i]; arr[i] = arr[j]; arr[j] = t;
    }

    /* Chase the chain; each load depends on the previous */
    size_t idx = 0;
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (size_t s = 0; s < STEPS; s++)
        idx = arr[idx % n];
    clock_gettime(CLOCK_MONOTONIC, &t1);

    long ns = (t1.tv_sec - t0.tv_sec) * 1000000000L
              + (t1.tv_nsec - t0.tv_nsec);
    free(arr);
    (void)idx; /* prevent dead-code elimination */
    return ns / STEPS;
}

int main(void) {
    /* Sizes chosen to fit in L1, L2, L3, then spill to RAM */
    size_t sizes[] = {16*1024, 256*1024, 8*1024*1024, 128*1024*1024};
    const char *labels[] = {"L1 (16KB)", "L2 (256KB)", "L3 (8MB)", "RAM (128MB)"};
    for (int i = 0; i < 4; i++)
        printf("%-14s: ~%3ld ns/access\n", labels[i], bench(sizes[i]));
    return 0;
}

Registers are the CPU's working memory — the only storage that the ALU (Arithmetic Logic Unit) can operate on directly. On x86-64, you have 16 general-purpose 64-bit registers (rax, rbx, rcx, rdx, rsi, rdi, rsp, rbp, and r8–r15), 16 XMM/YMM/ZMM SIMD registers for floating-point and vector work, and special-purpose registers like the instruction pointer (rip) and flags register.

Register access has zero additional latency: the value is already inside the CPU execution units. This is why compilers spend enormous effort on register allocation — keeping frequently used variables in registers rather than spilling them to memory. When registers run out (a spill), the compiler must emit a mov to the stack (L1 cache), which costs a few cycles.

On modern out-of-order processors, the architectural registers (the ones you name in assembly) are mapped to a larger set of physical registers via the Register Alias Table (RAT) — a technique called register renaming. This allows the CPU to execute multiple independent instructions in parallel even when they reuse the same architectural register name.

On ARM64 (AArch64), the equivalent is 31 general-purpose 64-bit registers (x0–x30), with x31 serving as the zero register (reads always return 0) or the stack pointer depending on context. RISC-V RV64I has 32 registers (x0–x31), where x0 is hardwired to zero.

The key practical point: the compiler knows about registers and manages them for you in C. But when you write inline assembly, annotate SIMD intrinsics, or read kernel code that uses register hints or asm volatile, you are directly manipulating this tier.

/* See what your compiler does with registers.
   Compile and inspect: gcc -O2 -S -o reg.s reg.c
   Then look at reg.s — you'll see the loop variable
   stays entirely in a register (no memory traffic). */

long sum_array(const long *a, int n) {
    long s = 0;
    for (int i = 0; i < n; i++)
        s += a[i];   /* s lives in a register the whole time */
    return s;
}

/* The -O2 output on x86-64 looks roughly like:
   xor   eax, eax        ; s = 0  (register rax)
   xor   ecx, ecx        ; i = 0  (register rcx)
.loop:
   add   rax, [rdi+rcx*8] ; s += a[i]  (one memory load, then reg add)
   inc   ecx
   cmp   ecx, esi
   jl    .loop
   ret                    ; return value already in rax
*/

Caches do not load one byte at a time. They load cache lines — typically 64 bytes on modern x86-64 and ARM64 processors. This is the fundamental atomic unit of the entire memory hierarchy from L1 down through DRAM.

When you access a single byte that is not in cache (a cache miss), the hardware fetches the entire 64-byte cache line containing that byte. This is both a blessing and a curse:

Blessing — spatial locality: if your next access is to an address within those same 64 bytes (e.g., the next element in an array), it will be an L1 hit with no additional memory traffic. Sequential array traversal is nearly free after the first miss.

Curse — false sharing: if two CPU cores each write to different variables that happen to share a cache line, the hardware coherence protocol (MESI) forces them to fight over that line, causing performance to collapse even though the cores are writing to logically independent data.

You can verify the cache line size:

# Linux: check via sysfs
cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
# → 64

In the Linux kernel, you will see __cacheline_aligned on critical data structures and ____cacheline_aligned_in_smp on per-CPU counters — these are macros that force struct alignment to 64-byte boundaries to prevent false sharing.

A crucial corollary: a 64-byte cache line holds 8 × 64-bit integers, or 16 × 32-bit integers. An array of 1 million 64-bit integers occupies ~15,625 cache lines. Touching every element sequentially means ~15,625 cache misses (one per line). Jumping around randomly in that array means potentially 1,000,000 cache misses — 64× more traffic.

/* Demonstrate false sharing: two threads increment
   adjacent counters. The "bad" version packs them into
   one cache line; the "good" version pads them apart.
   Compile: gcc -O2 -pthread -o fs false_share.c */
#include <pthread.h>
#include <stdio.h>
#include <time.h>

#define ITERS 200000000L

typedef struct { long a; long b; }          bad_t;   /* share a cache line */
typedef struct { long a; char pad[56]; long b; } good_t; /* separate lines */

bad_t  bad  = {0, 0};
good_t good = {0, {0}, 0};

void *inc_bad_a(void *_)  { for (long i=0;i<ITERS;i++) bad.a++;  return NULL; }
void *inc_bad_b(void *_)  { for (long i=0;i<ITERS;i++) bad.b++;  return NULL; }
void *inc_good_a(void *_) { for (long i=0;i<ITERS;i++) good.a++; return NULL; }
void *inc_good_b(void *_) { for (long i=0;i<ITERS;i++) good.b++; return NULL; }

static double run(void *(*fa)(void*), void *(*fb)(void*)) {
    pthread_t ta, tb;
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    pthread_create(&ta, NULL, fa, NULL);
    pthread_create(&tb, NULL, fb, NULL);
    pthread_join(ta, NULL); pthread_join(tb, NULL);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    return (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) * 1e-9;
}

int main(void) {
    printf("false sharing (bad):  %.2f s\n", run(inc_bad_a,  inc_bad_b));
    printf("padded     (good):  %.2f s\n", run(inc_good_a, inc_good_b));
    return 0;
}

Modern CPUs have not one cache but a hierarchy of caches. Each level is larger and slower than the previous, and they operate as a team to bridge the gap between register speed and RAM speed.

L1 Cache: The fastest, smallest cache. On most modern cores it is split into L1i (instructions, typically 32 KB) and L1d (data, typically 32–64 KB). Latency is 4–5 cycles (~1–1.5 ns). It is private per core and physically sits next to the execution units. This is where your hot loop variables and frequently called code live.

L2 Cache: Larger (256 KB – 1 MB per core), unified (holds both instructions and data), latency ~12–20 cycles. Also typically private per core. Acts as a victim cache / second chance for L1 misses.

L3 Cache (LLC — Last Level Cache): Shared across all cores on the same socket. Sizes range from 8 MB (older budget parts) to 256 MB (AMD EPYC with 3D V-Cache). Latency ~40–80 cycles. Because it is shared, it serves as the rendezvous point for inter-core communication — when core 0 writes a cache line and core 1 reads it, the line moves through the L3.

Associativity: Caches are not fully associative (too expensive). L1 is typically 8-way set associative — a given memory address can only land in one of 8 specific "sets" within the cache. This means 8 specific slots compete for the same addresses. Programs with access patterns that hit the same set repeatedly suffer from conflict misses — data is evicted even though the cache is not logically full.

Inclusive vs exclusive caches: Intel's LLC is traditionally inclusive (a line in L1 is also in L3), which simplifies coherence. AMD's Zen architecture uses a mostly exclusive hierarchy (L3 does not duplicate L2 contents), which gives more effective capacity.

Write policies:

• Write-back: writes go only to the cache; the dirty line is written to the next level only when evicted. Reduces bandwidth. Used by almost all modern CPUs.
• Write-through: every write immediately propagates to the next level. Simpler coherence, wastes bandwidth.

On a Linux system you can inspect the full cache topology:

lscpu | grep -i cache
# Or the detailed per-level breakdown:
ls /sys/devices/system/cpu/cpu0/cache/

/* Cache-size detection via timing.
   A stride-1 sequential scan of an array reveals when
   we spill from one cache level to the next — bandwidth
   (bytes/ns) drops sharply at each boundary.
   Compile: gcc -O2 -o scan scan.c && ./scan */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAX_SIZE (256*1024*1024)
#define REPEAT   8

int main(void) {
    char *buf = (char *)malloc(MAX_SIZE);
    memset(buf, 1, MAX_SIZE);

    printf("%-10s  %8s  %10s\n", "Size", "MB/s", "ns/byte");
    for (size_t sz = 4096; sz <= MAX_SIZE; sz *= 2) {
        volatile long sum = 0;
        struct timespec t0, t1;
        clock_gettime(CLOCK_MONOTONIC, &t0);
        for (int r = 0; r < REPEAT; r++)
            for (size_t i = 0; i < sz; i += 64)
                sum += buf[i];   /* stride-64 = one access per cache line */
        clock_gettime(CLOCK_MONOTONIC, &t1);
        (void)sum;
        double ns = (t1.tv_sec-t0.tv_sec)*1e9 + (t1.tv_nsec-t0.tv_nsec);
        double accesses = (double)sz/64 * REPEAT;
        double ns_per  = ns / accesses;
        printf("%-10zu  %8.0f  %10.2f\n",
               sz, accesses*64/ns*1e3, ns_per);
    }
    free(buf);
    return 0;
}

The entire cache hierarchy is a bet on one empirical observation about programs: real programs reuse data and instruction addresses. This is called the principle of locality, and it has two flavors:

Temporal locality: if you access a memory location now, you are likely to access it again soon. A loop counter, a frequently called function, a hot struct field — these exhibit temporal locality. The cache exploits this by keeping recently accessed lines resident.

Spatial locality: if you access address X, you are likely to access addresses near X soon. Array traversal, struct field access, function prologues — these all exhibit spatial locality. The 64-byte cache line exploits this by loading neighbors for free.

A third, less commonly named variant is sequential locality (a special case of spatial): instruction fetching is almost always sequential, so the hardware's instruction prefetcher reliably keeps ahead of execution.

Locality is not just a hardware trick — it is a design principle you should apply actively:

• Array of Structs vs Struct of Arrays (AoS vs SoA): If you have 1,000,000 particles and you only ever iterate over velocity, a SoA layout (all velocities packed together) has perfect spatial locality for that field. An AoS layout loads position and mass into cache alongside every velocity — wasting 2/3 of every cache line.

• Cache-oblivious algorithms: Algorithms like recursive matrix multiplication automatically have good cache behavior at all levels of the hierarchy without knowing cache sizes, by dividing the problem recursively until it fits.

• Loop tiling/blocking: When multiplying two matrices, a naive triple loop has poor spatial locality for one matrix (column access). Blocking the loop so that a submatrix fits in cache dramatically improves performance.

Kernel examples: the page allocator's buddy system processes pages in order of alignment, maximizing spatial locality in the free-list traversal. The SLAB allocator returns same-type objects from a local cache to preserve temporal locality for the object's hot fields.

/* AoS vs SoA: measure the cache impact of layout.
   We iterate a million particles updating only velocity.
   Compile: gcc -O2 -o layout layout.c && ./layout */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define N 1000000
#define ITERS 100

/* Array-of-Structs: all fields interleaved */
typedef struct { float x, y, z; float vx, vy, vz; float mass; float pad; } Particle;

/* Struct-of-Arrays: each field in its own array */
typedef struct {
    float *x, *y, *z;
    float *vx, *vy, *vz;
    float *mass;
} ParticleSoA;

static double now_ns(void) {
    struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec * 1e9 + t.tv_nsec;
}

int main(void) {
    Particle   *aos = calloc(N, sizeof(Particle));
    ParticleSoA soa;
    soa.vx = calloc(N, sizeof(float)); soa.vy = calloc(N, sizeof(float));
    soa.vz = calloc(N, sizeof(float)); soa.x  = calloc(N, sizeof(float));
    soa.y  = calloc(N, sizeof(float)); soa.z  = calloc(N, sizeof(float));
    soa.mass = calloc(N, sizeof(float));
    for (int i = 0; i < N; i++) { soa.mass[i] = aos[i].mass = 1.0f + i*0.001f; soa.vx[i] = 1.0f; }

    float force = 9.8f;
    double t0 = now_ns();
    for (int iter = 0; iter < ITERS; iter++)
        for (int i = 0; i < N; i++)
            aos[i].vx += force / aos[i].mass;   /* loads 32 bytes to use 8 */
    printf("AoS: %.1f ms\n", (now_ns()-t0)/1e6);

    t0 = now_ns();
    for (int iter = 0; iter < ITERS; iter++)
        for (int i = 0; i < N; i++)
            soa.vx[i] += force / soa.mass[i];   /* all loads are useful */
    printf("SoA: %.1f ms\n", (now_ns()-t0)/1e6);

    free(aos); free(soa.vx); free(soa.vy); free(soa.vz);
    free(soa.x); free(soa.y); free(soa.z); free(soa.mass);
    return 0;
}

Modern CPUs include hardware prefetchers — dedicated logic that watches your access patterns and tries to load cache lines before you ask for them, hiding the latency behind useful work.

There are typically two hardware prefetchers for data:

1. Stream prefetcher: detects sequential or strided access and speculatively fetches ahead. This is why sequential array traversal often looks as fast as register-only code.
2. Stride prefetcher: detects a constant stride (e.g., every 128 bytes) and prefetches at that stride.

The hardware prefetcher is smart but not omniscient. It fails with:

• Pointer chasing (linked lists, trees): the next address is inside the current load's result — you cannot know it until the current load completes. This is why linked-list traversal is a cache-miss disaster.
• Irregular or data-dependent access patterns: a hash table lookup depends on the hash value, which depends on the key.
• Very large strides: prefetchers typically give up at strides > a few KB.

Software prefetch instructions let you explicitly load a cache line into cache before you need it. In C, this is __builtin_prefetch(addr, rw, locality). In x86 assembly it is PREFETCHT0/T1/T2/NTA. In Linux kernel C, the macros are prefetch(addr) and prefetchw(addr) (defined in <linux/prefetch.h>).

Software prefetch is most useful when you know you will need data N iterations ahead in a loop and the hardware prefetcher cannot figure it out (e.g., following a linked list where you can look ahead by 1 node).

However, use with caution: excessive prefetching pollutes caches and can make things worse. The rule is: measure first, prefetch second.

/* Manual prefetch for linked-list traversal.
   Prefetch the next-next node while processing the current one.
   Compile: gcc -O2 -o pfetch pfetch.c */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 1000000

typedef struct Node { long val; struct Node *next; } Node;

static double now_ns(void) {
    struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec*1e9 + t.tv_nsec;
}

int main(void) {
    /* Build a shuffled linked list (random pointer order) */
    Node *nodes = malloc(N * sizeof(Node));
    int  *perm  = malloc(N * sizeof(int));
    for (int i = 0; i < N; i++) perm[i] = i;
    for (int i = N-1; i > 0; i--) { int j=rand()%(i+1); int t=perm[i]; perm[i]=perm[j]; perm[j]=t; }
    for (int i = 0; i < N-1; i++) { nodes[perm[i]].val = i; nodes[perm[i]].next = &nodes[perm[i+1]]; }
    nodes[perm[N-1]].val = N-1; nodes[perm[N-1]].next = NULL;
    Node *head = &nodes[perm[0]];

    /* Without prefetch */
    long sum = 0;
    double t0 = now_ns();
    for (Node *p = head; p; p = p->next) sum += p->val;
    printf("No prefetch:   %.1f ms  (sum=%ld)\n", (now_ns()-t0)/1e6, sum);

    /* With prefetch: look 4 nodes ahead */
    sum = 0;
    t0 = now_ns();
    Node *p = head;
    Node *pf = head;
    /* Advance prefetch pointer 4 steps ahead first */
    for (int i = 0; i < 4 && pf->next; i++) pf = pf->next;
    while (p) {
        if (pf->next) { pf = pf->next; __builtin_prefetch(pf, 0, 1); }
        sum += p->val;
        p = p->next;
    }
    printf("With prefetch: %.1f ms  (sum=%ld)\n", (now_ns()-t0)/1e6, sum);

    free(nodes); free(perm);
    return 0;
}

Main memory is built from DRAM chips organized into DIMMs (Dual In-line Memory Modules). Understanding DRAM internals helps you reason about why RAM latency is what it is and why it cannot simply be made faster.

DRAM internal structure: A DRAM chip is organized as a 2D array of capacitors. The array is divided into banks (typically 8–16 per chip), and each bank has rows (also called pages, ~8 KB each). To access data:

1. Row activation (RAS — Row Address Strobe): the row must be opened (sense amplifiers latch the entire row into a row buffer). ~15 ns.
2. Column access (CAS — Column Address Strobe): select the specific columns from the open row. ~15 ns.
3. Precharge: close the row, restore charge to the bit lines. ~15 ns.
4. Data transfer: burst the data over the memory bus.

If the next access hits the same open row, steps 1 and 3 are skipped — this is called an open-row hit and is much faster. This is why sequential access to a large array is faster than random access: sequential access keeps the same DRAM row open.

Refresh: DRAM capacitors leak charge. Every cell must be refreshed every ~64 ms. The memory controller issues periodic refresh commands that stall access for ~350 ns each. At scale, this DRAM refresh tax becomes measurable.

DRAM channels and interleaving: Modern systems have 2–8 memory channels. A 4-channel DDR5 system can deliver 4× the bandwidth of a single channel. The memory controller interleaves addresses across channels to spread requests.

NUMA (Non-Uniform Memory Access): On multi-socket servers, each CPU socket has its own local DRAM. Accessing memory attached to a remote socket (NUMA remote access) is 1.5–3× slower than local access. The Linux kernel is deeply NUMA-aware: alloc_pages_node(), per-node free lists in the buddy allocator, and numactl all exist to manage this.

# Check DRAM details and NUMA topology on Linux
lscpu | grep -i numa
numactl --hardware
# Shows nodes, their memory sizes, and the inter-node distance matrix
# Distance 10 = local, 20 = one hop, higher = farther

# Check memory channel/slot info
sudo dmidecode -t memory | grep -E 'Speed|Size|Locator|Type:'

# On a NUMA machine: bind a process to node 0's CPUs and memory
numactl --cpunodebind=0 --membind=0 ./my_program

When a cache is full and a new line must be loaded, the cache controller must evict an existing line. The choice of which line to evict is the replacement policy:

• LRU (Least Recently Used): evict the line that was accessed least recently. Optimal in theory for typical working sets. True LRU is expensive to implement in hardware for large associativity, so CPUs use approximate LRU (e.g., PLRU — Pseudo-LRU, using a binary tree of 1-bit flags).

• FIFO: evict the oldest line regardless of access history. Simpler but worse for hot data that was loaded long ago.

• Random: evict a random line. Surprisingly competitive with LRU for large caches due to its immunity to adversarial access patterns.

• RRIP (Re-Reference Interval Prediction): a modern policy used in Intel's LLC that assigns each line a "re-reference prediction value" and evicts lines predicted to be reused far in the future. Better than LRU for scan-dominated workloads.

Cache thrashing is a pathological situation where the program's working set (the set of cache lines actively needed at one time) exceeds the cache capacity. In a set-associative cache, thrashing can occur even when the working set should fit, if too many addresses map to the same set (conflict misses).

Classic example: multiplying two 512×512 matrices of doubles. The three arrays total ~6 MB. If your L3 is 8 MB they should fit. But with a naive triple loop, the access to matrix B is column-major — each access is 512 × 8 = 4096 bytes apart, causing a new cache miss for every B element. Loop tiling (blocking the loop to process 64×64 submatrices at a time) fixes this by ensuring each submatrix fits in L1/L2.

In the Linux kernel, this is why vmalloc-allocated memory (which can be physically non-contiguous) is slower than kmalloc-allocated memory (physically contiguous): contiguous physical memory has better cache behavior because the hardware prefetcher works on physical addresses.

/* Matrix multiply: naive vs tiled.
   For large N, tiled is dramatically faster due to cache reuse.
   Compile: gcc -O2 -o matmul matmul.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define N   512
#define TILE 64

static double A[N][N], B[N][N], C[N][N];

static double now(void) {
    struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec + t.tv_nsec*1e-9;
}

void naive(void) {
    for (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]; /* B[k][j]: column-major = cache miss per step */
}

void tiled(void) {
    for (int i=0;i<N;i+=TILE) for (int j=0;j<N;j+=TILE) for (int k=0;k<N;k+=TILE)
        for (int ii=i;ii<i+TILE&&ii<N;ii++)
            for (int jj=j;jj<j+TILE&&jj<N;jj++)
                for (int kk=k;kk<k+TILE&&kk<N;kk++)
                    C[ii][jj] += A[ii][kk] * B[kk][jj]; /* B subblock stays in cache */
}

int main(void) {
    for (int i=0;i<N;i++) for (int j=0;j<N;j++) { A[i][j]=i+j; B[i][j]=i-j; }
    memset(C,0,sizeof C);
    double t0=now(); naive(); printf("Naive: %.2f s\n", now()-t0);
    memset(C,0,sizeof C);
    t0=now(); tiled(); printf("Tiled: %.2f s\n", now()-t0);
    return 0;
}

Below RAM sits persistent storage — the tier that survives power loss. The gap between RAM and storage is not just latency but also interface: RAM is byte-addressable (the CPU can read a single byte), while storage is block-addressed (you read and write in sectors, typically 512 bytes or 4 KB).

Hard Disk Drives (HDDs): Data is stored as magnetic domains on spinning platters. A read requires:

1. Seek: the arm moves to the correct track. ~5–10 ms average.
2. Rotational latency: waiting for the sector to rotate under the head. ~4 ms average at 7200 RPM.
3. Transfer: reading the data as it passes the head. ~100 MB/s. Total random 4 KB read: ~10 ms. This is 100,000× slower than RAM for random access. HDDs are still relevant for cold storage due to low cost per GB ($15–20/TB vs ~$80–100/TB for SATA SSD).

SATA SSDs: Flash chips connected via the SATA interface (max 550 MB/s). Random 4 KB read ~100 µs. No mechanical parts means no seek time, but NAND flash requires an FTL (Flash Translation Layer) to manage wear leveling, garbage collection, and the mismatch between write granularity (page ~4–16 KB) and erase granularity (block ~256 KB).

NVMe SSDs: Flash chips connected directly to PCIe lanes, bypassing the SATA bottleneck. PCIe Gen 4 NVMe: ~7 GB/s sequential, ~50–100 µs random 4 KB reads. The NVMe protocol supports 65,535 command queues with 65,535 commands each, vs SATA's single queue of 32 — parallelism matters for SSDs.

The Linux I/O Stack: A read() syscall travels through: VFS → file system (ext4/xfs/btrfs) → page cache check → block layer → I/O scheduler → device driver → hardware. The page cache is key: Linux caches recently read disk blocks in RAM. On the second read() of a file, you hit the page cache — RAM latency, not disk latency. sync() and fsync() flush the page cache to persistent storage.

# Check page cache statistics
free -h             # 'buff/cache' is the page cache
cat /proc/meminfo | grep -i cache
# Drop the page cache (as root) to force cold reads:
echo 3 > /proc/sys/vm/drop_caches

io_uring: Linux 5.1+ introduced io_uring, a shared-memory ring buffer interface between userspace and kernel that eliminates syscall overhead for high-IOPS workloads. It is now the preferred interface for storage-intensive applications.

/* Measure cold vs warm read latency (page cache effect).
   Run as: sudo bash -c 'echo 3 > /proc/sys/vm/drop_caches' first
   for the cold measurement.
   Compile: gcc -O2 -o readbench readbench.c */
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(int argc, char **argv) {
    const char *path = argc > 1 ? argv[1] : "/usr/bin/gcc";
    char buf[4096];
    struct timespec t0, t1;

    for (int trial = 0; trial < 3; trial++) {
        int fd = open(path, O_RDONLY);
        if (fd < 0) { perror("open"); return 1; }
        clock_gettime(CLOCK_MONOTONIC, &t0);
        ssize_t n = read(fd, buf, sizeof(buf));  /* first 4 KB */
        clock_gettime(CLOCK_MONOTONIC, &t1);
        close(fd);
        printf("Trial %d: %ld bytes in %ld µs\n", trial+1, (long)n,
               (t1.tv_nsec - t0.tv_nsec + (t1.tv_sec-t0.tv_sec)*1000000000L) / 1000);
        /* Trial 1: potentially cold (disk). Trial 2+: warm (page cache). */
    }
    return 0;
}

Knowing the theory is not enough — you need tools to see which level of the hierarchy your program is hitting. Linux provides excellent tooling.

perf stat: uses hardware performance counters (PMU — Performance Monitoring Unit) built into the CPU. These counters can directly measure cache misses, TLB misses, branch mispredictions, and more.

perf stat -e cache-references,cache-misses,\
L1-dcache-loads,L1-dcache-load-misses,\
LLC-loads,LLC-load-misses ./my_program

Key metrics:

• L1-dcache-load-misses / L1-dcache-loads: L1 miss rate. Below 1% is great; above 5% warrants investigation.
• LLC-load-misses: every one of these is a RAM access (~100 ns).
• Instructions per cycle (IPC): a memory-bound program has low IPC because the CPU stalls waiting for data.

perf record + perf report: samples the program and shows which functions and lines cause the most cache misses.

perf record -e LLC-load-misses -g ./my_program
perf report

valgrind --tool=cachegrind: simulates a CPU's cache hierarchy and counts every L1/L2/L3 miss. Slower than perf (simulation, not hardware counters) but does not require root, and works without hardware counter support.

valgrind --tool=cachegrind --cache-sim=yes ./my_program
cg_annotate cachegrind.out.<pid>  # annotated source-level view

heaptrack / massif: track heap allocation patterns, useful for finding allocator overhead that causes cache fragmentation.

In the Linux kernel itself, the perf subsystem was developed partly by kernel developers for kernel profiling. perf top is the kernel equivalent of top but measured in CPU cycles per function.

# Profile an existing binary for cache misses
# (replace ./my_program with your binary)

# Quick summary of cache behavior:
perf stat -e instructions,cycles,\
cache-references,cache-misses,\
L1-dcache-loads,L1-dcache-load-misses,\
LLC-loads,LLC-load-misses \
./my_program 2>&1 | tail -20

# Sample which code causes LLC misses (requires root or paranoid=1):
# echo 1 | sudo tee /proc/sys/kernel/perf_event_paranoid
perf record -e LLC-load-misses -F 997 -g ./my_program
perf report --stdio | head -40

# cachegrind (no root needed):
valgrind --tool=cachegrind ./my_program
# Then: cg_annotate cachegrind.out.$(ls -t cachegrind.out.* | head -1 | grep -o '[0-9]*')