The CPU waits a lot
A CPU can do an addition in a fraction of a nanosecond, but fetching from main memory (RAM) takes ~100 ns — hundreds of wasted ticks. So chips keep small, fast caches of recently used memory. Read memory in the right order and almost every read is a fast hit.
- Registers: < 1 ns
- L1 cache: ~1 ns (tens of KB)
- L2/L3 cache: 3–40 ns (MBs)
- RAM: ~100 ns (GBs)
- SSD: ~100,000 ns
A direct-mapped cache
Memory moves in cache lines (blocks), e.g. 16 bytes at a time. In a direct-mapped cache every block has exactly one line it can live in: index = block % lines. The tag remembers which block is there. Reading a neighbour of something you just read is a hit — locality.
function makeCache(lineCount, blockSize) {
const lines = new Array(lineCount).fill(null);
let hits = 0;
let misses = 0;
return {
read(address) {
const block = Math.floor(address / blockSize);
const index = block % lineCount;
const tag = Math.floor(block / lineCount);
if (lines[index] === tag) {
hits++;
return "hit";
}
lines[index] = tag;
misses++;
return "miss";
},
stats() {
return { hits, misses };
},
};
}
function addresses(rows, cols, order) {
const out = [];
if (order === "row") {
for (let r = 0; r < rows; r++) for (let c = 0; c < cols; c++) out.push((r * cols + c) * 4);
} else {
for (let c = 0; c < cols; c++) for (let r = 0; r < rows; r++) out.push((r * cols + c) * 4);
}
return out;
}