A filter that reads the word it saves

What it costs to consult two bits a pair priced a record that had been counted as free. The two-ended selection sort scans for the smallest and largest keys left and swaps them to the ends, and a pass repaid by the scans after it gave it a pass first that compares every key with the next, so that a record of two bits a neighbouring pair holds which way each pair points. A question about positions $i < j$ is answered without a comparison when every pair from $i$ to $j - 1$ points the same way. Read sixteen pairs to a 32-bit word, the record cost 1.09 words a question on 1,024 keys in runs of four, and its reading stops at the first pair that breaks the run, so almost every question costs one word. The price that mattered was the other number: 201 word reads for every comparison the record saved, because it saves a comparison on about one question in two hundred.

Its closing section looked for a way to ask less. The record can say, before any of its words is read past the first, where it has nothing to offer: a position whose pair to the right is unknown, or whose run turns at that position, cannot start an answer about any position two or more to its right. A sort could keep one more bit a position, set when the pair there is known and the next pair points the same way, and consult the rest of the record only when that bit is set at the question’s first position. The bit would sit in the same word as the pair. The prediction was that on runs of four keys it would turn away about three quarters of the questions, and that the price a saved comparison would fall by about that factor, to under sixty word reads at 1,024 keys. It named the risk that the sort’s questions are asked from its current extreme, and that the extreme might sit mid-run more often than a random position does.

The filter turns away nearly as many questions as predicted. The price barely moves, and the reason was in the earlier essay’s first number all along.

A bit that says where a run can start #

The sort, the inputs and the pass are the earlier essay’s: the two-ended selection sort with its pass between neighbours and its two chains of past minima and maxima consulted first, on 256, 1,024 and 4,096 keys cut into sorted runs of 4 keys up to the whole array, the runs’ values interleaving at random. Every question the sort puts to its record of adjacent order is charged three ways at once, and none of them changes the sort or its answers, which are still checked against the keys.

The record of two bits a pair is charged as before: the words from the one holding the pair at $i$ to the one holding the last pair examined. The run list, which keeps even the runs too short to drop, is charged its binary-search probes. Behind the filter, a question about positions two or more apart reads the word holding the pair at $i$, finds the filter bit beside it, and is turned away at that one word if the bit is clear, meaning the pair at $i$ is unknown or the pair at $i + 1$ points the other way. If the bit is set, the question reads on as the plain record would. A question about two neighbours needs only the pair at $i$ and reads that one word in every scheme. The filter bit is never clear for a question the record could answer, since any answer needs the pairs at $i$ and $i + 1$ to point one way.

Two thirds turned away, one word each #

On 1,024 keys in runs of four, the filter turns away 66% of the questions put to the record and brings the words read from 1.094 a question to 1.007. On runs of sixteen it brings them from 1.141 to 1.001. The two curves are one curve at the scale of the plate, and so is the curve of the run list’s probes they were measured against: the list is still 8.80 probes a question on short runs and still becomes the cheaper record only on runs of 512 keys.

The same holds at every size. Behind the filter the record reads 1.008 words a question at 256 keys, 1.007 at 1,024 and 1.006 at 4,096 on runs of four, against 1.060, 1.094 and 1.074 without it: whatever the size, the filter takes the reading to within a hundredth of a word of one, and the size of the input changes nothing about that one.

A question the record cannot answer was already cheap. It reads the word holding the pair at $i$, finds that pair unknown or the next one turning, and stops, all inside that word unless the pair at $i$ is the last of its word. The filter reads the same word and stops in the same place. What it saves is the second word, read only when the break falls just across a word boundary, which happens to about one turned-away question in eight. The rest of what the record reads beyond its first word is the scan across an answer, and an answer is exactly what the filter lets through.

Close to the three quarters predicted #

The filter turns away 54% to 67% of the record’s questions at every size and every run length short of a sorted array, and at 1,024 keys in runs of four only 13% of the questions it turns away would have cost the record more than the one word the filter reads. The prediction’s three quarters is close. Its reasoning, that a run of four has a pair pointing the same way after only half its positions, is the right kind of reasoning about where runs start. The risk it named, that the current extreme sits mid-run more often than a random position, does not materialise; the extreme turns the run at its own position about as often as the share suggests.

The share is nearly flat in run length because a question’s first position is the sort’s current minimum or maximum, and an extreme of what is left is, by construction, a place where the order turns: the key after a minimum is larger, and on interleaved runs the key after that is often smaller again. Long runs raise the chance that the next pair points the same way, but the extremes of the unsorted remainder are mostly at the turns between runs, so even on runs of 512 keys more than half the questions start where nothing can be answered.

The reading beyond the first word #

Of the 0.094 words a question the record reads beyond the first on 1,024 keys in runs of four, the filter removes 92%; on runs of 512 keys it removes 1% of the 4.85. On short runs the reading beyond the first word is almost all wasted reading of turned-away questions that straddle a word boundary, and the filter takes nearly all of it. On long runs it is the reading of answers, the scan from $i$ to $j - 1$ across a run that holds them both, and the filter is designed never to stop that.

Between those two ends the share the filter removes falls steadily: on runs of 32 keys the record reads 0.425 words a question beyond the first and the filter 0.350, and on runs of 128 the record reads 1.77 and the filter 1.73. As runs lengthen, more of the questions the sort asks are about positions inside one run, the record answers more of them, and answering is reading.

So the filter works exactly as designed and has almost nothing to work on. The plain record’s 1.094 words a question is one word a question plus 0.094, and only the 0.094 was ever in reach. The one word is the price of reading the record at all, and the filter is read in it.

A price made of questions #

Behind the filter the record spends 185 word reads for every comparison it saves on 1,024 keys in runs of four, against 201 without it, and 716 against 764 at 4,096 keys: an eighth of the predicted fall. The prediction expected the price to fall with the questions turned away. It falls with the words saved, and the turned-away questions still cost one word each.

The record is asked 184 questions for every comparison it saves on 1,024 keys in runs of four, and 711 at 4,096 keys. That ratio is the floor under every scheme in which the record is read at least once a question. The plain record pays 1.094 words a question and so 201 a saving; the filter pays 1.007 and so 185; a perfect filter that read exactly one word and never more would pay 184. On runs of four keys the price is set by how often the sort asks, not by how much each answer reads.

The ratio grows with the input because the questions do and the savings do not. The two-ended selection sort asks about $n^2/4$ questions in all, one for every key in every scan, and the record saves comparisons only where runs survive the swaps, about $n$ of them on short runs, a few per scan. Doubling $n$ quadruples the questions and doubles the savings. On long runs the record answers a quarter or a third of the questions and the ratio falls to three or four; there the price is set by the length of the answers, and a filter has nothing to remove.

The record a filter would help #

There is one record on these plates whose cost a filter would cut, and it is not the one the filter was designed for. The run list pays its binary search on every question, answerable or not, because the search is how it finds out whether a run holds the first position at all. A filter bitmap in front of it, one bit a position read in one word, would spare the search on every question it turns away. On 1,024 keys in runs of four, with two thirds of the questions turned away at one word and the other third paying the list’s 8.8 probes, that is about 3.6 reads a question by arithmetic from the measured shares, not a measurement. It is still more than three times what the plain bits cost. The filter makes the expensive record less expensive and leaves the cheap record where it was, because the cheap record was already a filter: its first word answers the filter’s question.

Where the cost of a record really lies #

The earlier essay found that the run list’s search grows with the runs it holds and the bit record’s does not, and concluded that the bits are cheap and the list is not. Measured in reads a question, that is right, and it is the same lesson the record measured where it would run taught about a table of pairs. Measured in reads a saving, both records are expensive on short runs for one reason: the sort asks a record about every key of every scan, and on short runs almost none of those questions can be answered. The questions a sort asks twice measured how often a sort repeats itself; the record answers far less often than that, because answering needs a run between the two positions, not just a past comparison of them.

A filter is a cheaper record of the same fact the record already holds in its first word, so it cannot reduce the number of times that fact has to be read. Something that is read less often than once a question would have to live somewhere the sort reads for nothing. The sort keeps its current minimum and maximum in registers, and every question it asks starts from one of them. That is the place to put what a record knows about where the run from the extreme ends.

The price of remembering an answer put the break-even for a table of compared pairs at three reads a saving. Every scheme on these plates is above that on short runs, by a factor of fifteen at 256 keys and of two hundred and forty at 4,096. On runs of 64 keys or more the record comes within a factor of ten of it at 1,024 keys, and on runs of 256 keys it is at 18.

What the prediction got right #

The closing section predicted that on runs of four keys the filter would turn away about three quarters of the questions. It turns away 66% at 1,024 keys, and 61% to 67% at the other sizes. It predicted that the price per saved comparison would fall by about that factor, to under sixty word reads at 1,024 keys. It falls from 201 to 185, because the questions turned away had cost one word each and still do: the filter bit lives in the word the question reads first.

It named a failure, that the questions a selection sort asks are by their nature about the places where order has just been broken, so that the filter would let through as many as before. That failure does not occur, since the filter does turn away two thirds of the questions, and its premise is right in another sense: the questions are mostly about places where no run can answer, which is why a record read once a question is expensive however it is read. The question the section asked, whether a record can learn where it is useful from its own shape, has a narrow answer. It can, and the shape it learns from is already in the word it reads first.

What the counts assume #

Words, not time. A word read is one unit whether it is in cache or not. The record of 1,024 keys is 64 words and lives in one or two cache lines’ worth of the first level for the whole sort, so a real machine would charge its reads less than a comparison of two keys in memory. Nothing was timed.

One input shape. Runs of a fixed length with interleaved values. Inputs whose runs vary in length, or whose runs are nested, would give a different share of answerable questions; the earlier essays used this shape throughout, and so does this one.

The filter in the same word. The filter bit is charged nothing beyond the word that holds the pair. Kept in a separate bitmap it would cost a second word on every question it lets through and save nothing on the ones it turns away, so the plates show the filter at its cheapest.

Still open: a run end kept in a register #

Every question the sort asks starts from its current minimum or its current maximum, two positions it already keeps in registers, and it asks hundreds of questions from each before either changes. The record’s answer to all of them depends on one number: how far the run starting at that position reaches. A sort could find that number once, by scanning the record from the extreme to the run’s first break, keep it in a register beside the extreme, and answer every later question from that position by one comparison of $j$ with the register, reading no word at all. The register must be refreshed when the extreme moves or when a pair inside its run changes.

The measurement that follows gives the sort two such registers and charges the scans that fill them. The prediction is that on runs of four keys the reads fall from about one word a question to about one word for every change of extreme, so that the price per saved comparison falls from 185 to under ten at 1,024 keys and stops growing with $n$, because the extremes change about as often as the record saves a comparison. It could fail on long runs. A run that spans much of the array is broken at its ends by every pass’s two swaps, and each break forces a rescan of the whole run, so on long runs the register may read more than the plain record does. The question is whether the cost of consulting a record belongs to the questions or to the moments when what the record knows about the question’s first position changes.