What a ceiling costs in phrases

A cap on the copy depth is a dial with a price at every setting, and the price is phrases. A parse that will not follow a long chain builds the construction and states the two ends of the dial; this essay is the curve between them, which turns out to have a shape worth knowing before choosing a setting.

The numbers #

Sixteen copies of five hundred and twelve characters of English-like text — 8,192 characters, and a greedy parse of 156 phrases whose worst chain is 22.

Every row is a complete parse of the same 8,192 characters, and every one of them is a correct index over that text: the capped index produces the collection character for character and finds the same occurrences as exhaustive search at every setting, which is checked before any of these numbers is reported.

Read down the middle column and the shape is unmistakable. From no cap to a cap of eight the phrase count moves by nine per cent; from eight to four it moves by a factor of five and a half; from four to one by a further factor of eight.

Why the curve has an elbow #

Because the depths are distributed, and most of the mass is nowhere near the worst case.

The mean depth of the unbounded parse is 9.89 against a worst of 22. A cap above the bulk of that distribution binds on very few phrases, and every phrase it does not bind on is unchanged — so the parse is nearly the greedy one and the phrase count is nearly the greedy one’s. A cap below the bulk binds on nearly every phrase, and each one it binds on gets shorter, which means more of them, which means more chances for the next one to be bound as well.

That is a general shape rather than a fact about this text. Any constraint applied to a greedy construction is cheap while it binds on the tail and expensive once it reaches the mode, and the position of the mode is what decides where the elbow is. This collection has met the same arithmetic in the depth limit that almost never fires: introsort’s recursion cap costs nothing on ordinary input because ordinary input never reaches it, and the whole question about such a limit is what fraction of the distribution sits above it.

The trade in the units that matter #

Phrases are not the quantity a reader cares about; bits and character costs are, and both are derived from the phrase count.

The size is $z(2\lceil\log_2 n\rceil + \lceil\log_2\sigma\rceil)$ bits for the phrase table plus the boundary orders — linear in $z$, so the size column tracks the phrase column exactly. A cap of eight is 9,350 bits against 8,580; a cap of one is 514,570.

The character cost is the depth, and the measured version of it is well under the cap: extracting 256 characters costs 10 phrase follows each with no cap, 4 at a cap of eight, 2.80 at a cap of four, and 1 at a cap of one. So a cap of eight halves the measured extraction cost for nine per cent more structure.

Both numbers are on the plate because either alone is an advertisement: a size plate makes the cap look like pure cost and an extraction plate makes it look free, and the structure charges both.

Multiplying the two gives a single number, and the product is minimised at a cap of eight on this collection — 9,350 bits times 8 against 8,580 times 22. That is offered as a way of reading the curve rather than as an answer: a product of bits and follows is a choice of exchange rate, which is the thing three savings in three currencies says not to do silently. The curve is the result; the product is one reader’s summary of it.

The elbow moves with the collection, not with the cap #

Holding the cap fixed and growing the collection is the other axis, and it separates what the cap does from what the text does.

Without a cap the worst chain grows with the number of copies — 22 at sixteen copies and 38 at thirty-two, because each copy is parsed as a copy of the one before. The phrase count does not move at all. So the unbounded structure gets steadily worse to read while staying the same size, which is the failure mode the cap exists for and which no size plate can show.

With a cap of eight the chain is eight at every collection size and the phrase count is 170 at sixteen copies and 186 at thirty-two, against 156 — a premium of nine to nineteen per cent, which grows far more slowly than the chain it replaces.

That is the argument for capping at all, and it is an argument about shape rather than about the measured constants. A structure whose read cost grows without bound as its input grows, while its size does not, is a structure that will be unusable at some size and there is no size at which it announces this. Nine per cent to remove that is cheap.

Where the phrases actually come from when a cap binds #

A cap that binds does not simply shorten a phrase. It changes which earlier position the phrase copies from, and the two effects have different sizes.

The greedy rule takes the longest match anywhere earlier. Under a cap the longest match may be unavailable because its source region is too deep, and there are two ways out: take a shorter prefix of that same match, or take a different, shallower source that happens to agree for fewer characters. The construction takes whichever is longer, which is the greedy rule applied to a restricted set.

What that means for the phrase count is that the cap’s cost is not $\lceil D_{\text{free}}/D\rceil$ or any other tidy function of the depths. It is a property of where the shallow regions are in the text, and shallow regions are exactly the early ones — the first copy of a collection is entirely at depth zero and one, the second is at one and two, and so on. So a cap forces later phrases to copy from earlier copies, which are further away and therefore agree for fewer characters.

That is why the cost accelerates rather than scaling. Each tightening pushes the available sources further back, each further-back source gives shorter matches, and shorter matches mean more phrases at every position after them.

What the elbow is worth on other texts #

The same cap on four texts of four thousand characters, as a multiple of the unbounded phrase count:

• a text that repeats itself: 2.96x at a cap of four
• English-like: 1.31x
• four symbols, uniform: 1.28x
• periodic, period 17: 1.11x

A threefold spread from one parameter value, which is why the fourth essay on this ladder is about the direction of it rather than about the size.

Two things this does not buy #

It does not make the index smaller. Every row of the sweep above is larger than the row below it. The cap is bought with size and paid for in read cost, and a reader whose problem is size should not be looking at this dial at all — the dial for size is which measure of repetition the structure is proportional to, which is the collection decides which index is small.

It does not make the search cheaper. The crossing search and the propagation are proportional to $z$ per occurrence under the filtering policy and to $\log z$ under a grid, and both get worse as $z$ grows. So a cap of four, which multiplies $z$ by six, multiplies the filtering policy’s search cost by six as well.

The two ladders therefore pull in opposite directions in the same variable, and a reader building both should read them together. The structure paid for before the first query prices the search structures at $z\lceil\log_2 z\rceil$ bits; a cap of four takes that from 1,248 bits to about 9,460.

What is on the frontier and what is merely on the plate #

Six settings were measured and not all six are worth offering.

A cap of one and a cap of two are on the frontier in the formal sense — nothing dominates them — and neither is a structure anybody would build: at those settings the index is sixty and twenty-two times the size of the uncapped one, which is the subject of the term that came back. They are on the plate because a frontier drawn only over its useful part is a frontier whose shape has been chosen.

That is a convention worth stating rather than a matter of taste. A curve drawn from a cap of four to no cap looks gently sloped and invites a reader to pick the middle; the same curve with its left-hand end included is nearly vertical there, and the shape says what it costs to want a very short chain. Drawing only the region somebody would use is the plotting equivalent of quoting an average over the cases where a method works.

The same rule produced this collection’s plates of the filter that proposes everything and of the sampling that loses: the threshold that reaches zero draws a filter at the point where it stops filtering, because a sweep stopping short of the collapse hides the only part of the arithmetic that does not have to be measured.

What the elbow is not #

It is not an optimum, and the plate does not have one.

A curve with an elbow invites the reading that the elbow is the answer, and it is only the answer under a particular exchange rate between bits and phrase follows. Move the rate and the best point moves: a reader who pays dearly for space wants the loosest cap on the curve, and a reader who pays dearly for a read wants the tightest they can afford.

What the elbow is is the point where the marginal rate changes sharply. To the right of it, a unit of chain costs almost no bits; to the left, it costs a great many. That is genuinely useful and it is a weaker statement than an optimum: it says a reader should be confident about caps to the right of the elbow and should measure before choosing one to its left.

The frontier between time and space makes the same distinction for ten sorts, and the wording there is the wording here: the frontier is the answer to “which of these is defensible”, and the choice among the defensible ones is the reader’s and depends on numbers this collection does not have.

The construction cost, which is the column nobody quotes #

A capped parse is dearer to compute than an uncapped one, and by more than the phrase count grows: on the sixteen-copy collection, 10,857 character comparisons at no cap, 30,093 at eight, 458,460 at four and 2,683,493 at one.

The reason is that the construction is a scan over everything earlier for each phrase, so more phrases is more scans and each scan is over the same text. Two hundred and forty-seven times, between the two ends.

Whether that matters depends on how many times the structure is read, which is the same arithmetic as the rule that pays on a long enough text: a precomputation is amortised against use, and a cost quoted without the number of uses beside it cannot be judged. What is worth saying is that the column exists, that it is the largest ratio in the whole sweep, and that no account of a bounded parse this collection has read mentions it.

Reading the table the way this collection reads a frontier #

The site’s other frontier is the frontier between time and space — comparisons against peak auxiliary space over ten sorts — and the reading rule established there applies unchanged.

A frontier is a refusal to answer. There is no best cap, in the same way there is no best sort, and a plate offering one has smuggled in a weighting. What the curve gives is the set of settings that are not dominated, and it is small: on this collection, caps of 8, 16 and none, plus 4 for a reader who really cannot afford a chain of eight.

A point off the curve is a bug. Every cap here is on the frontier, which is what monotonicity guarantees and what the checks enforce. If a tighter cap ever gave both fewer phrases and a deeper chain, the construction would be choosing against a stale depth.

And the axes have to be the reader’s. Bits and phrase follows are what this structure charges; a plate in “compression ratio” or “phrases per character” would be in units nobody pays.

Choosing a growth factor is the same shape one field over, and it ends the same way: the parameter’s right value is a property of the workload, the curve is what a library can publish, and a default is a guess with a measurement behind it at best.

There is a second knee, and the curve flattens again #

“Flat at one end and vertical at the other” is the shape the plate shows over the range a reader would use, and the table’s own left-hand rows say the curve turns a second time.

Take the ratios between consecutive settings. From no cap to eight: 1.09. Eight to four: 5.56. Four to two: 3.02. Two to one: 2.57. The cost of halving the cap rises to a peak at the eight-to-four step and then falls at every tightening after it.

That is not a measurement artefact and it is not in tension with the acceleration the essay describes; it is what happens when the acceleration runs into a ceiling. A parse cannot have more phrases than the text has characters. At a cap of one the parse is 7,351 phrases over 8,192 characters — 90% of the absolute maximum — so there is almost nothing left to lose, and the last two halvings of the cap are cheap for the same reason the first two are: the constraint has stopped changing anything, at the other end.

So the curve has two knees and the plate draws one of them. The lower knee, at a cap of six to eight, is where the constraint starts binding on the bulk of the distribution. The upper knee, at a cap of about two, is where it has finished binding on all of it and the parse is nearly literals. Between them is the steep stretch, and the steepest single step is the one from eight to four — which is worth knowing, because it is the step immediately below the setting the essay recommends.

The reframing that follows is worth more than the shape. “A cap of one costs 47 times the phrases” reads as a large factor on a small structure, which invites the thought that it might be affordable for a very short chain. Read against the ceiling it says something else: at that setting the parse is within ten per cent of the worst any parse of this text could be, and the index is 514,570 bits against a text of about 41,000 — twelve and a half times the thing it indexes.

At that point the structure has not become expensive; it has stopped being an index in the sense the field uses the word, which is the condition an index larger than what it indexes is named after and the one the term that came back measures from the other side. A reader deciding between caps of four and two is choosing between two settings; a reader considering a cap of one is choosing between a compressed index and a slightly obfuscated copy of the text.

Which suggests the honest form of the plate’s left-hand end. Drawing it is right, for the reason the essay gives — a frontier truncated at the useful part is a frontier whose shape was chosen — and the axis that makes it readable is not the phrase count but the phrase count against $n$. On that axis the tight end saturates visibly at one, the flattening is a feature of the drawing rather than a surprise, and the two knees are both where they are.

What is being claimed #

The trade is flat at the loose end and vertical at the tight one, with an elbow around a cap of six to eight on this collection. Nine per cent of the phrases halves the worst chain; a further factor of two on the chain costs a factor of five and a half.

The elbow is where the depth distribution’s mode is, not where the worst case is, and the two are a factor of two apart.

The measured character cost is about half the cap at every setting, because most positions are shallow.

And the cap moves three quantities and only one of them is drawn on most plates: the size up, the read cost down, and the search cost up along with the size.