The ratio that was an implementation

This collection measured two multi-pattern shift rules’ preprocessing and published a number: at 128 patterns the exact rules cost 769,724 primitive steps to build and the published rules cost 18,270, a factor of forty-two that grows with the pattern set.

Both of those numbers were wrong about what they were measuring, in opposite directions, and the corrected ratio is 1.6.

The numerator: a definition where an algorithm was meant #

The table the links already knew is the first correction. The exact good-suffix rule was computed by writing its definition out — a loop over offsets, a loop over patterns, a loop over positions — which costs 757,058 character comparisons at 128 patterns.

The same table is computed from the trie’s failure links in 3,824 steps, and the two agree at every node. So 757,058 was the cost of evaluating a definition, and it was reported as the cost of building the rule.

That is a factor of 198 on its own, and it is the larger of the two errors.

It is worth being precise about what was wrong. The 757,058 was not a mismeasurement — that loop really does perform that many character comparisons, reproducibly, and the figure is checked on every build. What was wrong is the sentence attached to it, which said the exact rules cost that much to build. They cost that much to build the way this collection built them, and the difference between those two statements is the whole essay.

The denominator: a table nobody reads #

The second correction is an accounting error and it is smaller and, in its way, more instructive.

commentzWalter builds the two-dimensional bad-character table $\text{bad}[c][j]$ whenever the rule is anything other than “no shift at all”. The published rule does not consult it: the published shift is $\min(\max(d_1(v), \text{char}(c) - j - 1), d_2(v))$, and $\text{char}$ is the published rule’s own one-dimensional table, computed elsewhere.

So the published rule was charged for a table it never reads. At 128 patterns that table costs 12,666 steps — 69% of the published rule’s reported 18,270 — and once it is built only where it is consulted, the published rule’s precomputation is 5,604.

The bad-character table is precisely the thing the published rule exists to avoid. Charging the published rule for it is charging an algorithm for the work of the algorithm it replaces.

The arithmetic of the correction #

The numerator falls by 85.6 and the denominator by 3.3, so the ratio falls by 26 — and the two corrections push in opposite directions on the interpretation. Fixing the numerator makes the exact rule cheap; fixing the denominator makes the published rule cheaper still, and would have made the original ratio worse.

If only the accounting had been fixed, the published number would have become 137 rather than 42. That is worth stating because it is the version this collection would have arrived at by auditing its own accounting without building anything, and it would have been a stronger wrong conclusion.

What the corrected number says #

The exact rules cost 1.6 times the published rules to build, at 128 patterns, and the multiple is flat across the sweep: 2.35, 1.83, 1.67, 1.56, 1.53, 1.53, 1.55, 1.60 at one to 128 patterns.

That is a completely different statement from the one published. “Forty-two times and climbing” says the exact rules are unbuildable at any realistic set size; “1.6 times, flat” says they cost half again as much and the choice between them is decided by something else. What that something else is — precomputation plus scan against the length of the text — is the next essay.

How the error happened, which is the generalisable part #

Three separate things went wrong and each is a shape rather than a slip.

A definition was implemented as a definition. The exact rule was built to be a reference — the thing the published rule is checked against — and a reference is written in the form that is obviously correct rather than the form that is fast. That is the right way to write a reference. The mistake was measuring it and reporting the measurement as a property of the rule.

The unit was inherited. The comparison was between two implementations that already existed, and the quantity compared was the one both of them happened to count. Nobody chose “primitive steps of whatever each construction does” as the unit; it was what the code was already reporting. The count somebody chose is this collection’s essay about an algorithm’s own accounting, and this is the same failure applied to a comparison.

And a cost was attributed by the code’s structure rather than by the algorithm’s. The bad-character table was built inside commentzWalter under a condition about the rule name, and the rule name is not the same thing as the set of tables the rule reads. A reader auditing the algorithm would see that the published shift function does not mention bad; a reader auditing the accounting would see precomputeWork += … inside a branch that runs.

Why the accounting error survived #

The bad-character table was built for every rule but “none”, and the condition was a string comparison against a rule name. Nothing about that is subtle, and it sat in a file that had just been worked on at length.

It survived because nothing that read the number had a reason to doubt it. The plate that draws precomputation draws whatever precomputeWork says; the assertion that the published construction is flat per character was satisfied — 15.7, 15.0, 15.2, 15.6, 15.4, 14.7, 14.7, 14.3 is beautifully flat, because the unused table is itself linear in the pattern set. A wrong number that is wrong by a constant factor passes every check about shape.

That is the general danger with derived quantities. A cost attributed to the wrong algorithm is invisible to every check on the cost’s behaviour — its growth, its flatness, its ratio to another cost that shares the error — and visible only to a reading of what the algorithm actually does. There was no measurement that could have caught it; there was a paragraph that could have.

The paragraph that did catch it was written while adding a third construction. Putting a fourth column beside the three forced the question “what is each of these actually building”, and the answer for one of them was “a table it never opens”.

The essays that were wrong, and what has been changed in them #

Four earlier essays here quote numbers that this correction moves, and they have been updated rather than left as a record.

The table that walks every pair is the one most affected — its whole argument is the ratio — and it now carries the corrected denominator, the corrected per-character figures, and a pointer to the construction that overturns its conclusion about linearity. Its central observation survives: the definition really is quadratic in the pattern set, really does cost 769,724 steps at 128 patterns, and really is eighteen times the scan it enables. What does not survive is the sentence that preprocessing “linear in the total pattern length” is true of the published rules and false of the exact ones.

The shift somebody published, what the approximation gives up and the rule that pays on a long enough text each quote the ratio or the crossing it produces, and each has been corrected in place.

The alternative was to leave them and add a note, and it was rejected for the reason this collection generates every figure from a live computation: a number in the prose that no longer matches what the code produces is a number nobody can check. The corrections are small and the essays’ arguments are unchanged; only the constants moved.

The same shape, twice more in the essays beside this one #

The thread this produced is not about shift rules, and the two other instances written alongside it are worth putting beside it.

An intersection done by scanning. The candidates a filter cannot avoid measures a phrase index’s search examining 4,355 candidates for 32 occurrences, because the intersection at its centre was implemented as the definition of an intersection — walk one set, test membership in the other. The published structure answers the same question with a range query, and the difference is the same difference: a definition evaluated against a construction.

A candidate count against an operation count. The operations a candidate count leaves out is the unit failure beside it: two policies compared in a unit that meant different things on each side, giving a hundred-and-thirty-fold saving where the honest figure is 1.8.

Three cases written alongside each other, and they share a cause worth naming. A comparison inherits its terms from whichever side existed first. The first side’s implementation sets the unit, the first side’s accounting sets what is charged, and the second side is measured against a frame nobody chose. The defence is to write down, in a sentence, what each number counts before dividing one by the other.

What was right in the original measurement #

Most of it, which is worth saying because a correction essay that implies everything was wrong is its own kind of misreport.

The scans were right and are untouched. The exact rules read between zero and 6.3% fewer characters than the published rules, identical from thirty-two patterns up, and every one of those numbers stands.

The definition’s cost was right. 769,724 steps is what that loop performs, and the per-character figure climbing from 20.7 to 601 is a correct measurement of a quadratic construction.

The shape of the argument was right. Preprocessing is a real cost, it is quoted as negligible in the literature, and putting it beside the scan is the right thing to do. The essay that did it found a genuine eighteen-fold gap between a precomputation and the scan it enables.

What was wrong is one number and what it was a number about.

What the corrected numbers do to the crossing #

The practical consequence of a preprocessing figure is where it crosses a scan, and both corrections move that.

For two patterns of ten characters against four-symbol text: with the definition construction and the corrected accounting, the exact rules’ total — precomputation plus characters read — passes the published rules’ at 32,000 characters of text. With the link construction it passes at 8,000.

The figure this collection published earlier was “past sixteen thousand characters”, computed with the inflated denominator and the definition numerator, and it happened to land between the two corrected answers.

At four patterns the crossing is 4,000 characters with the link construction. At thirty-two patterns there is no crossing at any length, and the reason is not preprocessing at all: from about thirty-two patterns the two rules make identical shift decisions, so the scans are identical and there is nothing for the exact rule’s extra construction to earn back.

That last row is the useful one and it survives every correction. Where the two rules differ at all is on small sets, which is where both are cheap to build; where they are expensive to build they agree.

The gate that now holds it #

Three checks were added and they encode the three lessons.

The two exact constructions must agree at every node and every character, across six pattern-set sizes — 2,180 decisions — so a cheap construction can never diverge silently from the reference.

The link construction must be flat per character of pattern while the definition’s is not, both halves required, so a construction that had stopped building anything would fail.

And the exact rule’s precomputation must be a small multiple of the published rule’s — between one and four — and the definition’s must be at least four times that multiple. The second half is what makes the check about the collapse rather than about the ratio.

What a reader should take from a preprocessing figure #

Three questions, and they are the ones this episode would have answered.

Which tables does the algorithm read? A precomputation cost is a sum over the structures a rule consults, and a code path that builds something is not evidence that a rule consults it. The check is the shift function, not the constructor.

Is the number a construction or a definition? A quantity with a short mathematical statement and no published algorithm is usually implemented as its statement, and the cost of that is a fact about the statement. This collection now has a thread for it, and the shift rules are its worked example.

And is the unit the same on both sides? A character comparison in a nested loop over patterns and a rank operation on a bit vector are both “primitive steps” and are not the same act. Here both constructions were doing comparable work, so the unit was defensible — but nothing had checked, and the sibling failure one ladder over is exactly a comparison in two units.

Counting instead of timing is where this collection’s whole method starts, and its promise is that a count is reproducible where a duration is not. The promise holds. What this essay adds is that a count is reproducible and can still be a count of the wrong thing.

What a correction essay is for #

This collection publishes corrections as essays rather than as errata, and the reason is worth one paragraph since this is the third of them.

An erratum says a number was wrong. An essay can say how it came to be wrong, which is the transferable part — and in this case the how is three separate mechanisms, each of which will produce another wrong number somewhere else if it is not named.

The alternative is worse in a specific way. A collection that quietly fixes its numbers is a collection whose readers cannot tell which of its claims have been revised, and this site’s whole method is that every figure is computed from a live measurement that anybody can re-run. A revised number with no account of the revision is exactly as unverifiable as a number that was never measured.

So the four earlier essays are corrected in place and this one exists, and the pair is the record. The invariant that was wrong for seven years is the same shape from outside — a library’s merge policy, wrong in a documented way, found by a formal check and fixed with the history intact — and the reason that essay is interesting is the account rather than the fix.

What is being claimed #

The published ratio of 42 was measuring a definition against a rule, and 69% of the rule’s charge was a table it does not read.

The corrected ratio is 1.60 at 128 patterns and is flat across the sweep, between 1.53 and 2.35.

The two errors moved it in opposite directions. Correcting the accounting alone would have made the published figure 137; correcting the construction alone would have made it 3.3 times too small.

Four earlier essays have been corrected in place, because a number in prose that no longer matches the code is a number nobody can check.

And the scans are untouched. Nothing here changes a shift decision, a character read, or an occurrence found — which is what makes this a correction to an account of two rules rather than a change to either of them.

The one-sentence version, for a reader who wants to carry something away: what a definition costs to evaluate is not what the thing it defines costs to compute, and a comparison inherits its units from whichever side was built first.

One arithmetic consequence is worth adding, because it says something about partial corrections in general.

The two errors did not merely move the ratio in opposite directions — they very nearly cancelled. The published 42 is off by 26 times; correcting the accounting alone gives 137, off by 86; correcting the construction alone gives about 13, off by eight. Only one of the three intermediate positions is worse than doing nothing, and it is the cheaper of the two fixes.

So a reader who had spotted the accounting error and not the construction one would have published a number three times further from the truth than the one they replaced, with a correction notice attached. The table the links already knew is the other half, and the pair is the argument for finding both before amending either.