What a pass costs when it is a file

What a second pass buys measured a trade and deliberately left out its price. An exact median of thirty-two thousand values needs about a million bits of state in one pass, eleven thousand in two and three hundred and twenty in nine: the state falls as $n^{1/p}$, and each pass bought is paid for in memory saved. Near its end that essay named where the price would come from. In the external-memory model a pass is $n/B$ block transfers, so nine passes cost nine times the reading of one. It then declined to set an exchange rate, on the grounds that the ratio between memory and bandwidth belongs to a machine rather than to an algorithm.

That is true, and it hides something that does not depend on the machine. A pass over a file is not only $n/B$ transfers. It is $n/B$ transfers through a buffer, and the buffer is memory. A program cannot read a block into less than a block. So the moment a pass is priced as a file, the memory axis acquires a floor: nothing runs in less than one block of $B$ words. The steep part of the state law — the part that makes passes look like a good buy — lies almost entirely under that floor.

This page makes both charges and measures what is left of the trade.

A floor the streaming model does not have #

In the streaming model a pass is free and the only resource is state, so the state law can be read all the way down: nine passes, three hundred and twenty bits. On a file the reading has a unit. A block of 1,024 thirty-two-bit keys is 4 KB, the size of a page on most machines, and it is the least a pass can hold while it reads.

The law crosses the block line early. For a file of four million keys the state two passes need is two blocks, and three passes need a sixth of a block. For a file of a thousand million keys, three passes need exactly one block. Even at a trillion keys — four terabytes of them — the fourth pass is where the state reaches the buffer. The number of pass counts that are worth distinguishing is $\lceil \log n / \log B \rceil$. For every file a single machine holds, that is two, three or four.

Everything the streaming plates drew beyond that — five passes, seven, nine, the three hundred and twenty bits — is state smaller than the buffer the pass must be read through. On a file those points do not save memory. The buffer costs what it costs whatever the counters need, and a selection that could run in 45 words at four passes still needs a thousand of them to read.

Memory decides the passes, and the passes are few #

The measurement is exact selection of the median of 4,194,304 uniform keys held in a file of 4,096 blocks. The selector is the narrowing one from the earlier essays: each pass cuts the surviving interval into as many equal-width pieces as memory allows, counts the keys in each and keeps the piece holding the median’s rank, and the run collects — keeps and sorts what is inside the interval — as soon as that fits beside the read buffer. Memory is the parameter and passes are the result. A pass costs two words a piece (a counter and a cut point), and whatever is left after the buffer goes on pieces. Every answer is checked against a sort of the whole file.

From just over two blocks of memory to 3,072 words the median takes three passes. From 4,096 words — four blocks, 16 KB — it takes two, and it goes on taking two until memory holds the entire file, at which point it takes one. Between 16 KB and 8 MB of memory, a factor of five hundred, nothing changes at all. The trade the streaming model drew as a smooth curve is, on a file, one step at four blocks and another at the size of the file.

Those numbers follow from the law with the buffer added. At 2,100 words the buffer leaves 1,073 words for pieces, which is 536 pieces, and 4,194,304 keys divided 536 ways leaves about 7,800 in the median’s piece. That is too many to collect in the room left beside the buffer, so a second narrowing is needed, and then a third pass to collect. At 4,096 words there are 1,534 pieces and about 2,700 keys survive, which fits. The step sits where $n/s$ falls under $M - B$ with $s \approx (M - B)/2$, which for this file is just under four blocks.

The pass that reads almost nothing #

Rereading is what the streaming model’s passes are: every pass begins at the start of the file. A file allows something a stream does not. A pass can write. It can copy the keys inside the current interval to a new, smaller file while it counts, so that the next pass reads only that.

The second line on the plate does exactly that. It costs a second buffer, one block to write into, and the writes themselves. It is flat at 2.00 file-reads at every memory where rereading costs 3.00.

The trace shows what happens. The first pass cannot write anything useful, because until it has counted, the interval is the whole file. The second pass knows the interval from the first pass’s counts, so as it reads it copies the 7,721 keys inside it — eight blocks — to a new file. The third pass reads those eight blocks. The whole third pass costs sixteen transfers where rereading pays 4,096. The saving is in blocks moved, which a count of the selector’s own comparisons does not see — the gap the count is not the time keeps a second counter for.

So a third pass on a file is nearly free, and the price the streaming model’s trade was waiting for turns out to be close to zero. With the interval written out, two passes and three cost the same, 2.00 reads of the file plus a few blocks. The memory difference between them, four blocks against two, buys nothing a transfer count can see. The pass count ceases to be a cost at all. What remains is two full reads of the file, and that is the real price of exact selection against a file with more than a few blocks of memory: the first pass to find where to look, and the second to look.

The second buffer has a price that the trace also shows. At 2,100 words, one block for reading and one for writing leave 49 words for pieces, so the writing pass counts 24 pieces rather than 536. It narrows less, and its survivors are 314 rather than 15. That does not matter here, because 314 keys fit in memory at once. It would matter if memory were a few words smaller: a second buffer taken from a memory of barely two blocks is most of what was left for the pass’s own state.

That is the practical reading of sorting what will not fit turned to selection. External merge sort writes its runs out because every key has to be placed, and runs twice as long as memory is the page on how much a longer run saves when every key is written anyway. Selection needs only the keys near one rank, so what it writes shrinks by the fan-out each pass, and the sum of those writes is a geometric series dominated by its first term.

Where writing out costs more than it saves #

The plate above is uniform keys, and uniform keys are the case where equal-width cuts narrow by exactly the fan-out. The earlier essay found the rule that needs no data collapses on a heavy tail. A Pareto distribution puts nearly all its mass in a tiny fraction of the range, so an equal-width cut narrows the range and not the count. On a file that failure has a second cost.

Writing out on every pass is the worst policy here, by a wide margin. At 2,100 words it moves 7.64 files’ worth of blocks where rereading moves 4.00. The reason is in the counts. The first narrowing on these keys keeps 4,193,842 of the 4,194,304 — everything but 462, because 536 equal slices of a range up to $2^{30}$ put almost the whole distribution into the first. A pass that then writes the interval out copies all 4,096 blocks to save reading none of them in the pass after. The next narrowing keeps 4,173,548 and the pass after that copies 4,076 blocks more, then 3,178, and only the fifth pass writes something small. The copying is paid in full every time and the saving comes at the end.

A second buffer makes it worse. On uniform keys, 24 pieces instead of 536 was harmless, because the interval was already small. Here the interval is still the whole distribution, and a pass that narrows 24 ways instead of 536 needs more passes to reach it. Writing out at every pass takes six passes at 2,100 words where rereading takes four.

The repair uses information the selector already has. Before a pass begins, the previous pass’s counts say exactly how many keys the interval holds, and the current file’s length is known. So the choice to write out can be made per pass, and the plate’s third line makes it the simplest way: write the interval out only when it is at most half the file being read. On uniform keys that fires on the second pass, where the interval is under two thousandths of the file, and the run costs 2.00 as before. On Pareto keys it holds off until the interval has actually shrunk. At 2,100 words it spills once, on the fourth pass, when the interval has fallen to 9,932 keys. The run costs 4.00, the same as rereading and half of writing out every time.

The rule is not optimal, and the plate says so. At 4,096 words it costs 3.20 where rereading costs 3.00. The interval had fallen to a fifth of the file, so the rule wrote those 820 blocks out — and the pass that wrote them narrowed straight onto the median’s value, so no pass ever read them. At 2,600 words the same bet paid: it wrote 1,193 blocks, read them once instead of the file once, and finished at 3.58 against 4.00. A rule that knew how many passes remained could do better on both, and the number of passes remaining is the one thing a narrowing selector cannot know in advance on data it has not seen. Half is a threshold that is never much worse than either choice. That kind of rule turns up again and again in these essays, and the writes nobody counted is the page where a threshold on writes first had to be priced rather than assumed.

The sampled cuts, priced as reads #

The earlier essay’s repair for the heavy tail was to cut at order statistics of a sample rather than at equal widths. Each piece then holds the same count by construction, at the price of a pass: nobody knows the order statistics until a pass has gone by, so sampling and counting alternate. In the streaming model that price was a pass. On a file it is a read of the whole file, because the first sampling pass sees the whole file whatever the policy.

At 8,192 words the two rules trade places exactly as the earlier essay found for state. On uniform keys the sampling pass is an extra read of the file, 3.00 against 2.00, and it buys nothing that equal-width cuts did not already give. On Pareto keys the sample puts its cuts where the keys are. The first counting pass leaves only the median’s own value, and the run ends a whole pass sooner than equal widths do, 2.00 against 3.00. On log-normal keys, skewed but not extremely, they tie.

What changed is the unit, and the unit decides what a tie means. In the streaming model the comparison was between hundreds of bits and hundreds of thousands, a factor of eighty-three on the heavy tail. On a file both rules spend their state inside one block, so the state difference is invisible, and they differ only in how many whole reads they need: one pass more or one pass fewer. A choice that looked like two orders of magnitude in the streaming model is plus or minus a third on a file.

The Pareto keys also show the floor the earlier essay named for repeated values. They are rounded to integers, and 1,394 of them equal the median. Once the interval has narrowed to that one value, the counts already name the answer and no collecting pass is needed. The selector here takes that shortcut, and it is how every Pareto run above ends: the sampled one after its first count, the equal-width one after its third or fourth. The earlier essay did not take it, and paid for it in a flat row of 4,032-bit peaks.

What was measured and what was not #

Transfers are counted and not timed. A block read and a block written are each one transfer. On a disk a write can cost more than a read. On flash it costs more and wears the device. And the writing-out policy interleaves reads of one file with writes of another, which on a single spinning disk is a seek per block unless both are buffered in larger runs. One access, eight kilobytes is the page on how much a block’s price depends on the device. Every conclusion above about writing out assumes a write costs about what a read does.

The block is 1,024 words and the file is 4,194,304 keys. The step from three passes to two sits where memory reaches about $B + \sqrt{2n}$ — 3,920 words here — so a larger block moves it right by the block and a larger file moves it right by the square root. The law plate carries both, and the sweep was measured at one of each.

One rank, one file, one seed per input. The median of one draw of each distribution. Other ranks behave the same on uniform keys by symmetry. On Pareto keys a rank in the tail narrows more easily, because the tail is where the equal-width cuts have keys to separate, and it was not measured.

The spill rule’s threshold was not swept. Half was chosen before measuring, as the value that can never lose more than the cost of one wasted write of half a file, and the plate reports what it did rather than a threshold tuned to these inputs.

The streaming model is not wrong. It measures a different resource. On a wire there is no file, no second pass and no write, and the state law is the whole story — which is what the pass that was never a parameter set out from. The trade survives exactly where the file does not exist. A floor one pass cannot get under is a statement about that model and stays true. What this page adds is that a reader holding a file should read the law’s steep part as a statement about memory smaller than one page, and should ask a different question.

Still open: the counts a pass leaves behind #

Every selection above starts from nothing. Its first pass reads the whole file and counts 536 or 1,534 pieces, and the run keeps only the one piece holding the rank it wants. The other counts are thrown away. They are a histogram of the whole file at the resolution the memory allowed, and they are exactly what a second query for a different rank would compute again in its own first pass.

The measurement that follows keeps them. It answers a sequence of selection queries against the same file — the median, then the 90th percentile, then the 10th, then a hundred ranks drawn at random — with the first pass’s counts retained between queries. Each later query then starts from its piece’s interval and needs one or two passes over the keys inside that piece rather than two over the file. With the pieces written out once, as a file partitioned by piece, a later query reads only its own piece. The question is how many queries it takes before writing the partition pays for itself, and whether the answer is set by the number of pieces, which is the memory, or by the number of queries, which is the workload. The prediction is that it pays by the second query on uniform keys and not until much later on a heavy tail, where equal-width pieces are one enormous piece and many empty ones. That would make the partition a place where the pass that runs the other way and this page meet: a pass whose value depends on what is asked after it.