Memory Hierarchy

Definition: The layered organization of computer storage, from registers down through multiple cache levels, main memory, and disk, arranged by tradeoffs between speed, cost per byte, and capacity.

How It Works

Registers: inside the CPU core itself, sub-nanosecond access, capacity measured in bytes to low hundreds of bytes; see CPU Core and Registers
L1 Cache: roughly 1 ns latency, roughly 32-64 KB per core, split into L1i (instructions) and L1d (data) since fetch and data access patterns differ enough to benefit from separate caches
L2 Cache: roughly 3-5 ns latency, roughly 256 KB-2 MB, usually private per core, unified (instructions and data together)
L3 Cache: roughly 10-20 ns latency, tens of MB, typically shared across all cores on the chip, acting as a last defense before falling all the way to main memory
Main Memory (RAM): roughly 50-100 ns latency, tens to hundreds of GB, volatile (loses contents on power loss), managed by the OS’s virtual memory system
SSD/NVMe storage: roughly 10-100 microseconds latency, TB-scale, non-volatile
HDD storage: roughly 5-10 milliseconds latency (dominated by mechanical seek time), TB-scale, cheapest per byte, non-volatile
Each level down the hierarchy trades roughly an order of magnitude more latency for roughly an order of magnitude more capacity at a lower cost per byte, which is the entire economic reason a hierarchy exists instead of one uniform memory type
The hierarchy works because of temporal locality (recently accessed data is likely to be accessed again soon) and spatial locality (data near a recently accessed address is likely to be accessed soon too), both exploited automatically by caching a full line around any requested address, see Cache Line and Eviction
Virtual memory adds an address-translation layer between what a program sees and physical RAM, letting the OS give each process its own private address space and swap rarely used pages out to disk; the Translation Lookaside Buffer (TLB), itself a small cache of recent virtual-to-physical address translations, sits alongside the data caches and a TLB miss adds its own latency penalty on top of any data cache miss
NUMA (Non-Uniform Memory Access) on multi-socket servers means RAM attached to a different CPU socket than the one running a thread has higher latency to reach than “local” RAM, effectively adding another tier to the hierarchy that spans physical sockets, not just cache levels
Memory bandwidth and latency are distinct: a system can have high peak bandwidth (bytes/second when moving large sequential blocks) while still suffering badly on latency-bound workloads (many small, dependent, scattered accesses) that never get to exploit that bandwidth

Under the Hood

Given: a program repeatedly reads a 16 KB lookup table inside a tight loop. Step 1: on the first pass, every element is a miss at every level, forcing a full trip to RAM (~50-100 ns per line). Step 2: since the table (16 KB) fits comfortably inside L1 (32-64 KB), every subsequent pass hits entirely in L1 (~1 ns per access). Answer: after the first pass, the effective per-access latency drops by roughly 50-100x, which is the entire performance argument for keeping working sets small enough to fit in cache.

Given: the same 16 KB table, but now the loop also touches 2 MB of unrelated scratch data between passes, evicting the table from L1 and L2 but not L3. Step: every table access now costs an L3 hit (~10-20 ns) instead of an L1 hit (~1 ns), still far cheaper than a full RAM round-trip, but 10-20x slower than when it fit in L1. Answer: performance degrades gracefully level by level as working-set size grows past each cache’s capacity, rather than falling off a single cliff, exactly what a multi-level hierarchy is designed to provide.

Given: a matrix multiplication of two 2000x2000 double-precision matrices, naively coded with three nested loops. Step 1: the naive version streams through rows and columns in a pattern that repeatedly evicts and reloads large chunks of both matrices from RAM, since the full working set (tens of MB) far exceeds L2/L3 capacity. Step 2: a blocked/tiled version processes the matrices in small sub-blocks sized to fit inside L1 or L2, reusing each loaded block many times before moving to the next. Answer: blocking commonly yields a 5-10x speedup on large matrix multiplication with zero change to the actual arithmetic performed, purely from respecting the memory hierarchy’s capacity limits at each level.

latency ladder (approximate, relative to L1 = 1x):
  L1    1 ns      1x
  L2    4 ns      4x
  L3    15 ns     15x
  RAM   80 ns     80x
  SSD   50 us     50,000x
  HDD   7 ms      7,000,000x

Why It Matters

Explains why “more RAM” or “more CPU cores” alone doesn’t guarantee more performance: if an algorithm’s access pattern doesn’t respect locality, no amount of raw memory bandwidth compensates for hundreds of cycles of round-trip latency per miss
Cache-aware and cache-oblivious algorithm design (blocking/tiling matrix multiplication, B-trees sized to cache-line/page boundaries) exist specifically to keep hot data resident at the fastest hierarchy level that fits it
Virtual memory and the OS page cache extend this same hierarchy logic into software: the OS keeps recently used disk pages resident in RAM, applying the identical locality principle one more level down

Common Pitfalls

Cache stalls: fetching data not present in any cache level forces the CPU to sit effectively idle for hundreds of cycles waiting on RAM, a cost algorithmic complexity analysis (Big-O) doesn’t account for at all
Assuming latency numbers are fixed constants: actual latency depends on contention (other cores/threads sharing L3 and memory bandwidth), NUMA topology on multi-socket systems, and whether a translation lookaside buffer (TLB) miss also has to be resolved
Sizing a data structure without considering which cache level it needs to fit in; a hash table slightly larger than L2 can perform dramatically worse than one slightly smaller, for the same logical operation count
Ignoring that SSD and HDD latency differences (roughly 100-1000x) matter enormously for I/O-bound software design, even though both are commonly lumped together as “disk” in casual discussion
Forgetting NUMA effects on multi-socket servers: allocating memory on one socket and running the consuming thread on another can silently double or triple effective RAM latency for that thread’s accesses
Over-trusting Big-O complexity analysis alone for performance prediction: an O(n log n) algorithm with poor locality can lose to an O(n^2) algorithm with excellent locality on realistic input sizes, since the hierarchy’s latency gaps dwarf small constant-factor differences

Comparison

Level	Latency	Typical size	Volatile	Managed by
Registers	< 1 ns	Bytes	Yes	Compiler/hardware
L1	~1 ns	~32-64 KB	Yes	Hardware
L2	~3-5 ns	~256 KB-2 MB	Yes	Hardware
L3	~10-20 ns	Tens of MB	Yes	Hardware, shared
RAM	~50-100 ns	Tens-hundreds of GB	Yes	OS virtual memory
SSD	~10-100 us	TBs	No	OS filesystem
HDD	~5-10 ms	TBs	No	OS filesystem

Locality type	What it means	Exploited by
Temporal	Recently used data reused soon	Any caching level, keeping recent lines
Spatial	Nearby addresses used soon	Cache lines, prefetchers, sequential I/O

Example

An Intel Core i9 or AMD Ryzen 9 desktop chip typically has 32-48 KB L1d per core, 1-2 MB L2 per core, and 16-36 MB of shared L3, feeding into 32-128 GB of DDR5 RAM at roughly 60-100 ns latency, backed by an NVMe SSD at roughly 50-100 microseconds. Database engines like PostgreSQL explicitly tune buffer pool sizes and B-tree page sizes around exactly these numbers, since a query that stays resident in RAM instead of hitting disk can be 1000x faster for the identical logical operation.

Cloud instance types make this hierarchy a purchasing decision, not just a hardware fact: AWS’s memory-optimized instances (the r family) exist specifically to keep more of a working set resident in RAM rather than paying disk latency, while cache-optimized workloads (Redis, Memcached) are sized and priced around exactly how much hot data fits in RAM across a cluster.

Given: a web application’s response time suddenly gets 50x slower once its user table grows past a few million rows. Step 1: below that size, the table’s frequently accessed index pages fit entirely in the database’s RAM-resident buffer pool, so most reads never touch disk. Step 2: past that size, the working set exceeds available RAM, and queries increasingly force real disk (or even network-attached storage) round-trips at millisecond-scale latency instead of RAM’s nanosecond-scale latency. Answer: this is the memory hierarchy made visible as a business incident: the fix is rarely “optimize the query” alone, it’s recognizing which hierarchy level the working set now falls into and provisioning (more RAM, better indexing, a caching layer) accordingly.

Referenced by

Dig deeper

Spot an error in this note?