The cap that would ship

The cap on a parse’s depth is a parameter, and a parameter has to be set to a number.

The number that would choose a cap is the essay that asked what that number should be, and answered it from a sweep over a generated collection: the knee is at four to eight, and a cap of one costs 86% of the text in phrases.

Every real collection here disagrees.

The measurement #

Same sweep, same quantity, same construction: for each cap, parse the collection with sources deeper than the cap forbidden, and report the phrase count as a multiple of the free parse’s.

The knees, at the five-per-cent threshold: ten on the ten-revision history, twelve on the fourteen-revision one, nine on the essays, twelve on the source code, and ten on the generated collection re-measured at the same size.

So the published four-to-eight was not a property of the generator either. It was a property of the generator at the size the quadratic construction could reach — a few thousand characters — and the same model at a hundred thousand characters has a knee at ten. Two things moved: the collection became real, and the collection became large enough to measure.

What a tight cap costs on real text #

The other end of the sweep is where the two disagree most.

A cap of one — every phrase copies from a literal, nothing chains — costs 24.5 times the free parse’s phrase count on the ten-revision history and 48.1 times on the fourteen-revision one, against 21.4 on the generated collection and 6.4 on the essays.

That spread is the finding. A cap of one is a factor of six on unrelated prose and a factor of fifty on a version history, because a version history is made of chains: every character that survived a revision is copied from the revision before, and forbidding chains means re-encoding all of it as fresh matches.

At a cap of four the gap is 2.75. At a cap of two it is 2.89. At a cap of eight it has closed to 1.35, and by twelve both are at the free parse. So the model is a good approximation exactly where the cap is loose enough not to matter, and wrong by a factor of three where the parameter is interesting.

Why the knee is where it is #

The histogram says it, and this is the payoff for having drawn one.

The shape of a real history’s depth shows a bell: mean depth 5.71 on the ten-revision history, peak at 6, worst 14. A cap at D truncates everything deeper than D, so the cost of a cap is roughly the share of the collection above it — and the share above the peak is half the collection.

That places the knee just past the point where the tail becomes thin, which on a bell is a little above the mean and well below the worst. Measured: mean 5.71, knee 10, worst 14.

And one revision, one level says where the worst comes from: the generation count plus the file’s own offset, saturating once the oldest surviving passage stops deepening. So the knee is predictable from two numbers a system can measure — the depth of one document, and how many revisions it holds.

What to actually set #

For a system indexing a version history, the recommendation from these measurements is:

Cap at the generation count plus the base document’s worst depth, which is the saturation point, and costs nothing measurable. On the fourteen-revision file that is 19, and a cap of 24 is the free parse exactly.

If a tighter bound is needed, twelve is the cheap one. It costs 1.7% of the phrase count on the worst collection here and 0.4% on the next, and it bounds an extraction at twelve chained lookups rather than nineteen. That is a good trade and it is the number this page would put in a configuration file.

Below eight, expect to pay in tens of per cent, rising to a factor of ten by a cap of four. Anything in that range is buying a much tighter extraction bound at a price that shows up in the index’s size, because the phrase count is the size of a parse-based index — an index with z in its size is the whole reason z is the measure.

What the cap does to the collections that are not histories #

Two of the five lines on the sweep belong to collections with no generational structure at all, and they behave differently enough to be worth a section.

Twelve unrelated essays: a cap of one costs 6.4 times the free parse, a cap of four costs 1.96, a cap of eight costs 1.07. That is a shallow curve, and the reason is the histogram — prose’s depths are a bell too, but a narrower one, with a mean of 5.17 and very little mass past 8. Capping prose is cheap because there is not much down there.

Eight source modules: a cap of one costs 6.6, a cap of four costs 2.07, a cap of eight costs 1.15 — and then the curve does something the others do not. It keeps declining slowly, by a per cent at a time, all the way out to 24. That long flat decline is the run tail being truncated a little at a time, and the deepest text is punctuation is what it is made of.

The practical consequence is that a system indexing documents rather than revisions can cap much more aggressively than one indexing a history. At a cap of six the essays pay 32% and the fourteen-revision history pays 332%. Same parameter, same construction, an order of magnitude apart in cost — because the parameter is bounding a chain and one collection is built of chains.

The trade, in both currencies #

A cap is not free and it is not only a cost, and the plate that makes the decision is the one with both quantities on it.

What a cap buys is a bound on extraction: the number of chained lookups to produce one character. Uncapped, that is the worst depth — 14, 19, 78 depending on the collection. Capped at 12, it is 12, on every collection, whatever the text turns out to contain.

What it costs is phrases, and phrases are bits: a parse-based index stores a record per phrase, so a phrase count 1.7% higher is an index 1.7% larger. At a cap of 4 it is an index six to eleven times larger on a version history, which is not a trade anybody would take.

The shape of that curve is the argument for capping at all. Between a cap of 24 and no cap the size is identical and the guarantee improves; between 12 and 24 the size moves by a per cent and the guarantee halves. Only below eight does the curve turn, and everything to the right of the turn is free improvement.

Why the earlier number was not wrong #

Worth being precise, because “the published number was four to eight and the real one is nine to twelve” reads like an error and is not one.

The earlier sweep was drawn on the collection that could be measured. The parse was quadratic then — the parse in one pass of the text is what removed that — so a sweep over ten caps meant ten parses of a few thousand characters, and a few thousand characters of a generated collection was what a figure could afford. Every number on it is exact about that object.

What changed is not the arithmetic. It is that the object is now available in two other kinds — real, and large — and both of them move the answer. The knee moves from four-to-eight to nine-to-twelve when the collection becomes real; the cost at a tight cap moves by a factor of three when it becomes a chain rather than a star.

That is the pattern this whole strand keeps producing, and it is worth naming as a working rule: a parameter recommendation inherits everything about the collection it was measured on, including the things nobody thought were parameters. The size, the shape of the derivation, whether it has runs in it.

The one row that runs the other way #

A sweep with five collections and eleven settings has fifty-five numbers in it, and one of them is worth pulling out because it is the kind of thing that gets tidied away.

At the loosest settings, the source code’s phrase count under a cap of 24 is 1.1% above the free parse, and under a cap of 20 it is 1.4% — monotone, as it must be. But at intermediate caps the ordering between two collections swaps: the essays are more expensive than the source code below a cap of five, and cheaper above it. Two curves crossing in the middle of the plate.

That crossing is not noise. Prose has more mass at shallow depths than source code does — a prose document repeats words rather than lines — so a very tight cap hurts it more; source code has the run tail, so a loose cap hurts it longer. The two effects put the crossing at about a cap of five, and it is visible on the sweep as the point where two lines exchange places.

It matters because a recommendation phrased as “prose caps more cheaply than code” would be true on one side of five and false on the other. This collection’s rule about that is a limit is not a prediction: a comparison between two curves is a comparison at a point, and the point has to be stated.

What a system should measure for itself #

The whole recommendation above is four numbers, and the honest advice is to measure them rather than take them.

Parse the collection once uncapped: that gives the free phrase count and the worst depth, in linear time. Parse it at two or three candidate caps: that gives the cost curve near the knee. Four parses of a hundred thousand characters is under a second here, and it produces a curve specific to the collection rather than to somebody else’s.

The reason to bother is the spread on the plate. Between the essays and the fourteen-revision history, at a cap of four, the cost differs by a factor of 5.6 — and both are real collections of real text of the same size. There is no single number, and there is not even a single number per kind of collection: the two version histories differ from each other by a factor of two at the same cap.

What generalises is the shape, not the setting. The curve is steep below the mean depth, has a knee a little above it, and is flat past the worst — and that is a statement a system can act on by measuring two numbers, which is cheaper than trusting one.

What the cap does not bound #

One more thing belongs in a recommendation, because a bound that is quoted for the wrong operation is worse than none.

The cap bounds the number of chained copies an extraction follows. It does not bound the work: following a copy means a lookup in whatever structure holds the phrases, and that lookup is a predecessor query or a grid search, costing its own logarithm. The character that costs a chain makes the distinction and this page inherits it — a cap of twelve promises twelve lookups, not twelve memory accesses.

It also does not bound the length of what is copied. A phrase of ten thousand characters at depth 3 is three hops for the first character and three hops for the last, but producing the whole phrase means copying ten thousand characters. Extraction of a substring is bounded by its length plus its depth, and only the second term is what the cap touches.

And it says nothing about the search that finds the occurrences in the first place. A parse-based index answers “where does this occur” through machinery the cap does not enter — an index with z in its size has a grid in it, and the grid’s cost is a function of the phrase count, which the cap makes larger. That is the second-order cost of a tight cap and nothing here measures it: more phrases means a bigger grid, and a bigger grid means slower queries, so a cap chosen for extraction is paid for at query time as well as in bits.

Which is the honest closing note. The recommendation above — twelve, or the saturation depth, measured per collection — is a recommendation about one axis of a structure with three, and the other two are named here and not swept.

The knee transfers and the cost below it does not #

Two spreads on this page point in opposite directions, and setting them beside each other says which of the numbers here is safe to reuse.

The knees are nine, ten, twelve and twelve across four real collections — a spread of 1.33. The cost of a cap of one on the same four is 6.4, 6.6, 24.5 and 48.1 — a spread of 7.5. The parameter is stable across collections that differ by a factor of seven in what ignoring it costs.

That is not a coincidence of these four. The knee is a property of where a depth histogram’s tail thins out, and every real collection measured here has a bell with a mean between 5.2 and 5.7 — prose, source code and two version histories, all landing in a 0.5-wide window. The cost at a tight cap is a property of something else entirely: how much of the collection is chained, which is a fact about how the documents were derived and differs by construction between a version history and a pile of unrelated files.

So the two numbers have different domains. Nine to twelve is a statement about the shape of depth in real text and travels; “a cap of four costs eleven times the free parse” is a statement about a fourteen-revision history and travels nowhere.

Which suggests a cheaper instruction than the one this page gives. The recommendation above is to parse once uncapped and twice near the candidate caps — four parses. But the knee is a quantile of the depth histogram, and the uncapped parse already produces the histogram: cap where the mass above the cap is a few per cent, and the four collections here return nine, ten, twelve and twelve without a single capped parse being run.

That reduces the whole procedure to one pass, and it makes the recommendation portable in the right way. A system reports its own histogram’s high percentile rather than borrowing a number, gets the same answer this page got where the collection resembles these, and gets a different and correct answer where it does not — a collection of documents with no repetition at all would have a histogram concentrated near zero and a knee to match, and no sweep would be needed to discover it.

The one calibration worth doing once is which percentile. The cost at a cap is the mass above it times what re-encoding that mass costs, and the second factor is small near the knee and large far below it — which is why the cost curve is flat above the knee and steep below. Fixing the percentile that lands on a five-per-cent cost is a measurement, and it is the same measurement on every collection because it is a property of the re-encoding rather than of the text.

None of which changes the earlier caution. A histogram’s high percentile is still a summary of a distribution, and the shape of a real history’s depth is the reason the mean would be the wrong one to take — the mean sits at 5.71 where the useful cap is 10, and a cap at the mean costs half the collection. Expected is not average is the standing form of that, and here it is unusually sharp: the two statistics differ by a factor of two and the cost between them differs by a factor of a hundred.

What a reader building this should keep #

Three numbers and one instruction.

The knee is at nine to twelve on real text, not the four to eight measured on a generated collection at a size the quadratic construction could reach.

A cap of twelve costs 1.7% of the phrase count on the most expensive collection measured here, and bounds an extraction at twelve chained copies rather than at nineteen.

And a cap of four costs between two and eleven times the free parse, depending entirely on whether the collection is a version history or a pile of unrelated documents.

The instruction: parse the collection once uncapped and twice near the candidate caps, which is under a second on a hundred thousand characters, and read the knee off the resulting curve. The spread between two real version histories at the same cap is a factor of two, so there is no number this page could give that would be right for a collection it has not seen.