The operations a candidate count leaves out

Two essays ago the phrase index’s search examined 4,355 candidates to produce 32 occurrences. One essay ago a wavelet tree over a permutation answered the same query. Put the two numbers together and the grid examines 33 candidates against 4,355, which is a factor of a hundred and thirty-two, and that is the plate this ladder would have shipped if nobody had asked what a candidate costs.

What a candidate is on each side #

They are not the same act, and the whole of this essay is that sentence.

On the filtering side a candidate is a phrase examined: read the boundary’s other rank out of an array, compare it against two integers, and either keep it or not. Three array reads and two comparisons, no loops, no directories.

On the grid side a candidate is a point reported, and reporting one means lifting its position back through every level of the tree — one select per level, each of which is a binary search over a superblock directory and then a scan of up to a block. Before any of that, the descent to find the containing nodes spends two ranks per straddling node per level.

So one side’s candidate is a handful of instructions and the other side’s is a logarithm of them. A plate putting the two counts on one axis is not comparing costs; it is comparing two words that happen to be spelled the same.

The measurement, in the operations both sides perform #

The honest comparison needs a unit both policies pay in. The grid’s own unit is the rank and the select, both counted by the structure’s counter, so the comparison below charges the filter one operation per phrase examined and the grid one per rank and select — which is generous to the grid, since a select is dearer than an array read.

On the collection of thirty-two copies with an eight-character pattern:

• candidates examined: 4,355 filtering, 33 with the grid;
• rank and select operations: 2,209 ranks and 262 selects, so 2,471, against the filter’s 4,355 array reads.

The saving is 1.76 times, not 132. The two ratios differ by a factor of seventy-five, and the seventy-five is entirely the logarithm the previous essay described.

Why the operations do not fall as fast as the candidates #

Because the propagation runs one query per occurrence and the grid pays a descent for each.

The saving that a range structure gives is on the range: it does not walk 140 phrases to find one. What it does instead is descend a tree of $\lceil\log_2 z\rceil = 8$ levels, and it does that once per occurrence, per round of propagation. Thirty-one produced occurrences over several rounds of the queue is on the order of a hundred descents, each costing a couple of dozen ranks at eight levels, plus two binary searches to turn a text position into a pair of ranks.

That comes to about seventy operations per produced occurrence, against a hundred and forty phrase examinations. Both are constants times the answer, and the constants are one apart.

The candidate count is right about the shape: the filter’s cost per occurrence climbs towards the phrase table’s size and the grid’s stays flat, so on a larger collection the ratio grows. It is wrong about the size at the sizes measured, and it is wrong by a factor of seventy-five.

This is the site’s oldest habit, applied to itself #

One run, four counts, four answers is the foundation essay for this: one execution, four honest counters, four different rankings of the same algorithms. Three savings in three currencies is the same lesson in the filter strand, where a counting filter saves cells, a seed filter saves reads and an index walk saves both while spending ranks, and no plate sums them.

What is new here is that the two counts being confused are not two resources. They are one resource counted at two granularities: candidates on one side, and the operations a candidate costs on the other. That is a subtler error and it is easier to make, because both counts are called “work examined” and both are produced by the same instrument.

The rule that catches it is the unit of cost is not one, stated the other way round: before comparing two counts, check that one act on each side is the same act. It was not, and the sentence “the grid examines a hundred and thirty times fewer candidates” would have been true and useless.

What the plate must therefore carry #

Three columns, and they are the ones on the hero.

The candidate counts, both of them, because they are the shape. The grid’s operation count, because that is what its candidates cost. And the answer, because a comparison of two costs with no answer beside it cannot say whether either is close to the floor.

What must not appear is a single “speed-up” number. There is no exchange rate between an array read and a select, so any single number is a choice of exchange rate presented as a measurement — the thing this collection refuses to do everywhere else, and the refusal that produced the four-way plate in the filter strand rather than a winner.

The same confusion, in three places this collection has already been #

It is worth naming them, because the pattern is one pattern and it has produced three separate essays before this one.

A comparison count against a cache-miss count. The count is not the time is the foundation version: two sorts with the same comparison count run at different speeds because a comparison is not one act, and the site’s whole method is built on refusing to convert between the two.

A size against a query cost. A sampling that costs more than the array is the version in the compressed-index strand: a structure built to remove a term proportional to the text costs, on four-symbol text, twice the array it replaced — a size claim that was true in one regime and stated without one.

A skip against a construction. What the approximation gives up is the version in the matching strand: two shift rules whose scans differ by six per cent and whose precomputations differ by a factor nobody had put beside the scans.

Each of those was found by asking what a number counts before comparing it with another number. This one is the same question asked of a data structure’s own instrumentation, and the answer changed the headline by a factor of seventy-five.

What the counter could have said and did not #

The grid’s counter has always reported both numbers. gridWork() returns the ranks and the selects, points returns the candidates, and every plate in this ladder could have drawn either.

The reason the candidate count is the one that would have shipped is that it is the number the earlier essay in the ladder produced. It counted candidates because that was the quantity the filter policy had — a filter has no ranks to count — and a comparison written against an existing measurement inherits its unit without anybody choosing one.

That is the generalisable half of this essay. The unit of a comparison is usually inherited from whichever side was measured first, and the side measured first is usually the one that was already there. The count somebody chose is about this at the level of an algorithm’s own accounting; here it is about the accounting of a comparison between two implementations, and the fix is the same: state the unit, and check that one act on each side is the same act.

The regime where the grid genuinely wins by a lot #

It exists and it is not the one drawn above. The grid’s constant is a logarithm of $z$ and the filter’s is the size of the range it walks, so the ratio between them is the range divided by the logarithm.

On this collection the range is the phrase table, $z = 156$, and $\log_2 z = 8$ — a ratio under twenty before any constant, which is how a hundred-and-thirty-fold candidate saving becomes a not-quite-twofold operation saving. On a collection with a million phrases the range is a million and the logarithm is twenty, and the ratio is fifty thousand.

So the honest statement of the trade is: the grid replaces a term proportional to $z$ with a term proportional to $\log z$, and on a collection small enough to draw the two are a factor of two apart. That is the same structure of claim as a limit is not a prediction — an asymptotic statement that is true, is the right thing to build for, and says nothing about the size actually in hand. The cliff where the data stops fitting is the other half of the same caution: the size at which an asymptotic argument starts describing the machine is a measurement, and it is usually further out than the argument suggests.

What a reader should take from a “range structure” claim #

Three questions, and they generalise past this structure.

What is the range? A published bound of $O((t+1)\log z)$ is only better than $O(\text{range})$ when the range is much larger than $\log z$. On a small grid it is not.

What is the unit? The $\log z$ has a constant, and here the constant is a select — a binary search and a scan, not an array read. A bound that hides its primitive hides its constant.

And what does it cost before the first query? Nothing above has mentioned bits, and the grids on this collection are 27% of the whole structure. That is the next essay, and it is the column that decides whether any of this is worth building.

That third question is the one this collection asks of every structure it builds, and it is the reason an index has a size is a thread rather than a remark. A query cost quoted without a size is half a statement, and the half that is missing is the one paid whether or not anybody searches.

How the two numbers are taken, which is why they can be compared at all #

Both policies are built over the same parse. The grid index is a subclass of the filtering index rather than a second implementation, so the phrases, the three orderings, the binary searches into them and the character production are one body of code; only the two intersection methods are replaced.

That matters more than it sounds. A comparison between two implementations of a compressed index is nearly always a comparison of two parses as well, and a parse differing by five per cent in phrase count moves every number downstream of it. Here the parse is computed once and handed to both, and the sweep refuses to return a row at all unless the two policies produced identical occurrence sets — so a saving can never be a difference in what was found.

The counters are kept apart for the same reason. The grid has its own IndexCounter, separate from the index’s, so the ranks the backward searches spend are not attributed to the structure that did not spend them. Folding them together would have made the grid look worse by a constant that belongs to both policies, which is the mirror image of the error this essay is about: an inflated denominator is as misleading as a deflated numerator, and neither is visible in a ratio.

This is the discipline counting instead of timing sets out and one run, four counts, four answers turns into a method — one execution, several counters, no summing. What this essay adds is that the counters have to be at the same grain, and that a counter inherited from an earlier essay is a counter nobody chose.

What the filter’s candidate actually costs, since the comparison was generous #

The measurement above charges the filter one operation per phrase examined, and that is not quite fair to the grid: a phrase examination is three array reads, a bounds test and a set insertion, while a rank is a directory lookup and a scan of up to sixty-four bits.

Being precise about it does not rescue the hundred-and-thirty-fold figure and it does move the two-fold one. If a rank costs three array reads’ worth of work and a select five, the grid’s 2,471 operations are worth about eight thousand array reads against the filter’s 4,355 — and the grid loses.

That number is not offered as a result, because this collection does not have an exchange rate between a rank and an array read and inventing one would be exactly the error the essay is about. What it is offered as is the size of the uncertainty: the honest comparison is somewhere between “the grid wins by 1.8” and “the grid loses by 1.8”, and which of those is true is a property of a machine rather than of the two structures.

The way out of that is not a better exchange rate. It is a larger $z$, where the ratio is the range over the logarithm and no plausible exchange rate reaches it. Which is to say: the grid is the right structure for a collection this ladder cannot draw, and on the collection it can draw, the honest answer is that the two are within a small constant of each other.

The crossing the uncertainty leaves standing #

The section above ends with an interval — the grid wins by 1.8 or loses by 1.8, depending on an exchange rate nobody here has measured — and then defers to a larger $z$ without saying how much larger. That number can be bracketed without fixing the rate, by asking the same question at both ends of the interval.

The two costs scale differently and both scalings are established on this page. The filter’s cost is proportional to the range it walks, so it grows with $z$. The grid’s is proportional to $\log_2 z$. At $z = 156$ the filter spends 4,355 array reads; the grid spends 2,471 operations, which is 2,471 array reads under the generous accounting and about 7,937 under the pessimistic one — three array reads a rank and five a select, which is where the essay’s eight thousand comes from.

Under the generous rate the grid is already ahead at $z = 156$, so the crossing is somewhere below the collection drawn.

Under the pessimistic rate, set $27.9\,z$ against $1{,}090\log_2 z$ — the two costs rescaled from the measurement — and they meet at about 330 phrases.

So the whole of the uncertainty is this: the crossing is at a phrase count somewhere between well under 156 and about 330. Not a collection this ladder cannot draw — a collection roughly twice the size of the largest one it did.

That is a materially better closing statement than the interval it replaces, and the reason is worth extracting. An exchange rate nobody has measured propagates into a ratio as a factor of three either way, which is a useless answer. Propagated into a crossing point it becomes a factor of two in $z$, because the two costs diverge — one linear, one logarithmic — and a divergence turns a large uncertainty in the vertical into a small one in the horizontal.

Where two curves separate, the question worth asking is where they cross, not how far apart they are at one point. A ratio at a single size inherits the full uncertainty of the unit; a crossing inherits only its logarithm. This collection has been asking the first question of the grid throughout and the second question is cheaper to answer and harder to get wrong.

Two cautions on the number, because it is an extrapolation and this page is about not overstating one.

The scaling is assumed, not measured past $z = 156$. The filter’s linearity in the range and the grid’s logarithmic descent are both structural and both visible in the sweeps here, but nothing on this page runs at $z = 330$, so the crossing is a prediction of the kind a limit is not a prediction warns about — with the difference that it is a prediction about a size only twice the measured one rather than about infinity.

And the constants ride on one collection. Both rescalings take their constant from a single query on English at thirty-two copies. The four-symbol sweep has a larger phrase count and would place the crossing elsewhere, which is precisely the experiment this argument suggests: not a better exchange rate, but a corpus whose $z$ straddles 330.

Which is what three savings in three currencies recommends done one step further. Refusing to sum currencies is right; refusing to say anything quantitative about a comparison that spans them is a habit rather than a principle, and a crossing is the statement that survives the refusal.

What is being claimed #

The candidate ratio is 132 and the operation ratio is 1.76, on one query, one collection, one pattern. Both are measured, both are true, and only the second is a saving.

The difference is the logarithm, spent once per query in the descent and once per level per point in the lifting.

The shape is the candidate count’s and the size is the operation count’s. The filter’s cost per occurrence climbs with the phrase table and the grid’s does not, so the ratio grows without bound as the collection does — and at $z = 156$ it is under two.

And a single speed-up number would require an exchange rate nobody has measured. An array read and a select are not the same act, this collection has never given them a conversion, and the plate has three columns for that reason.