A walk that does not prune

The interval enumeration is one test in a recursion. Descend from the root carrying the interval; split it at each node; enter a child only if its half is non-empty; report a symbol at each leaf.

Remove the condition and the walk visits every node of the tree. It returns exactly the same symbols, with exactly the same intervals, in exactly the same order — because an empty subtree contributes nothing, and a leaf with an empty interval is not reported either way.

Same answer, on every input, always.

The measurement #

An eight-position interval on a twenty-six symbol alphabet.

The pruned walk enters twenty-four nodes and spends thirty-four bit-vector ranks, reporting seven symbols.

The unpruned walk enters fifty-five nodes and spends fifty-four ranks, reporting the same seven symbols with the same intervals.

A factor of 1.59 on the operations and a factor of zero on the answer.

That ratio is small here because the interval holds seven of twenty-six symbols, so a good deal of the tree is on a path to something. On a one-symbol interval the pruned walk enters six nodes and the unpruned one enters fifty-one, which is a factor of eight and a half.

The dependence on the interval is worth drawing out, because it says where the pruning earns its keep.

The unpruned walk’s cost is fixed: 2σ − 1 nodes, whatever the interval holds, because it enters everything. On twenty-six symbols that is fifty-one internal-and-leaf nodes and about fifty-four ranks, at every interval width.

The pruned walk’s cost follows the answer. Six nodes at one symbol, twenty-four at seven, fifty-one at twenty-six.

So the two lines are the same two lines as the descent against the loop, which is not a coincidence and is the subject of a later section. The factor between them is σ/d to within the logarithm, which is eight and a half at one symbol and one at twenty-six.

Why no test of the answer can catch it #

This is the point of the essay and it is worth stating in its strongest form.

The two implementations are extensionally identical. There is no input on which they differ, no output field that distinguishes them, and no property of their results that could be asserted to separate them. A test suite comparing outputs, a property-based test generating random intervals, a formal proof of correctness — none of them can see the difference, because there is no difference to see.

What differs is a number that the answer does not record: how much was spent producing it.

This collection’s habit for that shape is to charge the operations and assert on the charge, and the assertion has to be an equality rather than a bound. A node costs two ranks is the positive half: the ranks a descent spends equal twice the internal nodes it entered, exactly. This is the negative half: a version doing more must be caught by the count.

It is worth putting this in the general category properly, because “an optimisation that does not change the answer” describes almost every optimisation and this is a narrower thing.

Most optimisations change how an answer is computed and can be got wrong: a faster sort can be unstable, a cache can be stale, a bound can prune a live branch. Those are all catchable by a test of the answer, on the right input.

This one cannot be got wrong. There is no input on which the pruned and unpruned walks differ, so there is nothing for a correctness test to find, ever. The pruning is not a risky optimisation whose correctness needs establishing; it is a free one whose presence needs establishing.

That inverts what the check is for. A test suite normally exists to catch an optimisation that broke something. Here it exists to catch an optimisation that is missing.

Why the negative half is necessary #

An equality between a cost and a shape can pass while measuring nothing, if the shape is derived from the same walk as the cost.

The pruned descent returns its node count and its rank count from the same traversal. So a walk that entered twice as many nodes would report twice as many nodes, and twice as many ranks, and the equality would still hold — the check verifies the ratio and not the magnitude.

That is exactly the defect an unpruned walk is: it enters more nodes and spends proportionally more ranks. The equality passes on it.

So the equality check is about the arithmetic identity — two ranks a node rather than four — and it is not about the pruning at all. The pruning needs a check that compares against something outside the walk, and the only thing available is a second implementation.

The shape of the rejection #

The rejection test builds the unpruned walk explicitly — the same recursion with the condition removed — and requires two things.

The answers agree. Same set, same intervals. If they differed the test would be reporting a bug in one of the two rather than the presence of a pruning.

The costs differ, in the right direction. The unpruned walk must cost more. Not merely differently: more.

Both halves are needed. Without the first, a rejection test that happened to break the walk would report a cost difference and call it a demonstration. Without the second, a test could pass on two identical implementations.

The measured result: seven symbols both ways, thirty-four ranks against fifty-four, twenty-four nodes against fifty-five.

What the unpruned walk actually is #

There is a nice way to see what has been lost, and it explains why the two costs converge at one end.

An unpruned descent over a wavelet tree visits every node and computes an interval at each. That is exactly the same amount of work as asking about every symbol — the loop — reorganised. The two are not merely comparable; they are the same computation.

So removing the pruning turns the descent back into the loop, which is the operation it was written to replace. The pruning is the operation. Everything else about the descent — the traversal, the interval splitting, the two-rank identity — is shared with the thing it beats.

That reframes the factor of 1.59 above. On a narrow interval it should be, and is, much larger; on an interval holding every symbol the pruning removes nothing and the two are identical, which is where the descent and the loop are identical too.

Three ways this defect arrives #

It is worth thinking about how a real implementation ends up unpruned, because a defect nobody would write is not worth a check.

Written that way. A person implementing “enumerate the distinct symbols of an interval” from its description writes a recursion over the tree, collects the leaves with non-empty intervals, and returns them. The emptiness test at the leaf is obvious, since a symbol that is not there must not be reported, and and the emptiness test at the internal node is an optimisation that has to be noticed separately. Both produce the right answer and only one is the operation.

Refactored away. A version that tests at the leaves is simpler: one condition instead of two, and the recursion has no early return. A later simplification pass removes the internal test as redundant, correctly notes that the answer does not change, and ships.

Broken by the interval representation. If an empty interval is represented as a pair whose ends happen to be equal and the test is written as a comparison of a stored width, a change in how intervals are constructed can make the width nonzero for an empty range. The test then never fires and the walk is silently unpruned.

The third is the one a check catches that a careful reader would not, and it is the reason the check is on the count rather than in a comment. A comment cannot notice that a comparison stopped being true.

The class of defect #

Collecting what this instance has in common with the others this collection has met.

A quantity computed twice when one determines the other. The rank₀/rank₁ identity: invisible to the answer, visible to the count.

A branch taken that could have been skipped. This one.

A structure held that is never read. An object that keeps an array and promises not to use it has the same size as one that uses it — the defect what the chain cost had to guard against by making the removed structure raise rather than idle.

A cached result that is recomputed. A generator called through a registry rather than through a cache: the same output at a thousand times the cost.

All four are correct programs doing more work than necessary, and none of them can be caught by a test of the output. Three of the four are caught by an operation count and one — the structure held — is caught by making the object unable to answer.

That is the whole toolkit: charge the operations, or make the removed thing genuinely absent rather than merely unused.

The four rejections this strand ships #

The strand carries four rejection tests and they are worth listing together, because each one constructs a plausible defect rather than a broken program.

The unpruned walk. Same answer, more cost. Catches a missing pruning.

An order read off an unordered tree. One set, three orders feeds a running sum a Huffman tree’s leaf order and requires the resulting smaller-counts to be wrong — twenty of twenty-one, worst by 1,798. Catches a caller reading the output in sequence on the wrong shape.

A saving quoted as a product. Two factors that do not multiply computes the product of two measured factors and requires the combined measurement to fall short of it. Catches a claim rather than an implementation.

A size model presented as a structure. A price with no structure under it feeds an accounting and a built object to the same check and requires their operation counts to differ. Catches a number reported as an object.

Four defects, four instruments, and only one of the four is caught by anything a test suite would ordinarily contain. Two are about costs, one is about a caller, and one is about a claim in prose.

That distribution is the argument for this collection’s habit. A gate that only tests answers tests one quarter of what can go wrong with a structure whose subject is its cost.

What an equality check does not cover #

It is worth being honest about the gap this leaves, because the checks in this strand do not close it.

The equality — ranks equal twice the internal nodes — catches a cost that is wrong for the shape.

The rejection — the unpruned walk costs more — demonstrates that the pruning is present and worth something.

Neither catches a shape that is wrong. A descent that visited each node twice, or that recursed on an interval it had already handled, would report a node count and a rank count in the correct two-to-one ratio and would pass both checks.

Catching that needs a bound on the node count itself — k(1 + log₂(σ/k)) ancestors for k leaves — asserted against the alphabet and the answer’s size. This strand asserts the cost against the shape and does not assert the shape against the problem.

Naming the gap is the least that can be done about it, and it is what a check’s own account should include: not only what it catches but what it would let through.

What it would cost a real search #

The census factor of 1.59 is on one interval and understates what a search would pay, so it is worth working the search’s version out.

A backtracking search over a twenty-symbol alphabet at one error spends twenty-four thousand ranks with the enumeration. Unpruned, the enumeration is the loop, so it would spend the loop’s hundred and sixty-eight thousand.

That is a factor of seven, not 1.59, and the difference is that a search lives in narrow intervals. The branches that find nothing is where the search’s intervals are shown to be narrow and a looser budget wastes a larger share is where the budget is shown to narrow them further.

So the honest statement about the pruning’s value is the same statement as the operation’s value, which is what “the pruning is the operation” means. A single number for it would be a number about one interval width, and the range is 1.0 to σ.

Why this is a rejection rather than an assertion #

The strand’s checks come in two kinds and the difference is worth marking, because it is a habit rather than an accident.

An assertion states a property the machinery has and requires it: the ranks equal twice the nodes, the sets agree across shapes, the answers match the loop’s.

A rejection feeds the machinery something defective and requires it to be caught: an unpruned walk, an unordered tree read as sorted, a size model presented as a structure.

The distinction is that an assertion can be satisfied vacuously and a rejection cannot. An assertion about a property nothing ever violates is a comment; a rejection that never rejects is a failure, and this collection’s habit is that each site’s gate ends by feeding its machinery input it must refuse.

The unpruned walk is a good rejection because the input it constructs is plausible. It is not a broken implementation, a corrupted structure or an impossible input; it is what a careful person would write who had not noticed that the test was the point.

Where else the same rejection would apply #

The pattern — remove a test, keep the answer, cost more — is available wherever an operation’s content is a pruning, and this collection has three other places it would apply.

The document listing’s descent. Same operation on a different sequence, so the same rejection works unchanged. The tree answers the question relies on the pruning for its entire cost argument and inherits this check.

A range-minimum walk. The chained document listing prunes a subrange when its minimum is inside the range; removing that test returns the same documents and visits the whole range. Not built as a rejection there, and it would be the same shape.

A backtracking search’s budget test. Cutting a branch that cannot afford its remaining errors is a pruning; removing it returns the same occurrences and explores an exponentially larger tree. That one is caught by a timeout in practice, which is a poor instrument.

The third is worth a note because it is the one where the unpruned version is not merely slower but unusable, and where nobody would ship it by accident. The first two are the dangerous ones: both remove a modest constant factor, both leave the program working, and neither shows up as anything but a machine being slower than expected.

What a reader should take #

Two things, and the second is the general one.

The pruning is the operation. Not an optimisation of it. Remove the emptiness test and the descent is a loop over the alphabet, which is the thing being replaced.

And a defect no output can reveal needs an instrument that is not the output. That instrument is an operation count, and an operation count is only useful if something asserts an exact relationship between it and the structure — because a count nobody checks is a number that drifts, and a bound rather than an equality is a check that lets a doubling through.

There is a third thing, smaller and worth keeping: the rejection has to construct something a person would plausibly write. A test that feeds a structure garbage demonstrates that the structure rejects garbage, which is rarely the failure anybody has. A test that feeds it the version somebody would write on a reasonable reading of the specification demonstrates that the specification’s cost claim is doing work — and that is what a rejection in this collection is for.