Memory in modern computers is hierarchical, not uniform. Understanding the hierarchy explains why some code is fast and some slow even when the algorithms are the same.
This page covers the memory hierarchy and its software implications.
From fastest to slowest:
| Level | Capacity | Latency | Bandwidth |
|---|---|---|---|
| Registers | ~256 bytes | <1 ns | ~TB/s |
| L1 cache | 32-64 KB | ~1 ns | hundreds of GB/s |
| L2 cache | 256 KB - 2 MB | ~3-10 ns | hundreds of GB/s |
| L3 cache | 4-128 MB | ~10-30 ns | hundreds of GB/s |
| RAM | GBs | ~50-100 ns | ~25-50 GB/s |
| SSD | TBs | ~10-100 μs | GB/s |
| HDD | TBs | ~10 ms | hundreds of MB/s |
| Network storage | PBs | ms+ | depends |
Each level is roughly 10x slower and 10x larger than the level above.
Single fast/large memory would be ideal. Physics and economics conflict:
Hierarchy gives an effective speed close to fastest level (when cache hits) and capacity of slowest level.
Per-core. Split into instruction (L1i) and data (L1d).
Smallest, fastest. Hit determines whether instruction runs immediately or waits.
Per-core (usually). Larger, slightly slower.
Shared across cores. Largest CPU cache.
Provides cache coherence reference for inter-core communication.
Unit of cache management. Typically 64 bytes.
Memory is read/written in cache lines. Touching one byte loads 64.
Has profound implications for data layout.
Cache hit: data in cache, fast access.
Cache miss: must fetch from slower level. Slow.
CPU predicts what memory you'll access; loads it early.
Sequential access patterns prefetch well; random doesn't.
Cache full; old data evicted to make room.
Policies: LRU (or approximations), random.
Iterate through arrays in order. Prefetcher loves this.
Avoid splitting hot data across cache lines.
Smaller types fit more in cache.
Linked lists, trees with pointers cause cache misses.
Arrays are cache-friendly; pointer-based structures often aren't.
Use data soon after touching nearby data. Stays in cache.
Multiple cores writing different fields in same cache line. Each write invalidates other cores' caches.
Symptom: parallel code mysteriously slow.
Solution: pad data to cache line boundaries; separate hot fields.
In multi-socket systems:
NUMA-aware programming:
OS schedulers and allocators are NUMA-aware to some extent. Critical workloads need explicit attention.
OS abstraction: each process sees its own address space.
Map virtual addresses to physical. Hardware MMU translates.
Caches recent translations. TLB miss is expensive (full page table walk).
Virtual page not in physical memory. OS handles, possibly loading from disk.
Major faults (disk I/O) are very slow (~10ms).
Standard pages: 4KB. Huge: 2MB or 1GB.
Fewer page table entries; better TLB hit rate.
Used for performance-critical apps with large working sets.
Modern DDR4/DDR5:
Latency hasn't improved much over decades. Bandwidth has.
For LLM inference: bandwidth is often the bottleneck.
Sequential reads can hit max bandwidth.
Random reads: latency-bound; effective bandwidth much lower.
A program reading random 8-byte values from RAM: ~50ns each. For 25 GB/s peak, that's 5 GB/s actually achieved (160M ops/sec). Sequential could hit 25 GB/s of real data.
NAND flash. Block-based read/write.
Read latency: tens of microseconds. Write latency: depends on technology. Wear: limited write cycles per cell.
NVMe: PCIe-connected SSD. Fast.
Spinning platters. Mechanical seek time dominates.
Sequential: ~200 MB/s. Random: limited by seek time (~10ms each).
Byte-addressable persistent memory. Slower than DRAM, faster than SSD.
Niche product line.
Hardware prefetcher kicks in. Effective bandwidth approaches peak.
Access pattern with fixed stride. Prefetcher may detect.
If stride > cache line, every access is a miss.
Worst case. Each access pays full latency.
Designed to work well at all levels of hierarchy without tuning.
Examples: cache-oblivious matrix multiplication.
Process data in chunks that fit in cache.
Matrix multiplication: blocking is huge speedup.
B-trees over binary trees for cache friendliness.
Arrays of structures (AoS) vs structures of arrays (SoA) tradeoffs.
In-place where possible. Reduces working set.
CPU speeds grew faster than memory speeds. Memory access dominates many workloads.
Solution: more cache, smarter prefetching, GPU-style throughput computing.
Memory access uses far more energy than computation.
For mobile / edge: reducing memory traffic matters.
struct Point { float x, y, z; };
Point points[N];
Good when accessing whole structs.
float xs[N], ys[N], zs[N];
Good when accessing one field across many elements (vectorization).
Critical data hot, less-used cold. Lay out to keep hot data dense.
Code that ignores locality is slow.
Linked lists, deep object graphs. Cache misses dominate.
In multi-socket systems, ignoring NUMA wastes bandwidth.
Subtle multi-threaded performance bug.
When data exceeds RAM, random access becomes catastrophic.
Working set exceeds TLB. Lots of page table walks.
Tools:
Key counters:
For most application code: standard library defaults are good. Optimization matters when profiling reveals memory-bound code.