CPU Caches & Locality

in reviewThis lesson is complete and being validated before release - details may still change.

Cache and locality

Loading interactive demo…

The left grid is the memory, 64 words with their addresses, the words the cache currently holds filled in. The right grid is the cache: one row per set, one cell per way, each showing the tag of the block it holds. The strip beneath is the access stream, each address marked as it hits or misses. Tap a word in the memory to see how its address splits into offset, set, and tag.Take the tour, or press and explore. Legend:

The panel beside the stage is the real CacheSimulator class from the published library executing in your browser, with the current line highlighted.

The address being looked up, and the set it maps to.
A word the cache holds right now.
A hit: the line that held the tag.
A miss: the line the block was fetched into.
A miss in the access strip.
Words not in the cache, empty lines, and accesses still to come.

accesses counts the stream so far, hits and misses split it, hit rate is their ratio, and evictions counts the misses that threw a block out rather than filling an empty line.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The problem. The tiny CPU read a memory word in one cycle. A real one cannot: memory is large, far from the core, and built from slow dense cells, so a load takes hundreds of cycles. A cache is a small memory of fast cells next to the core that keeps copies of whatever was used recently, in the hope that it will be used again.

Splitting an address. With $B$ words per block and $S$ sets, an address $a$ names the word $a \bmod B$ of block $\lfloor a / B \rfloor$ ; that block may live only in set $\lfloor a / B \rfloor \bmod S$ , and the rest of the number, $\lfloor a / (B \cdot S) \rfloor$ , is its tag. When the counts are powers of two these are bit fields: the low bits are the offset, the next the set index, the rest the tag. The cache compares the tag against every line of one set, not against the whole cache, which is what makes a lookup fast.

Hits, misses, and the three Cs. A miss on a block never seen before is compulsory: nothing could have avoided it except a bigger block, which is why blocks hold several words and a sequential walk hits on all but the first of each. A miss on a block that was here but has since been thrown out is a capacity miss if the cache was simply too small for everything touched in between, or a conflict miss if the cache had room but the block's set did not. Direct mapping makes conflicts easy: the strided pattern uses only half the sets and misses forever, where two ways would hold both blocks.

Locality. Programs hit for two reasons. Spatial locality: having touched a word, they soon touch its neighbours, so the block pays for itself. Temporal locality: having touched a word, they touch it again soon, so the line pays for itself. The matrix walks show the first: the same sixty-four words in a different order change the hit rate from three in four to none. The small loop shows the second: eight words read four times hit after the first pass. The default pattern shows the limit: sixteen words through a cache of eight miss on the second pass exactly as on the first, because by the time the walk returns, every block has been pushed out.

Replacement. A full set must choose a victim. Least recently used throws out the line untouched for longest, which is right for temporal locality and wrong for a loop one block bigger than the cache, where it evicts exactly the block about to be needed. Real caches approximate it with a few bits per set.

Cost. The average access time is $t_{\text{hit}} + m \cdot t_{\text{miss}}$ for miss rate $m$ . With a hit of 4 cycles and a miss of 200, a 95 percent hit rate gives 14 cycles, and 90 percent gives 24: every point of hit rate is worth two cycles on average, which is why the hierarchy has several levels and why programmers arrange data for it.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

decompose is three lines of integer arithmetic, division and remainder by the block size and the set count; with powers of two a processor does the same with wires, no arithmetic at all.
A set is an array of lines and a lookup is findIndex over it, so direct mapped, two-way, and fully associative are the same code with a different set count. The hardware difference is how many tag comparators run in parallel.
lastUsed is the access count, and a miss replaces the line with the smallest. That is exact least recently used; real caches keep a bit or two per set and approximate.
An empty line is filled before anything is evicted, so the first misses of a run never count as evictions; the readout separates the two.
The access pattern is data the stage supplies; the class only sees addresses, and the random pattern's seed lives in the widget.

Processors outran memory early and have never stopped. In 1965 Maurice Wilkes proposed a small fast "slave memory" that would hold the words a program had used most recently, on the observation that programs reuse the same addresses and their neighbours far more than chance would predict. IBM shipped the idea in the System/360 Model 85 in 1968 and an editor renamed it the cache. Every processor since has carried one, then two, then three levels of them, and the gap they bridge has grown from a factor of a few to a few hundred.

1965Maurice Wilkes - Slave Memories and Dynamic Storage Allocation proposes holding recently used words in a small fast memory in front of the main one.source
1968IBM - The System/360 Model 85 is the first commercial computer with a cache; the name is chosen for the IBM Systems Journal article describing it.source
1987Mark Hill - Classifies misses as compulsory, capacity, or conflict, the three Cs that still frame how a cache is sized and organised.source
1989Intel - The 80486 puts an 8 KB cache on the processor die itself, the first level of the hierarchy every chip now has.source
2006Intel - The Core 2 shares a last-level cache between two cores, the shape of today's multi-core hierarchies.source

Used today

Every processor - Three levels of cache stand between a core and memory; a level-one hit costs a few cycles, a memory access hundreds.
Writing fast code - Walking an array in memory order, keeping working sets small, and laying out structures by access are all ways of hitting the cache.
Caches everywhere - Web browsers, databases, and content delivery networks apply the same idea at larger scales with the same hit-or-miss arithmetic.

pattern

lines

block

ways

seed1

accesses: 32 of 32
hits: 16
misses: 16
hit rate: 50%
evictions: 12

cache.ts

import type { Tracer } from "../trace";export interface CacheConfig {  /** How many blocks the cache holds; a power of two. */  lines: number;  /** Words per block; a power of two. The offset picks the word inside a block. */  blockWords: number;  /** Lines per set: 1 is direct mapped, `lines` is fully associative. */  ways: number;}export interface CacheLine {  valid: boolean;  tag: number;  /** The access count when the line was last touched, for least-recently-used replacement. */  lastUsed: number;}export interface AccessResult {  address: number;  set: number;  tag: number;  offset: number;  hit: boolean;  /** The way the block sits in after the access. */  way: number;  /** The tag the miss threw out, or null when the line was empty. */  evicted: number | null;}export interface CacheReport {  accesses: number;  hits: number;  misses: number;  /** Misses that threw a valid block out, as opposed to filling an empty line. */  evictions: number;  hitRate: number;}export const MAX_CACHE_LINES = 64;export const MAX_ACCESSES = 256;const isPowerOfTwo = (n: number): boolean => Number.isInteger(n) && n > 0 && (n & (n - 1)) === 0;/** * A cache between a processor and its memory: a few lines, each * holding one block of consecutive words. An address splits into an * offset (which word of the block), a set index (which lines the block * may use), and a tag (which block of all those that map to the set * is actually there). A lookup compares the tag against every line of * the set: a match is a hit, anything else a miss that fetches the * block and, when the set is full, throws out the line used longest * ago. Programs that touch nearby words soon after one another hit * because of the block; programs that return to the same words hit * because of the lines; everything else misses. * * Time: O(ways) per access. Space: O(lines). */export class CacheSimulator {  private readonly sets: CacheLine[][];  private readonly setCount: number;  private time = 0;  private hits = 0;  private misses = 0;  private evictions = 0;  constructor(    readonly config: CacheConfig,    private readonly tracer?: Tracer,  ) {    const { lines, blockWords, ways } = config;    if (!isPowerOfTwo(lines) || lines > MAX_CACHE_LINES) throw new RangeError(`lines must be a power of two up to ${MAX_CACHE_LINES}`);    if (!isPowerOfTwo(blockWords)) throw new RangeError("blockWords must be a power of two");    if (!Number.isInteger(ways) || ways < 1 || lines % ways !== 0) throw new RangeError("ways must divide the line count");    this.setCount = lines / ways;    this.sets = Array.from({ length: this.setCount }, () => Array.from({ length: ways }, () => ({ valid: false, tag: 0, lastUsed: 0 })));  }  /** The lines of a set, as they stand. */  set(index: number): readonly CacheLine[] {    const lines = this.sets[index];    if (!lines) throw new RangeError(`no set ${index}`);    return lines.map((line) => ({ ...line }));  }  /** How an address splits for this cache. */  decompose(address: number): { offset: number; set: number; tag: number } {    const block = Math.floor(address / this.config.blockWords);    return { offset: address % this.config.blockWords, set: block % this.setCount, tag: Math.floor(block / this.setCount) };  }  /** One memory access by address: a hit, or a miss that fills a line. */  access(address: number): AccessResult {    if (!Number.isInteger(address) || address < 0) throw new RangeError(`address ${address} is not a word address`);    this.time++;    const { offset, set, tag } = this.decompose(address);    const lines = this.sets[set]!;    // ▸ split the address: the offset picks the word in a block, the set picks the lines, the tag names the block    this.tracer?.emit("lookup", { address, set, tag, offset, time: this.time, tags: lines.map((line) => (line.valid ? line.tag : null)) });    const found = lines.findIndex((line) => line.valid && line.tag === tag);    const matchingWay = lines.findIndex((line) => line.valid && line.tag === tag);    if (found !== -1) {    if (matchingWay !== -1) {      lines[found]!.lastUsed = this.time;      lines[matchingWay]!.lastUsed = this.time;      this.hits++;      // ▸ a line of the set holds the tag: the word is here, and the line is marked as just used      this.tracer?.emit("hit", { address, set, way: found, tag, hits: this.hits, misses: this.misses });      this.tracer?.emit("hit", { address, set, way: matchingWay, tag, hits: this.hits, misses: this.misses });      return { address, set, tag, offset, hit: true, way: found, evicted: null };      return { address, set, tag, offset, hit: true, way: matchingWay, evicted: null };    }    // Fill an empty line if there is one; otherwise replace the least recently used.    let way = lines.findIndex((line) => !line.valid);    if (way === -1) way = lines.reduce((oldest, line, i) => (line.lastUsed < lines[oldest]!.lastUsed ? i : oldest), 0);    const victim = lines[way]!;    const lineToReplace = lines[way]!;    const evicted = victim.valid ? victim.tag : null;    const evicted = lineToReplace.valid ? lineToReplace.tag : null;    if (evicted !== null) this.evictions++;    lines[way] = { valid: true, tag, lastUsed: this.time };    this.misses++;    // ▸ no line holds the tag: fetch the block into an empty line, or into the line used longest ago    this.tracer?.emit("miss", { address, set, way, tag, evicted, hits: this.hits, misses: this.misses });    return { address, set, tag, offset, hit: false, way, evicted };  }  /** Every access in order. */  run(addresses: readonly number[]): CacheReport {    if (addresses.length > MAX_ACCESSES) throw new RangeError(`${addresses.length} accesses exceeds ${MAX_ACCESSES}`);    for (const address of addresses) this.access(address);    return this.report();  }  report(): CacheReport {    const accesses = this.hits + this.misses;    return { accesses, hits: this.hits, misses: this.misses, evictions: this.evictions, hitRate: accesses === 0 ? 0 : this.hits / accesses };  }}

hitRate =: 50%
evictions =: 12

16 hits and 16 misses in 32 accesses: a hit rate of 50%, with 12 evictions.

import type { Tracer } from "../trace";export interface CacheConfig { /** How many blocks the cache holds; a power of two. */ lines: number; /** Words per block; a power of two. The offset picks the word inside a block. */ blockWords: number; /** Lines per set: 1 is direct mapped, `lines` is fully associative. */ ways: number;}export interface CacheLine { valid: boolean; tag: number; /** The access count when the line was last touched, for least-recently-used replacement. */ lastUsed: number;}export interface AccessResult { address: number; set: number; tag: number; offset: number; hit: boolean; /** The way the block sits in after the access. */ way: number; /** The tag the miss threw out, or null when the line was empty. */ evicted: number | null;}export interface CacheReport { accesses: number; hits: number; misses: number; /** Misses that threw a valid block out, as opposed to filling an empty line. */ evictions: number; hitRate: number;}export const MAX_CACHE_LINES = 64;export const MAX_ACCESSES = 256;const isPowerOfTwo = (n: number): boolean => Number.isInteger(n) && n > 0 && (n & (n - 1)) === 0;/** * A cache between a processor and its memory: a few lines, each * holding one block of consecutive words. An address splits into an * offset (which word of the block), a set index (which lines the block * may use), and a tag (which block of all those that map to the set * is actually there). A lookup compares the tag against every line of * the set: a match is a hit, anything else a miss that fetches the * block and, when the set is full, throws out the line used longest * ago. Programs that touch nearby words soon after one another hit * because of the block; programs that return to the same words hit * because of the lines; everything else misses. * * Time: O(ways) per access. Space: O(lines). */export class CacheSimulator { private readonly sets: CacheLine[][]; private readonly setCount: number; private time = 0; private hits = 0; private misses = 0; private evictions = 0; constructor( readonly config: CacheConfig, private readonly tracer?: Tracer, ) { const { lines, blockWords, ways } = config; if (!isPowerOfTwo(lines) || lines > MAX_CACHE_LINES) throw new RangeError(`lines must be a power of two up to ${MAX_CACHE_LINES}`); if (!isPowerOfTwo(blockWords)) throw new RangeError("blockWords must be a power of two"); if (!Number.isInteger(ways) || ways < 1 || lines % ways !== 0) throw new RangeError("ways must divide the line count"); this.setCount = lines / ways; this.sets = Array.from({ length: this.setCount }, () => Array.from({ length: ways }, () => ({ valid: false, tag: 0, lastUsed: 0 }))); } /** The lines of a set, as they stand. */ set(index: number): readonly CacheLine[] { const lines = this.sets[index]; if (!lines) throw new RangeError(`no set ${index}`); return lines.map((line) => ({ ...line })); } /** How an address splits for this cache. */ decompose(address: number): { offset: number; set: number; tag: number } { const block = Math.floor(address / this.config.blockWords); return { offset: address % this.config.blockWords, set: block % this.setCount, tag: Math.floor(block / this.setCount) }; } /** One memory access by address: a hit, or a miss that fills a line. */ access(address: number): AccessResult { if (!Number.isInteger(address) || address < 0) throw new RangeError(`address ${address} is not a word address`); this.time++; const { offset, set, tag } = this.decompose(address); const lines = this.sets[set]!; // ▸ split the address: the offset picks the word in a block, the set picks the lines, the tag names the block this.tracer?.emit("lookup", { address, set, tag, offset, time: this.time, tags: lines.map((line) => (line.valid ? line.tag : null)) }); const found = lines.findIndex((line) => line.valid && line.tag === tag); const matchingWay = lines.findIndex((line) => line.valid && line.tag === tag); if (found !== -1) { if (matchingWay !== -1) { lines[found]!.lastUsed = this.time; lines[matchingWay]!.lastUsed = this.time; this.hits++; // ▸ a line of the set holds the tag: the word is here, and the line is marked as just used this.tracer?.emit("hit", { address, set, way: found, tag, hits: this.hits, misses: this.misses }); this.tracer?.emit("hit", { address, set, way: matchingWay, tag, hits: this.hits, misses: this.misses }); return { address, set, tag, offset, hit: true, way: found, evicted: null }; return { address, set, tag, offset, hit: true, way: matchingWay, evicted: null }; } // Fill an empty line if there is one; otherwise replace the least recently used. let way = lines.findIndex((line) => !line.valid); if (way === -1) way = lines.reduce((oldest, line, i) => (line.lastUsed < lines[oldest]!.lastUsed ? i : oldest), 0); const victim = lines[way]!; const lineToReplace = lines[way]!; const evicted = victim.valid ? victim.tag : null; const evicted = lineToReplace.valid ? lineToReplace.tag : null; if (evicted !== null) this.evictions++; lines[way] = { valid: true, tag, lastUsed: this.time }; this.misses++; // ▸ no line holds the tag: fetch the block into an empty line, or into the line used longest ago this.tracer?.emit("miss", { address, set, way, tag, evicted, hits: this.hits, misses: this.misses }); return { address, set, tag, offset, hit: false, way, evicted }; } /** Every access in order. */ run(addresses: readonly number[]): CacheReport { if (addresses.length > MAX_ACCESSES) throw new RangeError(`${addresses.length} accesses exceeds ${MAX_ACCESSES}`); for (const address of addresses) this.access(address); return this.report(); } report(): CacheReport { const accesses = this.hits + this.misses; return { accesses, hits: this.hits, misses: this.misses, evictions: this.evictions, hitRate: accesses === 0 ? 0 : this.hits / accesses }; }}