Home/Learn/Operating Systems/Memory Hierarchy

Memory Hierarchy

Beginner

Memory Management

The memory hierarchy arranges storage from fastest and smallest (registers) to slowest and largest (network storage), exploiting the principle of locality to make programs run efficiently.

Overview

No single memory technology can be simultaneously fast, large, and cheap — these three goals are in fundamental tension. The memory hierarchy solves this by layering storage: CPU registers (< 1 ns, bytes) → L1 cache (1 ns, 32 KB) → L2 cache (4 ns, 256 KB) → L3 cache (10 ns, 8–32 MB) → RAM (100 ns, GBs) → SSD (100 µs, TBs) → HDD (10 ms, TBs) → Network storage (ms–s, PBs). The system works because of the principle of locality: temporal locality (recently accessed data is likely to be accessed again) and spatial locality (data near recently accessed data is likely to be accessed). CPU caches exploit these patterns with 64-byte cache lines — loading a chunk of memory at once. Java performance implications: arrays are cache-friendly (contiguous memory); linked lists cause cache misses (pointer-chasing across heap).

Cache Lines and Spatial Locality

When the CPU reads one byte from RAM, it fetches an entire 64-byte cache line. If your program accesses sequential memory addresses (array traversal), subsequent accesses are already in the cache — very fast. If your program chases pointers to random memory locations (linked list traversal), every access is a cache miss — the CPU must wait 100+ ns for RAM each time. This single difference can cause a 10x–100x performance gap.

Java — array (cache-friendly) vs LinkedList (cache-unfriendly) benchmark

// Cache-friendly (array) vs cache-unfriendly (LinkedList) traversal
int SIZE = 10_000_000;

// Array: contiguous memory — excellent spatial locality
int[] array = new int[SIZE];
Arrays.fill(array, 1);

long start = System.nanoTime();
long sum = 0;
for (int x : array) sum += x;   // sequential access → CPU prefetcher works perfectly
long arrayTime = System.nanoTime() - start;

// LinkedList: each node is a separate heap object — random memory locations
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < SIZE; i++) list.add(1);

start = System.nanoTime();
sum = 0;
for (int x : list) sum += x;   // pointer-chasing → cache miss on every node!
long listTime = System.nanoTime() - start;

System.out.printf("Array traversal:      %d ms%n", arrayTime  / 1_000_000);
System.out.printf("LinkedList traversal: %d ms%n", listTime   / 1_000_000);
System.out.printf("Speedup:              %.1fx%n", (double) listTime / arrayTime);
// Typical result: array is 5x–20x faster than LinkedList for sequential traversal

Temporal Locality and the Cost of Abstraction

Temporal locality means recently used data is likely to be used again. Hot variables (loop counters, accumulators) get promoted to CPU registers by the JIT compiler. Warm data stays in L1/L2 cache. Cold data (rarely accessed) sits in RAM. Understanding this guides Java performance: keep frequently accessed objects small and alive in cache, avoid large object graphs for hot code paths, and prefer primitive arrays over boxed collections in tight loops.

Java — row-major vs column-major matrix access, cache locality impact

// Temporal locality: loop variables stay in registers/L1 cache
long total = 0;                          // → promoted to CPU register by JIT
for (int i = 0; i < 100_000_000; i++) {
    total += i;   // 'total' and 'i' are accessed every iteration — L1/register
}

// Cache-unfriendly: accessing a 2D matrix in column-major order
// (Java arrays are row-major in memory)
int ROWS = 1000, COLS = 1000;
int[][] matrix = new int[ROWS][COLS];

// ROW-MAJOR (cache-friendly): sequential access within each row
long t1 = System.nanoTime();
for (int r = 0; r < ROWS; r++)
    for (int c = 0; c < COLS; c++)
        matrix[r][c] = r * COLS + c;   // contiguous — good spatial locality
long rowTime = System.nanoTime() - t1;

// COLUMN-MAJOR (cache-unfriendly): jumps ROWS apart in memory each step
long t2 = System.nanoTime();
for (int c = 0; c < COLS; c++)
    for (int r = 0; r < ROWS; r++)
        matrix[r][c] = r * COLS + c;   // each access = different cache line!
long colTime = System.nanoTime() - t2;

System.out.printf("Row-major:    %d ms%n", rowTime / 1_000_000);
System.out.printf("Column-major: %d ms%n", colTime / 1_000_000);
// Column-major is typically 3x–10x slower due to cache misses

Memory Hierarchy Latency Numbers

Jeff Dean's famous "latency numbers every programmer should know" quantify the memory hierarchy. Knowing these numbers helps you make informed architectural decisions: is it worth caching this? Should I use off-heap memory? Is a round-trip to a remote database worth the latency for this query?

Java — memory hierarchy latency table + JVM heap inspection

// Memory hierarchy latency reference (approximate, modern hardware)
// ┌──────────────────────────┬────────────┬───────────┐
// │ Level                    │ Latency    │ Capacity  │
// ├──────────────────────────┼────────────┼───────────┤
// │ CPU Register             │ < 1 ns     │ ~256 B    │
// │ L1 Cache (per core)      │ ~1 ns      │ 32–64 KB  │
// │ L2 Cache (per core)      │ ~4 ns      │ 256 KB    │
// │ L3 Cache (shared)        │ ~10 ns     │ 8–64 MB   │
// │ Main Memory (RAM)        │ ~100 ns    │ GBs       │
// │ NVMe SSD                 │ ~100 µs    │ TBs       │
// │ SATA SSD                 │ ~1 ms      │ TBs       │
// │ Network (same datacenter)│ ~500 µs    │ —         │
// │ Network (cross-region)   │ ~50–150 ms │ —         │
// └──────────────────────────┴────────────┴───────────┘

// Java implications:
// - HashMap<Integer,Integer>: each get() potentially misses L1/L2 (pointer chasing)
// - int[]: cache-line prefetch means sequential access stays in L1
// - Redis cache hit: ~500µs (network) — 5000x slower than L1 cache
// - DB query without cache: ~5ms — 50,000x slower than L1

// Checking JVM memory (RAM level in hierarchy)
Runtime rt = Runtime.getRuntime();
System.out.printf("JVM Heap: %d MB used / %d MB max%n",
    (rt.totalMemory() - rt.freeMemory()) / 1_048_576,
    rt.maxMemory() / 1_048_576);

Key Points to Remember

1Memory hierarchy: registers < L1 < L2 < L3 < RAM < SSD < HDD < network — speed decreases, size increases.
2Temporal locality: recently accessed data will likely be accessed again — exploited by caches.
3Spatial locality: nearby memory is likely accessed together — CPU fetches 64-byte cache lines.
4Array traversal is cache-friendly (sequential); linked list traversal causes cache misses (pointer chasing).
5Row-major access of 2D arrays in Java is faster than column-major due to spatial locality.
6L1 cache is ~100x faster than RAM; RAM is ~1000x faster than SSD — design data structures accordingly.

Interview Questions

Why is traversing an ArrayList faster than traversing a LinkedList for the same data?

EasyGoogle

What are temporal and spatial locality, and how do CPU caches exploit them?

MediumAmazon

Why is row-major matrix access faster than column-major in Java?

MediumNetflix

A colleague suggests using HashMap<Integer, Integer> in a hot inner loop. What performance concern would you raise?

HardUber

Ask Aria about Memory Hierarchy

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Preemptive vs Non-Preemptive Scheduling

Virtual Memory & Address Space