The block that is not a block

Every field on this site ends with the essay that says what its instrument cannot see, and this one has more to say than most, because the external-memory model is a bolder simplification than anything the site has used before. It sets the cost of all computation to zero.

That is not a small thing to assume and it is the assumption that makes every result in this field clean. So the question is not whether the model is a lie — it is, deliberately and in a stated direction — but which of the claims built on it survive contact with a machine, and which do not.

The replacement policy is assumed away #

The cache-oblivious results quoted in the layout that is told nothing are proved in the ideal cache model, which assumes optimal offline replacement: the cache evicts the block whose next use is furthest away, which requires knowing the future.

Nothing runs that. The figure above measures the gap on the pattern designed to expose it — a cyclic sweep over one more block than fits, where recency is precisely the wrong signal — and LRU costs twice the optimum. On random and sequential patterns the two are equal or nearly so.

The theory’s defence is a real theorem and is worth stating properly, because it is better than it sounds: LRU with a cache of size 2M is within a factor of two of the optimum with a cache of size M. That is Sleator and Tarjan’s competitiveness result, and it means the assumption costs a constant factor and a doubling of memory rather than a change in class.

It is also exactly the kind of defence this site is suspicious of. A constant factor of two, on the resource that dominates, on a workload that is the standard access pattern for iterating over a table — that is not a rounding. The honest statement is that the bounds in this field are for a policy nothing implements, and the penalty for the policies that do exist is bounded, measurable and sometimes 2.

There is no prefetcher #

The model charges for a transfer when the algorithm asks for it. A real memory system watches the access pattern, detects a sweep, and issues the next transfer before it is requested — so that a sequential scan’s transfers overlap with the computation and cost, in time, very nearly nothing.

That does not change any transfer count in this field. It changes what the counts mean, and it changes them unevenly: a sequential pattern’s transfers become nearly free in time, and a random pattern’s do not. So the gap between the best and worst rows of the opening figure of one access, eight kilobytes — a factor of 64 in transfers — is larger than 64 in duration, because the 1,024 sequential transfers are prefetched and the 61,407 random ones are not.

The model understates its own headline result. That direction is worth having explicitly, and it is unusual: most simplifications on this site flatter the thing being measured.

There is one level, and a machine has five #

The model has fast memory and slow memory. A machine has registers, L1, L2, L3, main memory, an SSD, and possibly a network, each with its own B and its own M, and each pair of adjacent levels forms its own instance of this model with different parameters.

Analysing one level at a time is standard and it is what every number in this field does. What it cannot express is an algorithm that is good at one level and bad at another — which, as the layout that is told nothing argues, is what a tuned structure usually is.

The cache-oblivious construction is the honest answer to this, and it is the reason the idea matters more than its adoption suggests. An oblivious bound is a claim about every adjacent pair of levels at once, which is the only kind of claim that describes a real hierarchy without being restated five times with five sets of constants.

A transfer is not a duration, and the spread is four orders of magnitude #

The model’s unit is a count. Its costs, on a machine bought in 2026:

Charging one for each of these is a stronger simplification than anything lib/cache.js does, and the field’s numbers are only meaningful within a level. Comparing a B-tree’s 4 transfers to a sorted array’s 13 is a real comparison as long as both are between the same two levels; comparing either to a comparison count is not a comparison at all.

This is the same discipline the count is not the time established for the operation count, and it is the reason this site has never once converted a count into a predicted duration. Six counters now, none of them a time, and the refusal is deliberate rather than a gap waiting to be filled.

Nothing here is concurrent #

One request at a time, no queue, no parallelism. A real storage device is at its best with a hundred requests outstanding: an SSD’s throughput at queue depth 32 is many times its throughput at depth 1, because the internal parallelism has something to work with.

The consequence is that an algorithm’s transfer count and its achievable throughput are different quantities. An algorithm issuing 1,000 independent random reads can have them all in flight at once and finish in about the time of one; an algorithm issuing 1,000 dependent reads — each address computed from the last, which is exactly a tree descent — must wait for each. Same count, wildly different duration.

That distinction has a name in the literature (memory-level parallelism) and it is the reason a hash index’s single random read is better than its transfer count suggests, and a pointer chase is worse. A B-tree descent is the worst shape available under this criterion, because every level depends on the one above.

Two things follow, and they are worth being blunt about because they qualify results in this very field. Sorting’s transfer count is a good predictor of its cost, because a merge’s reads are independent and can be issued ahead. A search’s transfer count is a poor predictor, because its reads are a dependent chain. The same counter is more trustworthy for one of this field’s two headline problems than for the other, and nothing in the count says so.

Reads and writes are not one resource, and the model only half admits it #

The writes nobody counted charges a dirty block on the way out as well as on the way in, which is the model’s one concession to asymmetry, and it is not enough.

On flash, an in-place update triggers erase-and-reprogram inside the device and the device’s own garbage collector writes more data than the application ever asked to store. Endurance is finite: a cell tolerates a bounded number of programme-erase cycles, so a write is spending something that cannot be replaced. And a write is often durable — it must reach the device before the operation is acknowledged — while a read may be served from any copy.

None of that is in a transfer count. What the count gets right is the ratio: 49.3 against 2.0 elements written per key stored is a real measurement of a real quantity, and every one of the effects above makes the difference larger rather than smaller.

The model is also a simulation, and simulations have their own defects #

Everything above is about the distance between the model and a machine. There is a nearer question, which is the distance between the model and this implementation of it, and it deserves its own paragraph because it is the one this site can actually check.

lib/blocks.js is 300 lines of JavaScript that maintains a set of resident blocks and increments counters. Every number in this field comes out of it. Its five assertions exist because the alternative is a plausible-looking figure drawn from arithmetic that has quietly stopped being the arithmetic described: a scan must cost exactly ⌈n/B⌉ and never one more; a dirtied scan exactly twice a clean one; two traces of equal length must differ by about B, or the counter is a second name for the access count; the offline optimum must never lose and must sometimes win; and a memory too small to hold two blocks must be refused rather than reported on.

Three of the five were written before any figure was drawn and two were written because something looked wrong. The write-amplification measurement came out at zero on its first run, from an index computation that put every insertion into the same leaf, and the assertion caught it — the details are in the writes nobody counted, and the general form is that the code constructing the case is as likely to be wrong as the code being measured and is far less likely to be checked.

What the model is not built for at all #

Three problems where a transfer count is simply the wrong instrument, listed because the boundary of a tool is part of its description.

Anything whose cost is dominated by computation. A matrix multiplication moves n² elements and performs n³ operations; a compression pass reads a file once and spends its time in the coder. Setting computation to zero is a reasonable simplification when the ratio runs the other way and a nonsense when it does not, and the ratio is a property of the problem rather than of the model.

Anything interactive. A count says how much data moves and nothing about when. A structure whose total transfers are excellent and whose merges arrive in unpredictable bursts is a different product from one that spreads the same work evenly, and the model has no vocabulary for the difference — which is the tail-versus-mean argument on average is not a number makes about running times, in a setting where it decides architecture.

Anything where the data is compressible, encrypted, or shared. A block that compresses fourfold moves a quarter as much; a page shared between two readers is fetched once for both. Both effects change the constant by more than most of the tuning arguments in this field, and neither is expressible in a model whose only unit is a fixed-size block of raw elements.

The gap at three settings of the model #

The competitive ratio is a worst case over inputs, and the gap this figure measures is the realised one — so it is worth reading at three settings of the two parameters the model has.

The block size is the other parameter, and the interesting thing about it is that it should do nothing at all to a ratio measured in transfers.

What does move it is how long the pattern is allowed to run, which is the parameter a competitive ratio is silent about because it is stated as a supremum over inputs.

Six counters, and what each one is blind to #

This is the sixth quantity the site counts and the last of them for now, so it is worth setting the blind spots beside each other. Each counter was added because it distinguished two things every earlier one called identical; each of them is, equally, unable to see what the next one was added for.

Reading that table downwards is a fair summary of the site. Reading it across the last column is the more useful direction: every row’s blind spot was invisible until the row below it existed, which is the strongest argument available for expecting a seventh.

The obvious candidate is a counter of time-shaped quantities — dependent chains, queue depth, the difference between a hundred outstanding requests and one — which is the gap this essay spends its longest section on. Whether that can be counted deterministically, which is the price of admission on this site, is an open question and not a promise.

The seventh counter, and it is countable after all #

The essay leaves the dependent-chain problem as a gap and calls the seventh counter an open question. It is less open than that, and the shape of the answer is worth setting out, because the quantity is deterministic and machine-independent in exactly the way this site requires.

Every transfer an algorithm issues either can or cannot be issued before some earlier transfer has returned. That relation is a directed acyclic graph over the transfers, it is fixed by the algorithm and the input, and it has two numbers on it:

The work — the total number of transfers, which is what this field already counts.

The span — the length of the longest chain of transfers each of which depends on the one before. That is the number of rounds the algorithm cannot avoid, however many requests a device will accept at once.

Both are exact integers, both are the same on every machine, and their ratio is the queue depth the algorithm can actually offer.

Applied to this field’s two headline problems, the counter says immediately what the essay’s longest section says in a paragraph. A merge pass reads its runs independently: its work is $n/B$ and its span is a small constant, so its ratio is enormous and a device with a deep queue can be kept full. A tree descent reads each level from an address computed at the level above: its work is the height and its span is also the height, so its ratio is one and no amount of device parallelism helps.

That is the distinction the transfer count alone cannot draw, and it needs no clock, no queue model and no hardware — only the observation that a read whose address comes from a previous read cannot precede it.

Two further things fall out of having both numbers, and both are results the field currently cannot state.

A structure can be improved on the span axis alone. A B-tree descent that fetched several candidate children speculatively would have more work and less span, which is exactly the trade a prefetcher makes on the algorithm’s behalf and which the algorithm could make deliberately. A counter that reported only transfers would score that change as strictly worse.

And the two axes give a frontier rather than a ranking, which is what this site does with every pair of resources it counts. A layout with fewer transfers and a longer chain and one with more transfers and a shorter chain are not comparable without knowing the device’s queue depth — and the queue depth is a property of the hardware, which is exactly where this field puts every other exchange rate it declines to fix.

So the seventh counter is not blocked on inventing a deterministic quantity. It is blocked on the ordinary work of instrumenting the dependencies, and the reason it is worth doing is that it would convert the longest caveat in this essay into a number.

What survives #

Setting all of that beside the field’s claims, four survive without qualification and two do not.

Survives: the unit of cost is the block. Every level of every hierarchy moves a minimum unit and an algorithm that ignores it pays for what it does not use. Nothing above weakens this.

Survives: the base of the logarithm is M/B. The number of passes an external sort makes, and the height of a block-sized tree, are counts of rounds rather than of time, and a round is a round on any hardware.

Survives: the ranking of the structures, within a level. A B-tree moves less than a sorted array; a log-structured store writes less than an in-place tree; a van Emde Boas layout crosses fewer block boundaries. These are facts about arrangements of data and they do not depend on what a transfer costs.

Survives: the floor. The floor under moving data is an information-theoretic argument, and like every floor on this site it is a statement about what cannot be done rather than about a machine.

Does not survive: any statement about duration. Not one of the numbers in this field is a time, and the four-order-of-magnitude spread above is why converting one would be worse than useless.

Does not survive: the ordering of two algorithms whose transfer counts are close. Where the counts differ by 24× or by 64×, the ordering is safe. Where they differ by 20% — which is where most tuning arguments live — prefetching, concurrency and the replacement policy each move the answer by more than that, and the count does not decide the question.

That last line is this phase’s version of a rule the site has now stated four times in four fields, and the repetition is not an accident. A measured quantity is trustworthy up to the size of the effects the instrument does not model, and quoting it past that point is the error the whole collection exists to avoid.