CPU Caches and Locality

A CPU core runs far faster than main memory can deliver data, so small, fast caches sit between them. This lesson explains the cache hierarchy and shows, with a small cache simulator, which access patterns hit and which miss, so a reader can predict the cache behavior of a loop and restructure data for it.

Idea	Meaning
Cache line	The unit of transfer between memory and caches: 64 bytes on x86
Spatial locality	Using data that sits next to data used just before
Temporal locality	Using the same data again soon
Prefetching	Hardware loading lines before the program asks for them
TLB	A cache of virtual-to-physical page translations

The examples print checksums and miss counts from a deterministic simulator; measured timings appear only in the text.

The memory hierarchy

A core is one independent instruction-executing unit of a CPU; a 4-core CPU runs 4 threads at the same instant. Each core has registers, a few dozen named storage slots that instructions operate on directly. Every value a computation uses is loaded from memory into a register first.

Between registers and main memory (DRAM) sit the caches:

Level	Typical size	Shared by	Typical latency (order of magnitude)
Register	bytes	one core	under 1 ns
L1 data cache	32 to 48 KiB	one core	about 1 ns (4 to 5 cycles)
L2 cache	256 KiB to 2 MiB	one core	about 4 ns
L3 cache	several to hundreds of MiB	all cores on a socket	10 to 40 ns
Main memory	GiB	all cores	60 to 120 ns

These are typical orders of magnitude for current x86 server CPUs; lscpu on Linux prints the sizes for the current machine. A load that misses every cache costs roughly 100 times an L1 hit, time in which a core can execute several hundred instructions.

Caches move fixed-size blocks called cache lines: 64 bytes on x86 and most ARM server CPUs (Apple M-series cores use 128 bytes). Loading one int brings in the 15 around it.

Example 1: which cache line an index falls in

A line is identified by address / 64. For an int[] that starts at a line boundary, 16 elements share each line. This program counts the distinct lines touched by two loops that read the same number of elements.

Java

import java.util.HashSet;
import java.util.Set;

public class LineMath {
    static final int LINE = 64;

    static int linesTouched(int count, int stride) {
        Set<Long> lines = new HashSet<>();
        for (int i = 0; i < count; i++) {
            long address = (long) i * stride * Integer.BYTES;
            lines.add(address / LINE);
        }
        return lines.size();
    }

    public static void main(String[] args) {
        System.out.println("ints per line = " + LINE / Integer.BYTES);
        System.out.println("1024 reads, stride 1:  lines = " + linesTouched(1024, 1));
        System.out.println("1024 reads, stride 16: lines = " + linesTouched(1024, 16));
        System.out.println("1024 reads, stride 64: lines = " + linesTouched(1024, 64));
    }
}

Output

ints per line = 16
1024 reads, stride 1:  lines = 64
1024 reads, stride 16: lines = 1024
1024 reads, stride 64: lines = 1024

Stride 1 uses every byte of each line: 1024 reads cost 64 line transfers. With stride 16 every read lands on a new line, 16 times the traffic. This is spatial locality: data used together should sit together.

Example 2: a cache simulator, sequential versus strided

The remaining examples use a small model of an L1 data cache: 32 KiB, 8-way set associative, 64-byte lines, least-recently-used (LRU) replacement. Set associative means a line can live in only one group of slots (a set, chosen by the line number) and, inside that set, in any of 8 slots (ways). LRU means a full set evicts the line used longest ago. The model shows the direction of an effect, not its exact size.

Java

import java.util.Arrays;

public class StrideSim {
    static final class Cache {
        final int sets, ways;
        final long[][] tags, lastUse;
        long tick, hits, misses;

        Cache(int sizeBytes, int ways) {
            this.ways = ways;
            this.sets = sizeBytes / 64 / ways;
            tags = new long[sets][ways];
            lastUse = new long[sets][ways];
            for (long[] t : tags) Arrays.fill(t, -1);
        }

        void access(long address) {
            long line = address >>> 6;              // 64-byte lines
            int set = (int) (line % sets);
            long[] t = tags[set], use = lastUse[set];
            tick++;
            int victim = 0;
            for (int w = 0; w < ways; w++) {
                if (t[w] == line) { hits++; use[w] = tick; return; }
                if (use[w] < use[victim]) victim = w;
            }
            misses++;
            t[victim] = line;
            use[victim] = tick;
        }
    }

    public static void main(String[] args) {
        int n = 1 << 20;                            // 1M ints = 4 MiB
        int[] data = new int[n];
        for (int i = 0; i < n; i++) data[i] = i % 7;

        for (int stride : new int[] {1, 4, 16}) {
            Cache l1 = new Cache(32 * 1024, 8);
            long sum = 0;
            for (int start = 0; start < stride; start++) {
                for (int i = start; i < n; i += stride) {
                    sum += data[i];
                    l1.access((long) i * Integer.BYTES);
                }
            }
            System.out.printf("stride %2d: sum=%d reads=%d misses=%d%n",
                stride, sum, l1.hits + l1.misses, l1.misses);
        }
    }
}

Output

stride  1: sum=3145722 reads=1048576 misses=65536
stride  4: sum=3145722 reads=1048576 misses=262144
stride 16: sum=3145722 reads=1048576 misses=1048576

All three loops read every element once. Stride 1 misses once per line (65,536 lines in 4 MiB). Stride 16 makes 16 passes, and by the time a pass returns to a line, 4 MiB of other lines have evicted it, so every read misses.

Example 3: temporal locality and the working set

The working set is the data a loop touches repeatedly. If it fits in a cache, every pass after the first hits. If it is larger, LRU evicts each line before it is used again.

Java

import java.util.Arrays;

public class WorkingSet {
    static final class Cache {
        final int sets, ways;
        final long[][] tags, lastUse;
        long tick, hits, misses;
        Cache(int sizeBytes, int ways) {
            this.ways = ways; this.sets = sizeBytes / 64 / ways;
            tags = new long[sets][ways]; lastUse = new long[sets][ways];
            for (long[] t : tags) Arrays.fill(t, -1);
        }
        void access(long address) {
            long line = address >>> 6; int set = (int) (line % sets);
            long[] t = tags[set], use = lastUse[set]; tick++; int victim = 0;
            for (int w = 0; w < ways; w++) {
                if (t[w] == line) { hits++; use[w] = tick; return; }
                if (use[w] < use[victim]) victim = w;
            }
            misses++; t[victim] = line; use[victim] = tick;
        }
    }

    public static void main(String[] args) {
        for (int kib : new int[] {16, 32, 64}) {
            int n = kib * 1024 / Integer.BYTES;
            Cache l1 = new Cache(32 * 1024, 8);
            for (int pass = 0; pass < 10; pass++) {
                for (int i = 0; i < n; i++) l1.access((long) i * Integer.BYTES);
            }
            System.out.printf("%2d KiB x 10 passes: misses=%d hit rate=%d%%%n",
                kib, l1.misses, 100 * l1.hits / (l1.hits + l1.misses));
        }
    }
}

Output

16 KiB x 10 passes: misses=256 hit rate=99%
32 KiB x 10 passes: misses=512 hit rate=99%
64 KiB x 10 passes: misses=10240 hit rate=93%

16 KiB and 32 KiB fit, so only the first pass misses. At 64 KiB each line is evicted before the next pass reaches it, and the hit rate falls to the spatial-locality share (15 of 16 reads per line). The same cliff exists at the L2 and L3 sizes, so many algorithms slow down in steps as input grows.

Example 4: row versus column traversal

Java has no true two-dimensional array: int[][] is an array of references to row arrays. Each row is contiguous, so walking along a row is sequential, and walking down a column jumps to a different row array on every read. The model places the rows back to back, as in a freshly allocated matrix.

Java

import java.util.Arrays;

public class RowVsColumn {
    static final class Cache {
        final int sets, ways;
        final long[][] tags, lastUse;
        long tick, hits, misses;
        Cache(int sizeBytes, int ways) {
            this.ways = ways; this.sets = sizeBytes / 64 / ways;
            tags = new long[sets][ways]; lastUse = new long[sets][ways];
            for (long[] t : tags) Arrays.fill(t, -1);
        }
        void access(long address) {
            long line = address >>> 6; int set = (int) (line % sets);
            long[] t = tags[set], use = lastUse[set]; tick++; int victim = 0;
            for (int w = 0; w < ways; w++) {
                if (t[w] == line) { hits++; use[w] = tick; return; }
                if (use[w] < use[victim]) victim = w;
            }
            misses++; t[victim] = line; use[victim] = tick;
        }
    }

    public static void main(String[] args) {
        int n = 1024;
        int[][] m = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) m[i][j] = (i * 31 + j) % 100;

        Cache rowCache = new Cache(32 * 1024, 8);
        long rowSum = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                rowSum += m[i][j];
                rowCache.access(((long) i * n + j) * Integer.BYTES);
            }

        Cache colCache = new Cache(32 * 1024, 8);
        long colSum = 0;
        for (int j = 0; j < n; j++)
            for (int i = 0; i < n; i++) {
                colSum += m[i][j];
                colCache.access(((long) i * n + j) * Integer.BYTES);
            }

        System.out.println("same sum: " + (rowSum == colSum) + " (" + rowSum + ")");
        System.out.println("row-major misses:    " + rowCache.misses);
        System.out.println("column-major misses: " + colCache.misses);
    }
}

Output

same sum: true (51903468)
row-major misses:    65536
column-major misses: 1048576

Row-major misses once per 16 reads. Column-major misses on every read: one column touches 1,024 lines that map to a few sets (rows are 4 KiB apart), so they are evicted before the next column reuses them. On the 4-core Xeon used to write this lesson, summing a 4096 x 4096 int[][] took about 25 ms row by row and about 280 ms column by column, a factor of about 10 for identical arithmetic.

Example 5: array of objects versus parallel arrays

An array of objects (Trade[]) holds references; each Trade is a separate heap object with a header and all its fields. A loop that needs one field still loads the whole object's lines. Parallel arrays (also called structure of arrays) keep each field in its own primitive array, so a loop over one field reads only that field's bytes, contiguously. The model assumes 32 bytes per Trade object laid out back to back; real object sizes are covered in Object Layout and Allocation.

Java

import java.util.Arrays;

public class ParallelArrays {
    static final class Cache {
        final int sets, ways;
        final long[][] tags, lastUse;
        long tick, hits, misses;
        Cache(int sizeBytes, int ways) {
            this.ways = ways; this.sets = sizeBytes / 64 / ways;
            tags = new long[sets][ways]; lastUse = new long[sets][ways];
            for (long[] t : tags) Arrays.fill(t, -1);
        }
        void access(long address) {
            long line = address >>> 6; int set = (int) (line % sets);
            long[] t = tags[set], use = lastUse[set]; tick++; int victim = 0;
            for (int w = 0; w < ways; w++) {
                if (t[w] == line) { hits++; use[w] = tick; return; }
                if (use[w] < use[victim]) victim = w;
            }
            misses++; t[victim] = line; use[victim] = tick;
        }
    }

    record Trade(long id, long priceTicks, int qty, int venue) {}

    public static void main(String[] args) {
        int n = 100_000;
        Trade[] trades = new Trade[n];
        long[] ids = new long[n], prices = new long[n];
        int[] qtys = new int[n], venues = new int[n];
        for (int i = 0; i < n; i++) {
            trades[i] = new Trade(i, 10_000 + i % 50, 1 + i % 10, i % 4);
            ids[i] = i; prices[i] = 10_000 + i % 50; qtys[i] = 1 + i % 10; venues[i] = i % 4;
        }

        Cache aos = new Cache(32 * 1024, 8);
        long qtyA = 0;
        for (int i = 0; i < n; i++) {
            qtyA += trades[i].qty();
            aos.access((long) i * 32 + 24);         // qty inside a 32-byte object
        }

        Cache soa = new Cache(32 * 1024, 8);
        long qtyB = 0;
        for (int i = 0; i < n; i++) {
            qtyB += qtys[i];
            soa.access((long) i * Integer.BYTES);
        }

        System.out.println("total qty equal: " + (qtyA == qtyB) + " (" + qtyA + ")");
        System.out.println("objects misses:         " + aos.misses);
        System.out.println("parallel arrays misses: " + soa.misses);
    }
}

Output

total qty equal: true (550000)
objects misses:         50000
parallel arrays misses: 6250

Two trades fit in a line and sixteen quantities do, so the parallel array misses 8 times less. Real Trade[] loops are worse: the reference array is a second stream, and objects allocated at different times may be scattered. Parallel arrays cost readability and type safety, so they are used for hot loops over many elements (order books, time series, columnar analytics).

Example 6: pointer chasing and prefetching

Hardware prefetching is circuitry in the core that watches the stream of missed addresses, detects a sequential or constant-stride pattern, and requests the next lines before the program asks for them. It cannot help pointer chasing: walking a linked structure where the next address is known only after the current node is loaded. Each miss then costs full memory latency, one after another.

The program builds the same linked list twice inside one array of slots: once with nodes in list order, once with nodes in shuffled slots (as after many inserts and removals). Each slot is 32 bytes in the model.

Java

import java.util.Arrays;
import java.util.Random;

public class PointerChasing {
    static final class Cache {
        final int sets, ways;
        final long[][] tags, lastUse;
        long tick, hits, misses;
        Cache(int sizeBytes, int ways) {
            this.ways = ways; this.sets = sizeBytes / 64 / ways;
            tags = new long[sets][ways]; lastUse = new long[sets][ways];
            for (long[] t : tags) Arrays.fill(t, -1);
        }
        void access(long address) {
            long line = address >>> 6; int set = (int) (line % sets);
            long[] t = tags[set], use = lastUse[set]; tick++; int victim = 0;
            for (int w = 0; w < ways; w++) {
                if (t[w] == line) { hits++; use[w] = tick; return; }
                if (use[w] < use[victim]) victim = w;
            }
            misses++; t[victim] = line; use[victim] = tick;
        }
    }

    // next[slot] is the slot of the following node, -1 at the end
    static void walk(String label, int head, int[] next, int[] value) {
        Cache l1 = new Cache(32 * 1024, 8);
        long sum = 0;
        int hops = 0;
        for (int slot = head; slot != -1; slot = next[slot]) {
            l1.access((long) slot * 32);
            sum += value[slot];
            hops++;
        }
        System.out.printf("%-9s hops=%d sum=%d misses=%d%n", label, hops, sum, l1.misses);
    }

    public static void main(String[] args) {
        int n = 200_000;
        int[] order = new int[n];                  // order[k] = slot of k-th node
        for (int k = 0; k < n; k++) order[k] = k;
        build("in order", order);

        Random rnd = new Random(7);
        for (int k = n - 1; k > 0; k--) {          // Fisher-Yates shuffle
            int j = rnd.nextInt(k + 1);
            int tmp = order[k]; order[k] = order[j]; order[j] = tmp;
        }
        build("shuffled", order);
    }

    static void build(String label, int[] order) {
        int n = order.length;
        int[] next = new int[n], value = new int[n];
        for (int k = 0; k < n; k++) {
            value[order[k]] = k % 10;
            next[order[k]] = k + 1 < n ? order[k + 1] : -1;
        }
        walk(label, order[0], next, value);
    }
}

Output

in order  hops=200000 sum=900000 misses=100000
shuffled  hops=200000 sum=900000 misses=199479

Both walks compute the same sum. In order, two nodes share a line and the pattern is sequential, which a prefetcher also follows. Shuffled, almost every hop misses, and each miss waits for the previous load. This is why ArrayList iterates several times faster than LinkedList over the same elements, and why tree and hash structures with many small nodes are slower than their operation counts suggest.

Example 7: the TLB and pages

Programs use virtual addresses. The OS maps them to physical memory in pages, 4 KiB by default on x86 Linux. Translating an address requires a walk of the page tables, so the core caches recent translations in the translation lookaside buffer (TLB), which holds on the order of 64 entries at L1 and one to two thousand at L2. A loop that touches more pages than the TLB covers pays a page-table walk on top of any cache miss. The model below counts TLB misses with a 64-entry LRU TLB for the two traversals of Example 4.

Java

import java.util.LinkedHashMap;
import java.util.Map;

public class TlbModel {
    static final class Tlb {
        final int capacity;
        long misses;
        final Map<Long, Boolean> entries;
        Tlb(int capacity) {
            this.capacity = capacity;
            this.entries = new LinkedHashMap<>(16, 0.75f, true) {   // access order = LRU
                @Override protected boolean removeEldestEntry(Map.Entry<Long, Boolean> e) {
                    return size() > Tlb.this.capacity;
                }
            };
        }
        void access(long address) {
            long page = address >>> 12;                              // 4 KiB pages
            if (entries.get(page) == null) { misses++; entries.put(page, true); }
        }
    }

    public static void main(String[] args) {
        int n = 1024;                                // 1024 x 1024 ints, one row = 4 KiB
        Tlb rows = new Tlb(64), cols = new Tlb(64);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) rows.access(((long) i * n + j) * 4);
        for (int j = 0; j < n; j++)
            for (int i = 0; i < n; i++) cols.access(((long) i * n + j) * 4);
        System.out.println("pages in matrix:     " + (long) n * n * 4 / 4096);
        System.out.println("row-major TLB misses:    " + rows.misses);
        System.out.println("column-major TLB misses: " + cols.misses);
    }
}

Output

pages in matrix:     1024
row-major TLB misses:    1024
column-major TLB misses: 1048576

Column order touches 1,024 pages per column, far more than 64 entries, so every access misses the TLB. Large pages (2 MiB on x86) cover 512 times more memory per entry; the JVM can use them with -XX:+UseLargePages or -XX:+UseTransparentHugePages, covered in Virtual Memory, Page Faults, and perf.

Example 8: blocked matrix transpose

A transpose reads a by rows and writes b by columns, so one of the two is always column order. Blocking (tiling) processes the matrix in small square tiles that fit in the cache: inside a tile, both the rows read and the columns written stay cached until the tile is done.

Java

import java.util.Arrays;

public class BlockedTranspose {
    static final class Cache {
        final int sets, ways;
        final long[][] tags, lastUse;
        long tick, hits, misses;
        Cache(int sizeBytes, int ways) {
            this.ways = ways; this.sets = sizeBytes / 64 / ways;
            tags = new long[sets][ways]; lastUse = new long[sets][ways];
            for (long[] t : tags) Arrays.fill(t, -1);
        }
        void access(long address) {
            long line = address >>> 6; int set = (int) (line % sets);
            long[] t = tags[set], use = lastUse[set]; tick++; int victim = 0;
            for (int w = 0; w < ways; w++) {
                if (t[w] == line) { hits++; use[w] = tick; return; }
                if (use[w] < use[victim]) victim = w;
            }
            misses++; t[victim] = line; use[victim] = tick;
        }
    }

    static final int N = 512;
    static final long B_BASE = (long) N * N * 4 + 4096 + 64 * 7;   // b after a, offset to avoid set aliasing

    static long checksum(int[] m) {
        long h = 0;
        for (int i = 0; i < m.length; i++) h = h * 31 + m[i];
        return h;
    }

    static long naive(int[] a, int[] b) {
        Cache c = new Cache(32 * 1024, 8);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                b[j * N + i] = a[i * N + j];
                c.access((long) (i * N + j) * 4);
                c.access(B_BASE + (long) (j * N + i) * 4);
            }
        return c.misses;
    }

    static long blocked(int[] a, int[] b, int tile) {
        Cache c = new Cache(32 * 1024, 8);
        for (int ii = 0; ii < N; ii += tile)
            for (int jj = 0; jj < N; jj += tile)
                for (int i = ii; i < ii + tile; i++)
                    for (int j = jj; j < jj + tile; j++) {
                        b[j * N + i] = a[i * N + j];
                        c.access((long) (i * N + j) * 4);
                        c.access(B_BASE + (long) (j * N + i) * 4);
                    }
        return c.misses;
    }

    public static void main(String[] args) {
        int[] a = new int[N * N];
        for (int i = 0; i < a.length; i++) a[i] = i % 1000;
        int[] b1 = new int[N * N], b2 = new int[N * N];

        long naiveMisses = naive(a, b1);
        long blockedMisses = blocked(a, b2, 16);
        System.out.println("results equal: " + Arrays.equals(b1, b2));
        System.out.println("checksum: " + checksum(b1));
        System.out.println("naive misses:   " + naiveMisses);
        System.out.println("blocked misses: " + blockedMisses);
    }
}

Output

results equal: true
checksum: -8369889056822943936
naive misses:   278528
blocked misses: 40217

A 16 x 16 int tile spans 16 lines in each matrix, 32 in total, which fits in L1. Matrix multiplication libraries use the same technique; tile size depends on the cache size, so production code tunes it per machine or blocks recursively for every level.

Interview points

A cache line is 64 bytes on x86; caches load and evict whole lines, so the unit of memory cost is the line, not the field.
L1 hit is about 1 ns, main memory about 100 ns; the ratio, not the exact number, drives design.
Spatial locality: use neighboring bytes. Temporal locality: reuse data before it is evicted.
int[][] is an array of row arrays; iterate the last index in the inner loop.
Parallel arrays (structure of arrays) beat arrays of objects for loops over one or two fields of many elements.
Linked structures cause pointer chasing: dependent misses that prefetchers cannot hide.
A working set slightly larger than a cache level causes a sharp drop in hit rate.
The TLB caches page translations; large pages reduce TLB misses for big heaps.
Blocking (tiling) restructures loops so the working set fits in cache.

Summary

Registers, L1, L2, L3, and DRAM differ in latency by about two orders of magnitude end to end.
Data moves in 64-byte lines; 16 int or 8 long values share one line.
Sequential and constant-stride access are detected by hardware prefetchers.
Column traversal of a row-major matrix misses the cache and the TLB on every access in the model.
Shuffled node order makes almost every hop of a list walk a miss.
Blocked transpose produces the same result as the naive one with far fewer misses.
False sharing and coherence between cores are covered in Cache Coherence, False Sharing, Branch Prediction, and NUMA.