Two factors that do not multiply

Two savings, measured a strand apart, against the same published baseline, on the same structure.

The compound walk is 11.0×. The interval enumeration is 78.2×.

A reader with both numbers computes 11.0 × 78.2 = 859.7 for an index with both.

The measured figure is 78.2.

The shortfall is one of the factors #

859.7 divided by 78.2 is 11.0.

That is the compound walk’s own factor, to three significant figures. Not approximately, not to within an interaction term, not a shared constant — the same number.

A shortfall equal to one of the two factors says that one of them contributed nothing. The combined index is the enumeration alone, and adding the walk to it changes no operation count at all.

The absolute numbers behind those factors are worth having because the shortfall is easier to feel in operations than in ratios.

Twelve patterns of eight characters, one error, over eight thousand characters of a twenty-symbol alphabet.

The published loop spends 1,478,400 bit-vector ranks. The compound walk inside that loop spends 134,400. The enumeration spends 18,916.

The product would predict 1,719 — under two thousand ranks for a search that visits several thousand intervals, which on inspection is not a plausible number at all: the search’s live extensions alone are seven and a half thousand, and each of them costs at least one rank.

That implausibility is worth noticing because it is available without any of this essay’s arithmetic. A predicted cost below the number of things the search does is a prediction that has gone wrong somewhere, and a reader who checked it against the search’s own shape would have caught the error before building anything.

Why #

The compound walk returns two things from one descent: a symbol’s rank before a position, and the number of characters sorting before that symbol in the interval. Both are needed by a bidirectional extension — the first to move the forward interval, the second to move the reverse one.

The enumeration returns, for every symbol present, its sub-interval — which is [rank_c(lo), rank_c(hi)), which is the walk’s rank.

And running-summing the counts in leaf order gives, for every present symbol, the number of characters sorting before it — which is the walk’s smaller-count.

So one descent produces the walk’s output for every symbol at once. An index that enumerates and then also walks is computing the walk’s two numbers twice.

The identity holds across the budget sweep, which is what makes it a mechanism rather than a coincidence at one point.

At zero errors the walk is 11.0 and the enumeration is 98.1; the product is 1,079 and the measurement is 98.1. At one error: 11.0 and 78.2; product 860, measurement 78.2. At two errors: 11.0 and 104.6; product 1,151, measurement 104.6.

Three budgets, three different enumeration factors, and the shortfall is 11.0 every time. The walk’s factor is flat because it is σ/2 divided by the tree’s depth — a property of the alphabet — and the shortfall tracks it exactly because the shortfall is it.

The check #

Because the arithmetic is exact rather than approximate, the check can be too.

The measured combined factor must fall short of the product, by a stated margin. That catches a claim of independence.

And the shortfall must equal the walk’s own factor, to within two per cent. That catches an interaction of some other size, which would mean the mechanism is not the one described.

Both hold: shortfall 11.0, walk factor 11.0.

The second half is what makes this a claim rather than an observation. A check requiring only the first would pass on any shortfall — an overhead, a cache effect, a shared constant — and the explanation offered would be unsupported by anything.

Where the two savings do differ #

They are not the same operation and it would be wrong to conclude that the walk is redundant.

The walk answers about one named symbol. Its cost is one root-to-leaf descent, 2⌈log₂ σ⌉ ranks.

The enumeration answers about every present symbol. Its cost is 2d(1 + log₂(σ/d)) ranks for d symbols present.

At d = 1 those are the same. At d = 20 the enumeration costs about seven times the walk — and returns twenty times as much.

So on a search that wants one symbol, the walk is cheaper. The saving that is a loss measures that: 10.0 ranks a step against 19.0 on an exact search, a factor of 1.90 the wrong way.

The two savings therefore split by the shape of the search rather than stacking, and both are worth having in one index because both kinds of query occur.

Reading the two descriptions side by side #

The redundancy is visible in the two operations’ own accounts once they are put next to each other, and it is worth doing because the point of the essay is that it could have been seen without a measurement.

The count that was already there describes the compound walk: “at each level the walk already computes one of the two child counts, and when the code says go right the other one — every symbol that went left, all of which sort before c — is the difference between the two.” One symbol, one path, two numbers.

Asking about symbols that are not there describes the enumeration: “each reported symbol comes with the interval it occupies in its own leaf — [rank_c(lo), rank_c(hi)) — which is exactly the interval a search would extend into.” Every symbol, one subtree, an interval each.

The second sentence contains the first’s rank. What it does not say is that running-summing the counts gives the first’s smaller-count too — that is one further step, and it is the step nobody had taken because the enumeration’s own strand was about pruning rather than about counting.

So the redundancy is one inference away from two published descriptions, and the inference is what else that output already contains — which is a question about an operation’s results rather than about its cost, and is not the question either strand was asking.

The general form of the mistake #

A reader multiplying two factors is applying a model, and the model is that the two savings act on disjoint work.

That model is right often enough to be a default. Two optimisations to different phases of an algorithm, two compressions of different arrays, a faster inner loop and a better pruning — all multiply, because each removes a fraction of what the other left.

It fails when the two act on the same work, and then the combined saving is not the product and not the sum but roughly the larger of the two.

Distinguishing the cases needs one question about each saving: what does it remove? Not how large it is.

The walk removes σ ranks from computing a smaller-count. The enumeration removes the extensions those ranks were being spent on. The second’s removal includes the first’s, so the first has nothing left to do.

That question is answerable from the two descriptions, before any measurement, and it would have got the right answer here. What the measurement added is the exactness.

Three kinds of non-composition #

Since the failure mode has a shape, it is worth setting out the three shapes a pair of savings can have when they do not multiply, because only one of them is this one.

Subsumption. One saving’s removal contains the other’s, so the combination is the larger alone. This pair. The signature is a shortfall exactly equal to one factor.

Overlap. Two savings remove intersecting but distinct sets of work, so the combination is between the larger and the product. The signature is a shortfall between one and the smaller factor, and no exact identity.

Interference. One saving makes the other’s work harder — a compression that slows a lookup the other’s pruning depends on. The combination can be worse than either alone. The signature is a combined figure below the larger factor.

The three are distinguishable by the shortfall alone, before anything is understood about the mechanism, which makes the shortfall worth computing whenever two savings are applied together.

This collection has an instance of the second: three savings in three currencies measured a set of filtering improvements whose combination fell between the larger and the product, and the reason was that two of them pruned overlapping candidate sets. And it has no clean instance of the third, which is the one to watch for.

The other two pairs #

This strand has three savings and the other two pairs behave differently, which is what makes the classification useful rather than a rule about these two.

The marks and the walk. One is bits, the other operations. A search costs 12,486 ranks whether the marks are plain or sparse — identically, checked as an equality — and the sparser index is smaller. These compose.

The marks and the enumeration. Same argument. Compose.

So of three pairs, two compose and one does not, and the one that does not is the pair whose members are both about extensions.

That is the whole classification and it can be read off the descriptions: two savings compose when they are about different quantities, and one subsumes the other when one’s removal contains the other’s.

What the plate has to show #

Drawing this result was a small design problem worth recording, because the natural plate does not show it.

The obvious figure is three bars: the loop, the walk, the enumeration. That is three savings on one structure’s plate, and it shows the two savings and says nothing about their combination — because the combination is the same bar as the enumeration.

A plate showing only measurements therefore cannot show that a product is wrong, since the product is not a measurement. It has to be drawn: a fourth bar, computed rather than measured, labelled as the number nothing measures.

That is a departure from this collection’s usual habit, where every quantity on a plate is a measured one. The justification is that the product is the reader’s own arithmetic and the plate’s whole subject is that the arithmetic is wrong — so the wrong number has to be visible or the plate is answering a question nobody asked.

The convention it establishes: a plate about a combination draws the product a reader would compute, labelled as unmeasured. The alternative is a warning in prose beside a plate that agrees with the warning’s opposite.

The one thing that would make them multiply #

There is a version of these two savings that would compose, and describing it makes the subsumption concrete.

Suppose the enumeration returned only the set of present symbols — no intervals, no counts. A search would then know which characters to extend by and would still have to compute each one’s interval, which is a rank walk, which is where the compound walk would apply.

Under that design the two would compose almost exactly: the enumeration removes the dead extensions and the walk makes each surviving one cheaper. The product would be close to right.

The reason it is not the design is that the intervals are free. The descent carries an interval down the tree and splits it at every node, so by the time it reaches a leaf the interval is in hand — throwing it away and recomputing it with a rank walk would be doing the work twice on purpose.

So the subsumption is not an accident of how the operation happens to be implemented. It is a consequence of the operation being implemented well, and an implementation under which the two savings composed would be one that discarded something it had already computed.

That is a general and slightly counterintuitive point: two savings compose when at least one of them is leaving something on the table. A pair that multiplies cleanly may be a pair where the first could have gone further.

What a published pair of results cannot say #

The uncomfortable general point is about how these two results arrived.

Each was measured against the published baseline, correctly, in its own strand. Neither was measured against the other, because neither strand had the other’s structure.

So two correct results, each with a correct factor, produce a wrong answer when combined by the obvious arithmetic — and nothing in either result warns against it.

That is not a failure of either measurement. It is a gap that only a third measurement fills, and the third measurement is nobody’s result: it establishes that one of two existing improvements is redundant with another, which is a negative finding about work already done.

The general instruction is short and it is about reading rather than measuring. Two factors quoted against one baseline may not multiply, and the question to ask is what each removes.

Where else this collection has multiplied #

The habit of multiplying factors is common enough that it is worth asking where else this collection has done it, and the answer is instructive: twice, both times correctly, and both times because the savings were about different quantities.

Three savings in three currencies is the closest case by name and is not the same thing: its three savings are in different units — candidates, comparisons and bits — so they were never multiplied, only reported side by side.

The saving, spent takes a size saving and converts it into a speed improvement by spending it on a denser sampling. That is not a product either; it is an exchange, and the exchange rate is the measurement.

And a factor of fourteen, for four per cent reports one saving against one cost, which is a ratio rather than a composition.

So this is the first pair in this collection where two factors on the same quantity were available to multiply, and the first where the product would have been wrong. That is a small sample and it suggests the trap is rarer than it feels — most improvements to a structure are to different parts of it, and only two savings aimed at the same operation can subsume each other.

Which is also the warning: two savings aimed at the same operation is exactly the situation where a reader is most tempted to multiply, because both are described in the same terms and against the same baseline.

What the strand does with it #

The index built here takes both, and the reason is not that both save.

An index supporting only the enumeration would be slower on exact searches by a factor of 1.90. One supporting only the walk would be slower on branching searches by 78. Supporting both costs nothing — they are two methods on one structure, sharing every array — and lets each query use the one that suits it.

So the answer to “do these compose” is no, and the answer to “should an index have both” is yes, and those are different questions that a product would have conflated.

That is the practical residue of the whole essay: the arithmetic is wrong and the engineering decision is unchanged, which is a comfortable place to land and is not where a reader who had multiplied would have landed. They would have expected a search costing 1,719 ranks and got one costing 18,916, and gone looking for the missing factor of eleven in their implementation.

That last consequence is the practical cost of the wrong arithmetic and it is worth naming, because it is larger than the arithmetic itself. A wrong expectation about a cost does not merely mislead; it sends somebody looking for a bug that is not there. The measured index is correct, its operation count is correct, and the only thing wrong is a number the reader computed.

This collection has an established habit for that shape — an assertion that has never rejected anything proves nothing, so a claim about a cost gets a check — and the check here is on the shortfall rather than on either factor. Both factors were already checked in their own strands and both were right. What needed checking was the thing nobody had written down: that they do not multiply, and by how much they fail to.

A check on a claim nobody made is an odd object and it is the right one here. The claim was going to be made, by any reader with two numbers, and it is the check that makes the essay’s headline something the machinery can defend rather than something the prose asserts.

There is one more thing the shortfall is worth stating in, and it is the form a reader can carry to a structure this collection has not measured. Two savings on one operation compose only when they remove different work. The compound walk removes a second descent per symbol; the enumeration removes the symbols. The second removal contains the first, so the first has nothing left to remove, and the composition is the larger of the two rather than their product. That test — does the later saving still have work of its own to take away — is answerable before any measurement, and it is what the arithmetic here was missing.