One access, eight kilobytes

Every measurement on this site so far rests on an assumption that has never been written down: that one array access costs one unit.

It is in lib/count.js on the first line of the first phase. get(i) increments a counter by one, and it does so whether i is the element next to the last one or four million elements away. That assumption is not hidden — it is the definition of an operation count, and counting instead of timing argues at length that a count is worth having precisely because it is machine-independent.

It is also, for data that does not fit in memory, wrong by a factor of a hundred, and wrong in a way that no amount of counting more carefully can repair.

The unit that is actually moved #

Memory is not addressable one element at a time. A cache line is 64 bytes; a disk page is 4 or 8 or 16 kilobytes; a network fetch has a minimum useful size measured in packets. Whatever the level, the machine moves a block, and the smallest thing it can move is that block.

Asking for one element therefore fetches everything beside it. Whether that is generosity or waste depends entirely on whether the rest gets used before it leaves.

That picture is the entire model, and the model has a name and a date: Aggarwal and Vitter, 1988, the external-memory or I/O model. It is three numbers.

• n — the problem size, in elements. The familiar one.
• B — the block. How many elements move in one transfer, and the smallest unit that can be moved at all.
• M — how many elements fit in fast memory at once. M/B is therefore how many blocks are resident, and it turns out to be the number that decides the base of every logarithm in the field.

The cost of a computation is the number of block transfers between fast and slow memory. Work done inside fast memory is free.

That last sentence is a lie about every machine ever built, and it is a lie in a stated direction, which is the only kind this site permits. It is the limit in which moving the data dominates computing on it — and that limit is not exotic. It is the case whenever the data is on a disk, across a network, or merely much larger than the last level of cache, which for a modern machine means anything above about thirty megabytes.

Why the factor is exactly B #

The three rows in the opening figure are not three different algorithms. They are the same 65,536 accesses in three orders, and the ratio between the best and the worst is 64 — which is B.

That is not a coincidence and it is the model’s first theorem. Reading in order, each block arrives once and all B of its elements are used before it leaves: n accesses cost n/B transfers, and no algorithm that must look at all of its input can cost less than that. Reading one element per block, each access costs a whole transfer: n accesses cost n. Every access pattern sits between those two, and the spread between them is B.

So the same algorithm, on the same data, differs by the block size depending only on the order it chooses to walk. A factor of 64 is not a constant that the notation drops. It is larger than the difference between any two sorting algorithms this site has measured.

Why the random row is 61,407 rather than 65,536 #

The third row of the opening figure is worth a paragraph, because it is the one number in it that is not round and the roundness of the others is what makes it visible.

Striding by exactly B costs 65,536 transfers, one per access, and that is a ceiling: no access can cost more than one transfer. Random access costs 61,407, which is 93.7% of the ceiling and not 100%. The missing 6.3% is not noise and it is not the model being generous.

The array is 1,024 blocks and fast memory holds 64 of them, so at any moment 6.25% of the array is already resident, and an access drawn uniformly at random lands on a resident block with that probability. Measured: 4,129 hits in 65,536 accesses, a hit rate of 6.30% against the 6.25% the ratio predicts. The two agree to within the noise of one seeded sequence, which is the sort of check worth making because it is the difference between understanding a number and reporting one.

That is a small quantity and it is worth knowing that it is there, because it is exactly what makes a random access pattern look better in a model than it will on a machine whose useful cache is a smaller fraction of the data. A random walk over data sixteen times the size of memory does not miss every time; it misses 93.7% of the time, and the 6.3% is a statement about the ratio M/n rather than about the algorithm.

Both figures above were drawn from the same seeded stream, so both reproduce byte for byte on every build, and the 61,407 is a measurement of a specific sequence rather than an expectation over sequences. That distinction is expected is not average’s, and it applies to a cost model exactly as it applies to a running time.

Nothing here is new to the reader who has followed the cache field #

The count is not the time made this argument once already, and where an algorithm looks drew the pictures. lib/cache.js has modelled a cache since the foundation phase and reports a miss count beside every comparison count.

So it is worth being precise about what is actually different, because the mechanism is close to identical — a set of resident blocks, a replacement rule, a counter — and dressing up a small difference as a large one would be exactly the sort of thing this site exists to refuse.

Three things differ, and each one turns out to be worth a field.

First, B and M are stated rather than modelled. lib/cache.js picks a plausible cache — 64 lines of 8 elements — and reports what a trace does in it. The numbers it produces are a property of that choice, and the essays using it say so. Here the two numbers are parameters of the claim: an algorithm is optimal at a stated block size and a stated memory, the word means nothing without them, and a figure that omits either has said nothing at all. Every plate in this field prints both.

Second, the algorithm is allowed to know them. This is the real difference. In the cache field the hardware is a fact: the algorithm cannot negotiate with it and the essays measure what happens. Here a structure can be designed around B — a B-tree is precisely that, a tree whose node is one block because somebody looked up the block size — and the cost of the design is then a function of a number the designer chose. That opens a question the cache field cannot ask: what can an algorithm achieve when it is told neither number? The answer is surprising and is the layout that is told nothing.

Third, writes are counted separately, because they are a different resource. A block that has been written to costs a transfer on the way out as well as on the way in. lib/cache.js counts misses and stops; a structure whose reads are cheap and whose writes are amplified fiftyfold is invisible to it. That structure is what a modern storage engine is, and the counting is the writes nobody counted.

The same accesses at three block sizes #

$B$ is the parameter the whole model turns on, and the sequential row is exactly $n/B$ at every setting while the strided row is $n$ at all of them.

And the other parameter is the memory, which decides how much of a working set survives between uses rather than how much arrives at once.

The sixth counter #

lib/blocks.js is the instrument, and it is the sixth quantity this site counts. The tally so far: comparisons, swaps, reads and writes from count.js; auxiliary slots and stack frames, also from count.js; modelled cache misses from cache.js; random bits from randomness.js; mispredicted branches from branch.js; and now block transfers.

Every one of them was added for the same reason, and by now the pattern is familiar enough to state as a rule: a new counter earns its place by distinguishing two things that every existing counter says are the same.

• The space phase found two merge sorts with identical comparison counts and wildly different total allocation.
• The randomness phase found two reservoir samplers with identical output distributions spending 1,356,399 and 9,380 random bits.
• The practice phase found insertion sort doing 176 times the comparisons of merge sort and one sixth the branch mispredictions.

This one finds the same 65,536 accesses costing 1,024 transfers and 65,536 transfers. It is the widest gap of the four, and unlike the other three it is not a subtlety — it is the difference between a query returning and a query timing out.

The instrument carries five assertions and each one can fail. A scan must cost exactly ⌈n/B⌉ transfers and never one more, because every bound in this field is quoted in units of a scan and a model that overcharged a sweep would be wrong about the one pattern the whole field is calibrated against. A dirtied scan must cost exactly twice a clean one. Two traces of identical length must differ by about B, or the transfer count is a second name for the access count. The offline optimum must never lose to a runnable policy, and must strictly beat it on some trace. And a memory too small to hold two blocks must be refused outright, because a merge with one block resident cannot hold an input and an output at once, and a model that reported numbers for such a machine would be reporting numbers for a machine on which nothing runs.

What the model immediately buys #

The reason to adopt a cost model is that it changes an answer, and this one changes the answer to the most-taught question in the subject.

Binary search over a sorted array is optimal in comparisons. That is not a claim about implementations, it is the floor under every comparison sort’s argument applied to searching: ⌈log₂(n+1)⌉ comparisons, and no comparison-based algorithm does better, ever.

In transfers it is nearly the worst thing available.

Binary search’s first probe is at n/2, its second at n/4, and so on. Every probe until the last log₂ B of them lands in a block of its own, so the cost is about log₂(n) − log₂(B) = log₂(n/B) — a saving of a constant number of transfers and nothing asymptotic at all, because the base of the logarithm is still two.

A B-tree changes the base. Its node is one block, so one transfer resolves log₂ B comparisons rather than one, and the height is log_B n instead of log₂ n. At B = 1024 that is a tree of height 3 over four million keys, and the measured cost is 1.01 transfers per query, because the root and the four nodes below it are five blocks in a memory holding a thousand, and never leave it.

The optimal algorithm in one model is a poor algorithm in the other, and neither model is wrong. That is the shape of every argument in this field, and it is the reason it exists as a field rather than as a caveat.

Where 1.99 and 1.01 come from #

Those two measured figures are worth deriving rather than quoting, because the derivation is where the third parameter earns its place. A reader who has met B-trees will expect a cost of $\log_B n$, and $\log_{64} 4{,}194{,}304$ is 3.67 — four levels, so four transfers, not two. The model says two, the measurement says 1.99, and the missing pair of transfers is $M$.

Count the tree by levels. At $B = 64$ the root is one block, the level below it is sixty-four, the next is 4,096 and the leaves are 65,536. Fast memory holds $M/B = 1{,}024$ blocks, so the root and the level under it — sixty-five blocks between them — fit and stay, while the 4,096-block level does not. A query therefore pays for the third level and the leaf: two transfers, which is the 1.99 the sweep measured, the shortfall being the queries whose third-level node happened to be resident from a previous one.

At $B = 1{,}024$ the same count gives a different answer. The fanout is sixteen times larger, so four million keys need only three levels: 4,096 leaf blocks, four internal nodes above them, and a root. Fast memory now holds sixty-four blocks — fewer, because $M$ is fixed and blocks are bigger — but the whole top of the tree is five blocks, so everything above the leaves is resident and a query pays for the leaf alone. One transfer, measured 1.01.

So the general shape is not $\log_B n$ but

$$\log_B n \;-\; \log_B M \;=\; \log_B \frac{n}{M}$$

— the height, less the levels that never leave. That subtraction is why the field’s bounds are quoted in $\log_{M/B}$ rather than in $\log_B$: the resident fraction is not a constant to be dropped, it is a whole term, and at these parameters it is half the cost at one block size and all of it at the other.

Two things follow that are easy to miss from the figure alone.

A larger block is not uniformly better. Raising $B$ shortens the tree and lengthens nothing, but it also shrinks $M/B$, so fewer blocks stay resident. Here the first effect wins by a distance; at a block large enough that the root’s own children no longer fit, it stops winning. The dial has an optimum rather than a direction, and the optimum is a function of $M$.

And the residency is what makes the comparison honest. Binary search’s sixteen transfers are already net of the same effect — its last few probes fall inside one block, and its first few land in blocks that a previous query may have left behind. Both structures are measured on a machine with a memory rather than on one that forgets everything between accesses, which is the difference between this model and a miss counter. The cliff where the data stops fitting is the same parameter seen from the other side, and a tree with nodes the size of a block is where the arithmetic above becomes a structure.

What has to be said about the model before it is used #

Two honest limits, stated here because every later essay leans on them.

A block transfer is not a time. It is a count, in the same sense that a comparison is a count. A random read from a spinning disk, a random read from an SSD and a cache line fill differ by four orders of magnitude and this model charges one for each. What it captures is how much data moves, which is the quantity that dominates when the data is large — and it says nothing whatever about how long the moving takes.

The model has no prefetching, no concurrency and no asymmetry beyond the write-back charge. A real system reads ahead when it detects a sweep, issues many requests at once, and writes at a different cost from reading. All three change the constants and none changes the exponents, which is the usual defence and is worth exactly what such defences are usually worth. The block that is not a block is the essay that takes the defence apart and says what survives it.

What survives, and what the rest of this field is built on, is the one thing the model gets exactly right: the unit of cost is the block, and an algorithm that ignores that is choosing to pay for B−1 elements it will not use.

There is a third limit which is not a limit on the model but on this site’s use of it, and it is the same one every phase here has had to state. Every figure in this field is drawn at sizes that fit in a browser during a build — arrays of tens of thousands rather than the billions the model was invented for. The model’s asymptotics are not established by those measurements and could not be: a limit is not a prediction applies to a transfer count exactly as it applies to a comparison count. What the measurements do is what measurement has done throughout this collection — refuse a claim that is wrong, and put a number on the constant that the notation drops. Both are worth having. Neither is a proof, and no essay here pretends otherwise.