What a quadratic construction was setting

The ladder about depth caps was measured on collections of about two thousand characters. Nothing in it says why, and nothing in it claims two thousand is the right size at which to study a cap. It is the size the quadratic construction allowed.

With the parse now linear, the same sweep runs at 65,536 characters in three seconds. This essay is which of the ladder’s conclusions hold there.

What a cap is #

A parse that will not follow a long chain built it, and what a ceiling costs in phrases priced it. A phrase’s depth is how many generations of copying separate it from a literal, and reading a character at depth d means following d phrases to produce it. A cap restricts a phrase to sources whose whole region is shallower than the cap, which bounds what any character costs to extract.

The cap is a dial and the ladder swept it. What it costs is phrases, and what it buys is a bounded read.

The headline, at both sizes #

The ladder’s sharpest number was that a cap of one costs 90% of the text: at 8,192 characters, 7,351 phrases where the free parse used 156. That is the term proportional to the text — the one the whole phrase-index family exists to remove — coming back.

At 65,536 characters the same cap gives 56,462 phrases against a free parse’s 2,179: a factor of 25.9, and 86% of the text.

So the conclusion holds and the number moves a little. 90% became 86%, because a longer collection has more repetition to exploit at every depth and the free parse is proportionally smaller. The shape is identical.

The reason the share falls is worth spelling out, because it is the one place the two collections genuinely differ rather than merely being different sizes.

At a cap of one, no phrase may copy from a region that is itself copied — so every phrase’s source must be a literal or a region produced from literals. On a collection of copies, the first copy is the only thing that qualifies, and a phrase can be at most as long as a matching stretch of it. The longer the base text, the longer those stretches, so the more of the collection a cap of one can still cover with copies rather than literals.

Sixteen copies of 4,096 characters therefore does better at cap one than eight copies of 1,024, and the 86% against 90% is that difference.

Where the cap stops binding #

The free parse’s deepest position is fourteen. Above a cap of fourteen nothing changes, and at twelve the cost is four tenths of one per cent.

That number could not be obtained from the ladder’s collection, because its free parse’s worst depth was twenty-two and its collection was a thirty-second of the size. A deeper chain on a smaller collection is not a paradox: depth counts generations of copying, and a collection of eight copies of a short base text produces longer chains than sixteen copies of a long one, because each copy is short enough to be produced almost entirely from the copy before it.

Depth is a property of how the text was built, not of how much of it there is. The ladder said so and could only show it by comparing two texts; this shows it by comparing two sizes of the same construction.

What is not fourteen anywhere #

It is worth putting the free parse’s depth beside the thing it is often confused with.

A collection of sixteen copies has, in an informal sense, sixteen “generations”: copy sixteen resembles copy fifteen resembles copy fourteen. If the parse followed that chain naively, depth would be about sixteen and every character in the last copy would cost sixteen follows.

It does not. The greedy rule takes the longest match, and the longest match for a stretch of copy sixteen is often in copy one — because the copies differ from the base in different places, so a stretch that is unedited in copies one and sixteen matches directly. Depth therefore tracks how the edits interleave rather than the copy number, and fourteen against sixteen copies is close only by coincidence.

That is the same distinction the cap that binds on one text and not another draws between repetition and generations of copying, and it is why the depth histogram is a measurement rather than a parameter.

The knee, which is the number a reader wants #

Between a cap of six and a cap of eight the cost falls from 33% over the free parse to 6%. Between eight and twelve it falls to 0.4%.

So the useful reading of the sweep is that the interesting range is four to eight, and outside it the dial does nothing worth having: below four the cost explodes, above eight there is nothing left to buy.

The ladder said the same, at its own size, with its knee between four and eight as well. That is the most reassuring result here, because the knee is the only part of the sweep a reader would act on.

What thirty-two times the size did not change #

Four conclusions from the ladder, all of them holding.

The trade is monotone in both directions. A tighter cap costs more phrases and bounds reads more tightly, at every step, with no crossings.

A cap of one is nearly one phrase per character. 86% here, 90% there.

The cap’s cost is a property of the text, and in the opposite direction to the guess: a periodic text — the one that looks like nothing but chains — pays little for a cap, and an internally repetitive one pays a lot, because depth measures generations of copying rather than repetition. The cap that binds on one text and not another is that finding, and it is unchanged at this size.

And a capped index is still an index. It produces its text and finds its occurrences, which is checked at every cap.

Why the ladder could not see fourteen #

The ladder’s collection had a free parse whose worst depth was twenty-two. This one’s is fourteen. Both are correct, and the difference is entirely in the collections.

A collection of eight copies of a 256-character base text produces long chains: copy two is produced from copy one, copy three from copy two, and so on, because the greedy rule takes the longest match and the longest match is usually in the immediately preceding copy. Depth then grows nearly with the number of copies.

Sixteen copies of 4,096 characters produces shorter ones, because a base text that long contains internal repetition of its own — so a phrase in copy nine often matches something in copy one directly, at depth one, rather than following the chain.

A cap’s cost is decided by a structure the collection’s parameters do not name, and the two sizes here differ in that structure as well as in size. That is a limitation of this comparison and it is stated rather than tidied away: a strictly controlled experiment would have swept the size at a fixed number of copies, and that experiment is not this one.

What it did change #

One thing, and it is small but worth recording.

The ladder reported a cap of eight at 9% of the phrases over the free parse. Here it is 6.4%. A cap of four cost the ladder a factor of six; here it costs 2.6.

Both directions of that gap have the same cause: a longer collection made of more copies has a shallower depth profile, so a given cap bites less. The ladder’s collection had a worst depth of twenty-two and this one has fourteen, and a cap of four is a much harsher constraint on a text whose chains run to twenty-two.

So the ladder’s numbers are correct and its collection was harder than this one. That is not an error and it is exactly the kind of thing a second size makes visible: a measurement taken at one size on one collection is a measurement about that collection, and its transferability is a question nobody had asked.

The measurement whose size nobody chose #

There is a general point here worth extracting, because this collection will meet it again.

A quadratic construction does not merely make a measurement slow. It decides which measurement is taken, and it does so without anyone noticing. Nobody in the cap ladder decided that two thousand characters was the right size; they chose the size that fitted in a figure, and the size that fitted was the one the construction’s cost allowed.

The consequence is not error — every number in that ladder is correct about its own collection. It is unexamined scope: a conclusion whose range of validity nobody looked at, because looking would have taken two hours a point.

The cheap defence is to say what the collection was and let the reader judge, which the ladder does. The expensive defence is to measure at a second size, which is what this essay is, and it is expensive only because the construction was quadratic.

What the extraction cost looks like at this size #

A cap buys a bound on reading. Extracting a character at depth d follows d phrases, so a cap of four guarantees no character costs more than four follows — and the ladder’s whole argument for capping is that a compressed index with unbounded depth has an unbounded worst-case read.

At the free parse, the worst is fourteen and the mean is 3.98. So the typical read is already cheap and the cap is buying insurance against the tail.

That reframes what the dial is for. It is not a performance knob — the mean barely moves — it is a guarantee, and its price is 6% of the phrases for a worst case of eight or 160% for a worst case of two.

What the linear construction cost to trust #

It is worth saying what had to be true before any of this was worth measuring.

The new construction had to produce the same parse — not a parse of the same size, the same phrases at the same positions with the same lengths. The parse in one pass of the text is the essay about the one ordering that makes that true, and it is checked on four texts of different character before anything here is measured.

Without that check every number in this essay would be about a different parse, and the comparison with the ladder would be a comparison of two constructions rather than of two sizes. The check is cheap and it is the whole foundation of the essay.

What is checked at this size #

Everything the ladder checked, run at the new size and at the new speed.

No position is deeper than its cap — the check the term that came back relies on — verified by walking the parse and computing depths from the phrases rather than from the construction — a construction that both enforces a bound and reports whether it holds is a check of nothing.

The uncapped construction is the greedy parse, phrase for phrase, which is the assertion that makes every comparison here a comparison of like with like.

And the term proportional to the text comes back at the tightest cap — asserted as a required failure of the family’s whole premise, so that a change making a cap of one cheap would fail here rather than quietly removing the ladder’s sharpest finding.

The three sweeps that were never taken #

Beyond re-running the ladder, the linear construction makes three measurements available that nobody could have taken, and it is worth naming them even though only the first is taken here.

The depth histogram over a large collection, which is the measurement that would choose a cap and which the number that would choose a cap is about. One linear pass, 3.16 operations a character over thirty-two thousand.

The cap’s cost against the number of copies, at a fixed base text — which separates “more collection” from “more generations”, and which the two sizes compared above unhelpfully confound. It is a sweep of ten points, each now three seconds, and it is a deferral rather than a result.

And the cap against a real corpus, which is a different question again and which the strand after this one opens. Every collection here is copies of a generated text with a fraction of its characters replaced, and whether a version history’s depth profile looks anything like that is not a question this strand can answer.

The mean is stable and the maximum is not #

Two quantities have been quoted about depth and only one of them has been treated as a measurement. The maximum moved from twenty-two to fourteen between the two collections, which is the confound this essay flags. The mean is 3.98 here, and the ladder’s own histogram sits in the same neighbourhood.

That pairing is worth taking seriously, because a statistic that is stable across two collections which differ in every parameter is a statistic about the method rather than about the collection. The greedy rule takes the longest match, the longest match is usually found in an early copy rather than the immediately preceding one, and the typical position is therefore three or four follows from a literal whatever the collection’s shape.

The maximum is the opposite: it is an extreme over tens of thousands of positions, so it is decided by the rarest arrangement in the collection rather than by the typical one, and it moves with the base length and the copy count in opposite directions. A long base text gives phrases somewhere to match directly and pushes the maximum down; more copies give the chains somewhere to run and push it up. The two collections moved both parameters at once, and in the directions that fight, which is exactly why the confound is total rather than partial.

So the cap is being sized against the least stable number in the measurement, and there is a better one available now that the histogram is affordable.

Choose the cap from a percentile of the depth distribution rather than from its maximum. Capping at the 99th percentile means that one position in a hundred is forced to become a literal or to copy from a shallower source, which costs a phrase each and is a bounded, computable price — and it converts the sizing question from how deep does this collection go into how much of the tail is worth paying to remove, which is a question with a stable answer.

Both the numbers that decision needs are one linear pass away. The mean says what a reader typically pays and the percentile says where the tail starts, and the maximum — the number the ladder could not obtain and this essay reports as fourteen — turns out to be the one that matters least.

What a reader should carry #

The ladder’s conclusions are sound at both sizes measured, and one of its numbers moved by a third.

That is a good outcome and it is not a strong one. Two sizes is two sizes: it says the conclusions are not artefacts of a particular collection, and it says nothing about what happens at a million characters, where a real corpus lives and where nothing in this collection has ever measured.

A corpus that was not generated is where that question goes next, and it changes the ground under all of this — because every collection in this strand, at both sizes, is copies of a generated text with a fraction of its characters replaced, and that is a model rather than a corpus.