Cache Hierarchy

Learning objective

Explain why the same amount of work can run orders of magnitude slower depending only on memory access pattern, by relating it to the L1/L2/L3/RAM hierarchy, cache lines, spatial and temporal locality, and hardware prefetching — then be able to predict, for a given working-set size and access pattern, roughly which level of the hierarchy will serve most accesses.

Prerequisites

• Comfortable reading Java or Rust code that allocates and iterates arrays.
• No prior knowledge of cache hardware is assumed — this lab builds the hierarchy from scratch. (If you've done the False sharing lab, the cache-line concept here is the same one used there.)

Theory

The hierarchy

A modern CPU core does not read main memory (RAM) directly on every access — RAM latency, on the order of a hundred nanoseconds or more, would leave the core idle for hundreds of cycles per load. Instead, each core sits behind a hierarchy of progressively larger, progressively slower caches:

When a core requests an address, the hierarchy is checked from L1 outward: a hit at any level returns the data at that level's latency; a miss falls through to the next level, all the way to RAM if nothing above holds it. Because each lower level is also larger, a miss at L1 is often still a hit one or two levels down — the expensive case is a miss all the way to RAM.

Cache lines

Every level moves data in fixed-size blocks called cache lines — commonly 64 bytes on current x86-64 and ARM64 parts (see the False sharing lab for why this is a common example, not a universal constant). Requesting one byte pulls in the whole 64-byte line containing it. This is the physical basis for locality: touching one element of an array effectively pre-loads its neighbours for free, if you go on to use them before the line is evicted.

Spatial and temporal locality

Two independent properties of an access pattern determine how well it uses the hierarchy:

• Spatial locality — how close together in memory the addresses you touch are. Iterating an array index-by-index has excellent spatial locality: each 64-byte line serves roughly 8 consecutive longs (or 16 ints) before the next line is needed. Chasing pointers scattered across a large heap has poor spatial locality: each access may need a fresh line that shares nothing with the line before it.
• Temporal locality — how soon you return to an address you already touched. A loop that repeatedly scans a working set small enough to stay resident in a cache level has excellent temporal locality: after the first pass warms the cache, every later pass hits it. A single sweep over a multi-gigabyte array that's never revisited has poor temporal locality — by the time you might return to an early element, it has long since been evicted to make room for everything touched since.

Both matter independently. An access pattern can have good spatial locality but poor temporal locality (one long sequential sweep over data far larger than any cache level), or the reverse (repeatedly re-reading a single scattered set of pointers small enough to fit in L1, where each individual pass has poor spatial locality but the working set as a whole stays warm).

Hardware prefetching

Beyond passively caching what was touched, most cores also speculatively fetch data they predict will be touched soon. The simplest and most common form is a stride/stream prefetcher: when the memory controller observes a core reading address A, then A + stride, then A + 2·stride, it starts issuing fetches for A + 3·stride, A + 4·stride, … before the core asks for them, hiding RAM latency behind the compute already in flight.

This is why sequential access is not simply "as fast as the cache line happens to be big" — a genuinely large, sequentially-swept array can still run close to cache-level latency in steady state, because the prefetcher keeps arriving before the core does. Random access defeats this mechanism entirely: with no detectable stride, the prefetcher has nothing to predict, and — once the working set exceeds what fits in cache — every access pays close to full RAM latency, even though the same number of bytes is being read as the sequential case. The interactive model below demonstrates this directly: sequential access to a working set that exceeds every cache level still lands mostly in L2 thanks to a simulated prefetcher; random access over the same size lands in RAM almost every time.

Working-set size vs. access pattern: four regimes

Combining "does the working set fit in a given cache level" with "is the access pattern sequential or random" gives four regimes — exactly what the interactive model's four scenarios below let you step through:

1. Sequential, fits in L1 — cheapest possible case. First pass warms the line; every later access, forward or looped, is an L1 hit.
2. Random, fits in L1 — same eventual steady state as (1) once the whole working set has been touched once, because residency, not order, is what determines an L1 hit for a small enough set — but it gets there without the head start hardware prefetching gives sequential access.
3. Sequential, exceeds every cache level — the working set can never fully reside in cache, so pure demand-fetch would miss to RAM on every access. Hardware prefetching narrows that gap substantially: most accesses land in L2 because the prefetcher stays ahead of the stream.
4. Random, exceeds every cache level — the worst case, and the one real systems most need to avoid for hot paths: no predictable stride means no prefetching benefit, and a working set larger than any cache level means almost no reuse either. Close to every access pays RAM latency.

Java and Rust

public final class ChaseTables {
    private ChaseTables() {}

    // A sequential cycle: 0 -> 1 -> 2 -> ... -> size-1 -> 0. Maximal spatial locality.
    public static long[] sequentialCycle(int size) {
        long[] next = new long[size];
        for (int i = 0; i < size; i++) next[i] = (i + 1) % size;
        return next;
    }

    // A random single-cycle permutation built with Sattolo's algorithm.
    // Plain Fisher-Yates would risk producing several short sub-cycles,
    // which would let a pointer chase loop through only a small hot
    // subset of the array — Sattolo's algorithm guarantees exactly one
    // cycle covering all `size` elements.
    public static long[] randomCycle(int size, long seed) {
        int[] perm = new int[size];
        for (int i = 0; i < size; i++) perm[i] = i;
        Random rnd = new Random(seed);
        for (int i = size - 1; i > 0; i--) {
            // nextInt(i), not nextInt(i + 1) as in Fisher-Yates — excluding
            // self-swaps is what makes this a single cycle instead of a
            // random permutation (usually several disjoint cycles).
            int j = rnd.nextInt(i);
            int tmp = perm[i]; perm[i] = perm[j]; perm[j] = tmp;
        }
        long[] next = new long[size];
        for (int i = 0; i < size; i++) next[perm[i]] = perm[(i + 1) % size];
        return next;
    }
}

@State(Scope.Thread)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Fork(1)
@Warmup(iterations = 5, time = 1)
@Measurement(iterations = 10, time = 1)
public class CacheHierarchyBenchmark {

    // 16 KB of longs — comfortably fits inside L1D on any current desktop/laptop core.
    private static final int SMALL_SIZE = 2_048;
    // 128 MB of longs — exceeds any consumer last-level cache.
    private static final int LARGE_SIZE = 16_777_216;
    private static final int CHASES = 1_000_000;

    private long[] sequentialSmallTable, randomSmallTable, sequentialLargeTable, randomLargeTable;

    @Setup(Level.Trial)
    public void setup() {
        sequentialSmallTable = ChaseTables.sequentialCycle(SMALL_SIZE);
        randomSmallTable = ChaseTables.randomCycle(SMALL_SIZE, 1);
        sequentialLargeTable = ChaseTables.sequentialCycle(LARGE_SIZE);
        randomLargeTable = ChaseTables.randomCycle(LARGE_SIZE, 2);
    }

    private static long chase(long[] next, int steps) {
        long idx = 0;
        for (int i = 0; i < steps; i++) idx = next[(int) idx];
        return idx; // returned, not discarded, so the JIT cannot eliminate the loop as dead code.
    }

    @Benchmark public long sequentialSmall() { return chase(sequentialSmallTable, CHASES); }
    @Benchmark public long randomSmall() { return chase(randomSmallTable, CHASES); }
    @Benchmark public long sequentialLarge() { return chase(sequentialLargeTable, CHASES); }
    @Benchmark public long randomLarge() { return chase(randomLargeTable, CHASES); }
}

/// A sequential cycle: 0 -> 1 -> 2 -> ... -> size-1 -> 0. Maximal spatial locality.
pub fn sequential_cycle(size: usize) -> Vec<u64> {
    (0..size).map(|i| ((i + 1) % size) as u64).collect()
}

/// A random single-cycle permutation built with Sattolo's algorithm — see
/// java.md for why this guarantees a single cycle, unlike Fisher-Yates.
pub fn random_cycle(size: usize, seed: u64) -> Vec<u64> {
    let mut perm: Vec<usize> = (0..size).collect();
    let mut state = seed.max(1); // xorshift64 needs a non-zero seed
    let mut next_rand = |bound: usize| -> usize {
        state ^= state << 13;
        state ^= state >> 7;
        state ^= state << 17;
        (state % bound as u64) as usize
    };
    for i in (1..size).rev() {
        let j = next_rand(i); // exclusive of i, not i + 1 — see java.md
        perm.swap(i, j);
    }
    let mut next = vec![0u64; size];
    for i in 0..size {
        next[perm[i]] = perm[(i + 1) % size] as u64;
    }
    next
}

use criterion::{black_box, criterion_group, criterion_main, Criterion};

const SMALL_SIZE: usize = 2_048;       // 16 KB of u64s — fits inside L1D.
const LARGE_SIZE: usize = 16_777_216;  // 128 MB of u64s — exceeds any consumer LLC.
const CHASES: usize = 1_000_000;

fn chase(next: &[u64], steps: usize) -> u64 {
    let mut idx: u64 = 0;
    for _ in 0..steps {
        idx = next[idx as usize];
    }
    idx
}

fn bench_sequential_large(c: &mut Criterion) {
    let table = sequential_cycle(LARGE_SIZE);
    c.bench_function("sequential_large", |b| b.iter(|| chase(black_box(&table), CHASES)));
}

fn bench_random_large(c: &mut Criterion) {
    let table = random_cycle(LARGE_SIZE, 2);
    c.bench_function("random_large", |b| b.iter(|| chase(black_box(&table), CHASES)));
}

criterion_group!(benches, /* ...small variants..., */ bench_sequential_large, bench_random_large);
criterion_main!(benches);

Benchmark methodology

Method: 1,000,000 dependent pointer-chase steps per benchmark, identical down to the byte in both languages — a 16,384-byte working set (fits L1) and a 134,217,728-byte / 128 MiB working set (exceeds cache), each in sequential and random cycle order built by the same Sattolo's-algorithm construction. Approximate per-access latency (ns) = batch time ÷ 1,000,000.

Sized against this machine's actual cache hierarchy, not a generic guess (Apple M1 Max, per AnandTech's teardown): the 16 KB working set fits inside even the smallest L1D on the chip (64 KiB, E-core) with room to spare; the 128 MiB working set exceeds the single largest cache level (48 MiB System Level Cache) by close to 3×, and any per-cluster L2 (12 MiB P-cluster / 4 MiB E-cluster) by an order of magnitude.

Java (JMH, mean time per 1,000,000-chase batch ± 99.9% CI, lower is better):

Rust (Criterion, bootstrap-median time per 1,000,000-chase batch, lower is better):

Small working sets land within rounding of each other regardless of order in both languages (order stops mattering once everything is cache-resident). Large-sequential is nearly as fast as small in both languages — prefetching at work. Large-random is where the two languages actually agree on the physically meaningful number: 118.54 ns/access (Java) vs. 110.98 ns/access (Rust), about 7% apart — both plausible single uncontended DRAM accesses, and this is the figure that should generalize across languages on the same hardware, because it's dominated by the memory subsystem rather than either runtime.

The naive sequential/random ratio (~48–50× in Java, ~86–87× in Rust) is not directly comparable across languages, and the reason is traceable, not mysterious: that ~1.75× gap between the two ratios tracks almost exactly the ~1.75× gap between the languages' own sequentialSmall/sequential_small floors (Java ≈ 2.2 µs, Rust ≈ 1.26 µs per batch) — a gap that has nothing to do with memory latency, since a 16 KB, L1-resident chase should cost near-identical CPU cycles regardless of language. That floor is fixed per-invocation harness overhead (JMH's blackhole consumption vs. Criterion's leaner closure call), and because sequentialLarge is also mostly prefetch-hidden, it inherits roughly that same overhead-dominated floor instead of reflecting real memory cost — which mechanically compresses Java's computed ratio relative to Rust's. Treat the ratio as "prefetching helps a lot," not as a precise, portable multiplier — the absolute random-access latency above is the trustworthy cross-language number.

Re-run the project in code/ on your own hardware before treating any of this as authoritative for a design decision — see the raw per-iteration samples (JMH -rf json; Criterion's target/criterion/**/new/sample.json and estimates.json) for more than the summary line.

Known limitations

• No CPU affinity or core-type pinning. Neither JMH nor Cargo/Criterion pins the process to a specific core, and macOS documents its thread-affinity API as advisory on Apple silicon, not a hard pin — there is no user-space taskset equivalent here. Results reflect whatever core(s) the OS scheduler actually granted.
• Concretely observed, not just a theoretical caveat: an earlier attempt at this exact run, made while an unrelated browser process briefly used >100% CPU on this machine, produced a randomSmall result of 35,257 ± 61,833 µs/op — a mean smaller than its own error bar — with per-iteration samples swinging from 2,267 µs to 93,274 µs within one ten-iteration window. That run was discarded; the numbers above are from a subsequent run taken once load had settled. Latency-bound (random-access) benchmarks are far more exposed to this than throughput-bound (sequential/prefetched) ones, because a prefetched stream has slack to absorb a brief stall where a dependent random chase does not.
• Bounds checks are retained, in both languages, and that's correct. idx is data-dependent (read from the array itself), not a loop-invariant range either HotSpot's range-check elimination or LLVM's bounds-check elision can statically prove safe, so the check on every access is not eliminated in either language. Disassembling the Rust chase function (rustc -O --emit=asm) confirms it directly as a cmp/branch pair before the load. This cost applies identically to every benchmark here, so it doesn't bias the sequential-vs-random comparison.
• Criterion's stable-Rust black_box is a strong convention, not a compiler guarantee — its own doc comment admits the fallback (a volatile read + forget, since this project doesn't enable the nightly-only real_blackbox feature) "may... fail to prevent code from being eliminated." The disassembly evidence above, not the comment, is what this lab relies on. JMH's auto-detected compiler blackhole is a more mature, purpose-built mechanism by comparison.
• Benchmarks were run sequentially, one language at a time, specifically to avoid the two processes contending for shared L2/SLC bandwidth — an earlier attempt at running both concurrently was caught and abandoned before any numbers from it were used.

Common mistakes

• Treating "it's in the cache" as binary — a cache hierarchy has several levels with very different latencies; "cached" without naming a level is not precise enough to reason about performance.
• Assuming sequential access is fast because of cache-line reuse alone — for a working set that exceeds cache capacity, hardware prefetching is usually doing most of the work, not just fewer fetched lines.
• Assuming random access is just "cache-line reuse minus locality" — it also loses hardware prefetching entirely, which is often the larger effect once the working set exceeds cache.
• Hardcoding a cache-line size or cache size as an architectural constant — these are facts of the machine you measured on, not guarantees.
• Benchmarking access patterns without defeating the optimizer — a compiler or JIT can hoist, vectorize, or reorder a plain array loop in ways that no longer reflect the memory-access pattern you intended to measure; the benchmarks above use pointer chasing specifically to prevent that.

Investigation task

Using the Java or Rust project in code/, and a profiler or hardware counter tool available to you:

1. Run all four benchmarks (sequentialSmall, randomSmall, sequentialLarge, randomLarge in Java; the equivalent Criterion functions in Rust) and record the reported time per batch for each.
2. Compute an approximate nanoseconds-per-access figure for each by dividing the reported batch time by the number of chases per batch (1,000,000 — see "Benchmark methodology" above).
3. If you have perf (Linux) or Instruments (macOS) available, look for a last-level-cache-miss or memory-stall counter and compare it between the *Small and *Large variants — confirm the miss rate rises sharply only for the *Large benchmarks.
4. Change LARGE_SIZE to a value that fits inside your machine's actual LLC size (check it first) and re-run sequentialLarge/randomLarge — confirm the sequential/random gap narrows once the working set fits in cache, matching the "fits" vs. "exceeds" scenarios in the interactive model above.
5. Run each benchmark twice — once with the machine otherwise idle, once with a CPU-heavy background task running (a video call, a build, a browser tab doing heavy work) — and compare the reported error bars. Expect the random* benchmarks to show much more run-to-run variance under load than the sequential* ones; "Known limitations" under Benchmark methodology above has a concrete example of this from this lab's own reruns.
6. Write down your CPU model, cache sizes (per level, if you can find them), and your measured numbers, and explain any difference from the disclosed numbers above.

Accessibility notes

• The interactive model is fully keyboard operable: the scenario selector and the Java/Rust code tabs are roving-tabindex tablists (arrow keys, Home/End); every step/reset control is a native <button>.
• Every step is announced to screen readers via an aria-live="polite" region, in addition to the visible result badge and the state inspector table — the working-set grid's colour coding is a supplementary visual aid, never the only carrier of the result.
• The working-set grid has no animation; step transitions resolve instantly, so there is nothing to gate on prefers-reduced-motion beyond the site-wide CSS rule.
• With JavaScript disabled, this page's theory, Java and Rust code, benchmark methodology, trade-offs and sources remain fully readable — only the interactive model and the graded quiz require script.

Review questions

Self-check before or after the graded quiz below:

1. Why can a 128 MB sequential sweep run nearly as fast as a 16 KB one, when neither working set fits in any single cache level except the small one?
2. What specifically does random access lose that sequential access has, once the working set exceeds cache capacity?
3. Give an example of an access pattern with good spatial locality but poor temporal locality, and one with the reverse.
4. Why does the benchmark code use a dependent pointer chase instead of a plain for (i = 0; i < n; i++) sum += array[i] loop?

Sources

• What Every Programmer Should Know About Memory — Ulrich Drepper, 2007. people.freebsd.org/~lstewart/articles/cpumemory.pdf
• Intel 64 and IA-32 Architectures Optimization Reference Manual, Chapter 3 (Cache and Memory Subsystem) — intel.com/sdm
• A Primer on Memory Consistency and Cache Coherence — Sorin, Hill, Wood, Morgan & Claypool, 2011.
• lmbench: Portable Tools for Performance Analysis — McVoy & Staelin, USENIX ATC 1996.
• Sattolo's Algorithm — en.wikipedia.org/wiki/Fisher–Yates_shuffle
• Criterion.rs User Guide — bheisler.github.io/criterion.rs
• JMH: Java Microbenchmark Harness — openjdk.org/projects/code-tools/jmh