The number that would choose a cap

A depth cap is a parameter, and the ladder that introduced it swept it and drew a curve. What no essay in that ladder printed, and what every reader deciding a value would want, is a single histogram of the text’s own depths.

It is one linear pass over the parse the parse in one pass of the text builds. It costs 3.16 operations a character, which over thirty-two thousand characters is a hundred thousand operations and about a fiftieth of a second.

What the histogram says #

Over sixteen copies of a two-thousand-character text: eleven distinct depths, a worst of ten, a mean of 3.98.

Read against the sweep, that settles the parameter immediately. A cap of twelve or more changes nothing at all, because nothing is deeper than ten. A cap of four sits at the mean, so it will bite on roughly half the positions. A cap of one leaves only literals and things copied from literals, which is why it costs 86% of the text in phrases.

Nothing about that reading needs the sweep. The sweep says what each cap costs; the histogram says which caps are live.

Reading the shape rather than the summary #

The mean and the worst are the two numbers usually quoted, and neither is the useful one.

What decides a cap’s cost is the share of positions above it, because those are exactly the positions whose phrases have to be shortened or replaced. At a cap of six, the share above is a few per cent and the parse grows by a third; at a cap of four it is about a quarter and the parse grows by a factor of 2.6.

That relationship is not linear and it is not a curve anybody publishes, because it is a property of one text. What it does mean is that the tail of the histogram is the part to read: a text whose depths pile up at three and trail off to ten behaves quite differently from one spread evenly over the same range, even with the same mean.

Why the two are different questions #

A sweep answers “what does this dial do”. A histogram answers “what is this text like”.

The distinction matters because the sweep’s answer is expensive and collection-specific, and the histogram’s is cheap and transfers. Sweeping ten caps means building ten parses; the histogram is computed from the one parse a phrase index needs anyway.

And the sweep’s shape depends on the histogram. A text whose depths run to twenty-two — which is what the ladder’s own collection produced — has a wide band of caps that do something, and a text whose depths stop at ten has a narrow one. Two sweeps of the same shape at different scales are two histograms.

What one linear pass means #

The histogram is computed by walking the finished parse and assigning each position a depth: zero for a literal, and one more than its source’s for a copied character.

That is one pass over the phrases and one arithmetic operation per character. The parse itself is the expensive part, at about three operations a character — and the parse was needed regardless, because a depth is a property of a parse and there is nothing to measure before one exists.

So the marginal cost of the histogram is close to zero: it is the parse’s own bookkeeping, kept rather than discarded.

A measurement that is a by-product of work already being done should be reported. That is a weak-sounding rule and it is the one this essay is about, because the alternative — recomputing it later, or not having it — is what produces a parameter chosen from a curve.

What a cap is actually buying #

It is worth restating, because the histogram changes what the answer looks like.

Extracting a character at depth d costs d phrase follows. The free parse’s mean depth is 3.98 and its worst is ten, so the typical extraction is already four follows and the cap is buying insurance against the tail.

That reframes the dial. It is not a performance knob — capping at eight moves the mean by very little and costs 6% of the phrases — it is a guarantee, and its price is what a guarantee costs.

A reader who cares about average extraction cost should not be capping at all. A reader who has a bound to meet should cap at their bound and read the price off the sweep. Those are different people and the histogram is what tells them which they are.

The one thing a cap does move on average #

There is a second-order effect worth recording, since the argument above says the mean barely moves.

Capping does not only truncate the tail: it changes which sources are chosen everywhere, because a phrase that would have copied from a deep region copies from a shallower one instead. So the whole distribution shifts down a little, not just its top.

Measured at a cap of eight over the thirty-two-thousand-character collection, the mean falls from 3.98 to about 3.4 — a sixth — for 6% more phrases. That is a genuine improvement in average extraction cost and it is nowhere near the size of the guarantee it comes with, which is what makes “insurance” the right word.

A parameter chosen from a curve #

This collection has an essay about exactly this failure in another field. The threshold somebody chose is about a sort’s cutoff — the size below which a library switches to insertion sort — and its finding is that the published value is a number from a machine nobody has any more, carried forward because nobody re-measured.

A cap chosen by looking at where a sweep’s curve turns is the same shape of decision, and the formula everybody sizes filters with records a third instance of it. The curve’s knee is at four to eight on the collections measured here, and a reader taking eight from that has taken a number about these collections.

The histogram is the thing that transfers. “Cap at the worst acceptable extraction cost, and here is what this text’s depths actually are” is advice; “cap at eight” is a number from somebody else’s data.

It is also worth noticing that a cap is one of three input-dependent parameters this collection has now measured this way. The sampling rate of a compressed index trades locates against bits by a factor of thirty; the block length of a compressed bit vector has an interior optimum; and a depth cap trades phrases against a bound on extraction.

In all three, the sweep is the plate everybody draws and the data’s own distribution is the plate nobody does. A sampling that costs more than the array is the sharpest instance: a sampling rate chosen from a curve rather than from the query mix produces a structure whose samples outweigh what they index.

What the ladder should have printed #

The ladder’s essays each drew a sweep, and the sweep is the right plate for the argument each was making — the trade is monotone, the tightest cap brings back the linear term, the cost is a property of the text.

What none of them drew is the histogram of the collection the sweep was taken on. That is the plate a reader needs in order to know whether the sweep’s shape will hold for them, and it is the cheapest plate in the strand.

A parameter’s plate should show the data as well as the dial. This collection’s convention since the grid strand has been that a cap, a threshold or any input-dependent parameter is drawn as a curve with the parameter along it, and the essay names the measurement that would choose a value. The second half of that convention is what this essay is: the measurement, named and now drawn.

What it costs to have been without it #

It is worth being fair to the ladder here, because “nobody printed the histogram” reads as a criticism and the ladder’s essays are not wrong.

Every conclusion in that ladder is about a dial, and a dial’s behaviour is what a sweep shows. That a tighter cap costs more phrases, that a cap of one brings back the term proportional to the text, that the same cap costs two texts different amounts — all of those are statements about the parameter and all are correctly supported.

What the missing histogram cost is transferability. A reader of those essays learns what a cap does and cannot tell whether their own text’s depths reach the caps being discussed. That is not an error in the essays; it is a gap in what they equip a reader to do, and it is the gap this one fills.

What a quadratic construction was setting is the other half of the same repair: the ladder’s sizes were chosen by its construction’s cost, and its plates were chosen by what its construction could afford to compute.

What the two collections say together #

Two histograms have been measured in this strand, on collections built the same way with different parameters.

Sixteen copies of a two-thousand-character base: depths to ten, mean 3.98. Eight copies of a two-hundred-and-fifty-six-character base: depths to twenty-two.

The second is the smaller collection and has the deeper chains, which is the finding the cap that binds on one text and not another records in a different form: depth measures generations of copying, and a collection of many short copies produces more generations than one of few long ones.

So the parameter that decides a text’s depth profile is not its size and not its repetitiveness. It is how the repetition is arranged — and no summary statistic in this collection captures that. Not the run count, not the phrase count, not the entropy at any order.

Why nobody prints it #

It is worth asking, because the answer is not carelessness.

A depth histogram is not a property of a text. It is a property of a text and a parse of it, and the parse is the expensive object. Before the parse is linear, computing a histogram over anything larger than a few thousand characters is the same two hours the sweep costs — so the measurement that would say which caps are live is exactly as expensive as trying every cap.

That is a real reason and it is now gone. At three operations a character the histogram is available over a collection of any size a reader has, and it is available before deciding anything.

A cheap measurement that used to be expensive is a habit that has to be rebuilt. The instrument changed and the practice has not caught up, which is the shape of most of what this collection files under practice.

What a reader with a real collection should do #

Three steps, and the first two are nearly free.

Parse it and keep the depths. The parse is what a phrase index needs anyway, and the depths are its own bookkeeping. Over a million characters that is about three million operations.

Read the histogram’s tail. The worst depth is the cap above which nothing happens; the share above any candidate cap is what that cap will cost in shortened phrases, approximately and before any second parse.

Then settle whether there is a bound to meet. If extraction cost is a guarantee in somebody’s requirements, cap at it and pay. If it is an average, do not cap: the mean is already four and capping at eight moves it to three and a half for six per cent more phrases.

None of that requires a sweep, and none of it requires the ten parses a sweep costs. The sweep is a plate for an essay; the histogram is an instrument for a decision.

What is checked #

The histogram is one pass, asserted as an operations-per-character figure below twelve — so that a change making it quadratic would fail here rather than quietly making this essay’s argument false.

It has more than three distinct depths, which is the check that it is measuring something rather than reporting a degenerate parse.

And the depths themselves are computed from the finished parse rather than from the construction that produced it, for the reason the whole cap ladder insists on: a construction that both enforces a bound and reports whether it holds is a check of nothing.

The histogram is one suffix sum from being the instrument #

The plate this essay argues for is a histogram, and the quantity it argues is the useful one is the share of positions above a candidate cap. Those are not the same plate, and the second is one suffix sum from the first.

A histogram gives the mass at each depth. The decision needs the mass strictly above each depth, which is the histogram summed from the top down — one pass over eleven numbers. The result is a curve falling monotonically from one to zero, and reading a cap off it is reading a quantile: cap where the tail is as thin as the phrase premium a reader is willing to pay.

That is a better instrument than the histogram for two reasons, and the second is the one that decides how the plate should be drawn.

It is the quantity the cost tracks. The essay’s own numbers say a cap of six leaves a few per cent above it and costs a third more phrases; a cap of four leaves about a quarter above it and costs 2.6 times. Both readings are of the tail rather than of the mode, and a histogram makes a reader do the summing by eye — which is exactly the operation an eye is worst at, because the tail is where the bars are shortest.

And it is comparable across texts. This strand has two collections whose depths reach ten and twenty-two, and their histograms cannot be put on one frame usefully: the horizontal axes differ by a factor of two and the vertical scales are counts of different totals. Their tail curves can. Both run from one to zero, both are read as quantiles, and putting them together shows the thing the essay says and the histograms do not — that similar means sit above very different live bands, because the same quantile lands at a different depth.

That last point is the whole argument for the form. Two texts with a mean of about four and worst depths of ten and twenty-two have the same summary statistic and different answers, and a curve of “share above $d$” against $d$ separates them at a glance while the means do not. It is expected is not average’s standing complaint about a mean, met with the specific replacement rather than a warning — the tail curve is the whole distribution, and the cap is a point on it.

It also connects this essay’s recommendation to the one the practice field eventually arrives at. The cap that would ship sets the cap where the mass above it is a few per cent, and finds nine to twelve across four real collections whose tight-cap costs differ by a factor of seven. That is the quantile reading, applied to real text, and its stability across those four is the evidence that the quantile is what transfers where the depth is not.

So the convention this essay asks for has a second half. Draw the histogram, and draw its tail. The first says what the text is like; the second is the plate a reader points at when choosing a number, and it costs one suffix sum over a dozen integers on top of a measurement that was already free.

The general habit #

There is a rule hiding in this that is worth stating on its own, because it applies well beyond depth caps.

Every input-dependent parameter has a distribution behind it, and the distribution is usually cheaper to measure than the parameter is to sweep.

A sort’s cutoff has a distribution of subproblem sizes behind it. A hash table’s load factor has a distribution of probe lengths. A sketch’s width has a distribution of item frequencies — and the items that survive k counters is the essay where measuring that distribution turned out to decide a structure’s whole behaviour.

In each case the sweep is the plate that gets drawn, because a sweep looks like an experiment and a histogram looks like a description. The sweep is the more expensive of the two and the less useful to a reader with their own data.

What this leaves the strand #

Four essays: a parse in one pass, a sweep at thirty-two times the size, a relaxation measured, and a histogram that costs nothing.

The deferral that opened it asked for a linear-time bounded-depth parse because the quadratic construction was setting every sweep size in the ladder. It got a linear-time parse, a different bounded-depth parse whose difference is measured, and one measurement that nobody had because nobody could afford it.

What it did not get is a cap enforced exactly in linear time, and the cap an automaton cannot see is why: the query a state would have to answer is about a quantity the parse itself produces, which is a dependency rather than a missing structure.