Memory hierarchy — where it appears
Named by 7 essays across 4 fields — each of them below, with the objects they name alongside it.
One access, eight kilobytes
Every count on this site charges one for an array access. A machine charges for a block. The same 65,536 accesses cost 1,024 transfers in one order and 65,536 in another, with nothing about the algorithm's work changed — a factor of 64, which is exactly the number of elements in a block, and which no counter here could see until now.
The count is not the time
An operation count is exact, machine-independent, and not a running time. The gap between them is mostly memory, and it is large enough to reorder the rankings. This site carries a second count — modelled cache misses from the same runs — and asserts that the two disagree, because if they agreed the second one would carry no information.
The layout that is told nothing
A B-tree is built around a block size somebody looked up. The van Emde Boas layout is given neither the block size nor the memory size, and across seven block sizes spanning a factor of 64 it tracks the best structure that was told them. An algorithm with no parameters making a claim at every level of the hierarchy at once is a strange thing to be able to measure, and this is what it costs.
The writes nobody counted
Sixteen thousand keys inserted into a B-tree write 49.3 elements' worth of blocks for every key stored. The same keys into a log-structured store write 2.0. Every operation counter reports the two as the same work — the same insertions, the same comparisons, the same number of updates — and the factor of 24 decides which structure a storage engine is built from.
The block that is not a block
This field's model has one memory, one block size, one processor, no prefetcher, no queue and no clock, and every number in it is a count of transfers rather than a duration. A real machine has five levels, reads ahead, issues a hundred requests at once, and charges four orders of magnitude more for one kind of transfer than another. What survives the difference is worth stating exactly, and so is what does not.
A tree with nodes the size of a block
A B-tree is a binary search tree that has read the hardware manual. Its node holds as many keys as fit in one transfer, so the height falls from log₂ n to log_B n — and the measured cost falls further still, to 1.01 transfers over four million keys, because the top of the tree is small enough to stay in memory. The comparison count goes up.
The filter each run carries
A log-structured store turns every lookup for a missing key into a read of every level, and a Bloom filter on each run buys those reads back with memory. Spread five bits a key evenly across three levels and a missing key still wastes 0.279 reads. Give the small levels more bits and the large one fewer — the same memory — and it wastes 0.201. At four levels the gap is 0.382 against 0.209, because sized filters stop the waste growing with the number of levels.
Named alongside it
The objects these essays reach for when they reach for this one.
Block transferCost modelExternal-memory modelB-treeData movementLocalityLsm treeSimulationTrade offWrite amplificationAccess patternBinary search