One revision, one level

Take a file’s first revision. Parse it, and measure the deepest chain of copies in it.

Add the second revision, parse the pair, measure again. Then the first three, the first four, and so on to fourteen. Every point is a real file at a real moment in its history, and the collection at each step is a prefix of the collection at the next.

The result is as clean as anything measured here. One more revision, one more level of depth, exactly, nine times in a row.

The increment #

The numbers: one revision alone reaches depth 8. Two reach 10, three 11, four 12, and then 13, 14, 15, 16, 17, 18, 19 — one per generation through the eleventh — and then it stops.

The claim the cap ladder made was depth is generations of copying, and as an increment that is exactly right. A character that survives from revision k to revision k+1 is copied from revision k, so its depth is one more than it was. A passage that survives the whole history collects one level per revision, and the deepest chain in the collection is the oldest surviving passage.

That is a very specific thing to be true, and it is worth pausing on how easily it could have been false. If the parse preferred a recent source over an old one when both were available, the depths would stay flat as the history grew: the longest match would be found in revision k rather than in revision 1, and the chain would be short. If the parse preferred the earliest occurrence — which is what this one does, because a suffix automaton’s state hands back the earliest end position it has seen — the chain runs all the way back.

So the increment is a property of the parse as much as of the history. The parse in one pass of the text is the construction, and the choice of the earliest occurrence is not an optimisation: it is what makes the parse reproducible, and it is what makes depth mean “how long has this survived”.

The offset nobody wrote down #

The other half of the measurement is the part the ladder’s sentence misses, and it is larger than the part it got right for the first several generations.

A single revision already reaches depth 8. One document, no history, nothing copied from anything: eight levels, from the file’s own internal repetition. Two revisions reach 10, not 1 or 2.

So the honest form of the claim is

depth of a k-generation history = k + what one document had on its own

and on this file the second term is 8, on another it is 9, and on twelve unrelated essays with no history at all it is 15. The offset is not a correction; at k = 4 it is twice the term the ladder was about.

That matters for a cap directly. Somebody choosing a cap from the ladder’s sentence would reason: this file has twenty revisions, so set the cap at twenty. The measurement says: set it at twenty plus eight, and the eight is not a property of the history at all — it is a property of the file, and a system that knows how many revisions it holds does not know it.

Where the offset comes from #

It comes from the same place the essays’ depth comes from, which is ordinary repetition.

A file of five thousand characters contains its own boilerplate: the same identifiers, the same indentation, the same three-line pattern repeated. Each of those is a copy of something earlier, and if the earlier thing was itself a copy, the chain lengthens. Nothing in that is a version history; it is what any text does.

The reason the offset is eight rather than three is that repetition compounds. A phrase copied from a phrase copied from a phrase produces depth 3 from three copies of a passage — and a file with a dozen recurring constructions in it, each recurring a dozen times, produces chains of the length measured here without anything unusual happening.

That is the finding the shape of a real history’s depth records, seen from the other end. There, the point was that depth exists without generations. Here, the point is that it is already there at the first generation, so the history’s contribution has to be measured as an increment rather than as a total.

Why the increment is worth having as an equality #

A trend and an equality are different kinds of evidence, and this collection has been careful about the difference before.

A trend — depth grows with generations — is compatible with almost anything: growth that flattens, growth that accelerates, growth with a coefficient of a tenth. It cannot be used to set a parameter, because it does not say what to set it to, and it cannot be refuted by a measurement that is a bit off.

An equality can. Each revision adds exactly one level is refuted by a single generation that adds two, or none, and nine consecutive generations satisfying it is either the mechanism or a coincidence with a probability worth writing down. It also predicts: the twentieth revision of this file will reach depth 27 unless the chain saturates first, which is a claim somebody can check.

That is the same reason measured, not asserted is the first theme in this collection, and the same reason the fits here are refused rather than rounded. A curve that “looks linear” is a description. A curve on which every step is exactly one is a mechanism, and the difference is what makes the offset visible at all — if the increments had been ragged, nobody would have noticed that they started from eight rather than from zero.

What a system would need to know #

There is a practical version of this, because the cap is a parameter something has to set.

To set it from the ladder’s sentence, a system needs the generation count, which it knows: a version-controlled file knows how many revisions it holds. To set it from this page’s equality it needs the generation count and the offset, and the offset is a property of the content that no metadata carries.

The offset is cheap to measure — parse one document, take the worst depth, four milliseconds on a five-thousand-character file — but it has to be measured on something, and the natural candidate is the first revision, which a system indexing a history has in front of it. So the rule is implementable: parse the base, add the number of revisions, cap there.

What it cannot do is generalise across files. Eight here, nine on the second history, fifteen on twelve unrelated essays: the offset is a property of one file’s internal repetition and there is no constant that covers a collection of different things. A system holding many histories would have to measure each, or take the worst, or accept that the cap binds harder on the files with more internal structure — and that last option is the one that costs phrases silently, which is the failure this collection’s cap essays exist to make visible.

What the parse’s own choices contribute #

One more control is worth stating, because “depth” sounds like a property of a text and is a property of a text and a parse.

The parse here is greedy: at each position it takes the longest match available, and among equal matches the earliest source. Both choices push depth up. A parse taking the latest source would find its match in the most recent revision every time, and the chain would be one hop long — depth would be nearly flat in the generations, and the whole ladder would be about nothing.

That alternative is not hypothetical: it is the one a compressor with a sliding window produces, because an old occurrence has fallen out of the window and only the recent one is available. So a version history compressed with a windowed coder has shallow depths and a windowed coder has a worse compression ratio, and the two facts are the same fact.

A parse that will not follow a long chain is the essay that makes the trade explicit by capping the depth directly rather than by shrinking the window. What this page adds is the measurement of what the uncapped, earliest-source parse actually produces on a real history — which is the left-hand end of that trade, and had never been drawn on anything but a model.

What the mean does instead #

The worst depth grows at exactly one a generation. The mean grows at 0.36.

From 3.19 at one revision to 7.92 at fourteen — a rise of 4.73 over thirteen added generations. That gap between 1.00 and 0.36 is the shape of the collection stated as two numbers, and it says something a histogram alone does not.

If every character survived every revision, the mean would grow at 1.00 too: the whole collection would move down one level per generation. It grows at a third of that because most characters do not reach back through the chain. A character in revision 12 is usually copied from revision 11 — the nearest previous occurrence of the passage it belongs to — and only the passages that are stable and old accumulate the full chain.

So the mean rising at 0.36 means roughly a third of the collection at any moment is old, stable text, and the rest is either new or recently touched. That is a statement about how a file is edited, extracted from a parse that knows nothing about editing.

The saturation #

At the twelfth revision the worst depth stops at 19 and does not move again.

That is not the history ending — there are two more revisions in the collection, and the collection keeps growing — and it is not a limit of the parse. It is the oldest passage’s chain ceasing to extend, and there are two ways that happens.

The first is that the passage is edited. A chain from revision 1 to revision 12 breaks the moment somebody rewrites the line it runs through; after that the deepest surviving text is younger.

The second is subtler and is what happens here. A passage that appears in every revision has many previous occurrences, and the parse takes the earliest — so the chain from revision 14 does not run 14 → 13 → 12 → … → 1, one hop per revision. It runs to the earliest occurrence directly, and the depth is set by whichever route the greedy parse actually took at each position. Once the collection contains enough copies, the phrase boundaries stop aligning generation by generation and the chains flatten.

Either way, the practical consequence is the useful one: a long enough history saturates, so a cap set at the saturation depth is free for every future revision as well. That turns a cap from a parameter that has to grow with the collection into a constant, which is exactly the property a system wants from one.

What it costs to get the offset wrong #

Both directions cost, and the plate says how much.

Too tight, which is what the ladder’s sentence produces: cap at the generation count, ignore the offset. On the fourteen-revision history that is a cap of 14 against a worst depth of 19, and it costs 1.7% of the phrase count. Small — because the tail is thin, and cutting the last five levels touches almost nothing.

Much too tight, which is what a reading of the ladder’s sweep produces: the ladder reported a knee at four to eight, so cap at 8. On this collection a cap of 8 costs 68% more phrases, because the mass of the distribution is at 8 and a cap there cuts the collection in half.

Too loose costs nothing in phrases and costs the guarantee: a cap of 24 on this collection is the free parse, and an extraction can follow 19 copies.

The asymmetry is worth stating plainly. Between the peak of the distribution and its tail there is a factor of forty in what the cap costs, and the peak is where a generation-counting rule would put it.

The general shape #

This is the third time in this collection that a quantity has turned out to be a constant plus a term somebody was measuring, and the constant has been the larger one at the sizes anybody runs.

The others: an index’s size is a payload plus an overhead, and the overhead dominates at every size drawn — a range minimum quoted at 2n bits carries 651,800 bits of machinery against 131,072 of payload. And a search’s cost is a number of extensions times a per-extension cost, where the per-extension cost had a σ in it that nobody was counting.

Here the constant is a file’s own repetition and the term is the history. The pattern in all three is the same: a quantity gets its name from the part that grows, and at real sizes the part that does not grow is what gets paid for.

Where this sits #

Four measurements make up what is known here about depth on real text, and they are best read in order.

The shape of a real history’s depth is the histogram: a bell, peaking in the middle, with a thin tail — and the finding that twelve unrelated essays have nearly the same one. This page is the same quantity as a function of the generation count, which is where the increment and the offset separate.

The deepest text is punctuation is the tail, and it is a different object entirely: a run of one repeated character produces one level per character, so the deepest positions in a collection of source files are the dashes in a comment separator rather than anything that was copied.

The cap that would ship is the parameter, set from all three: the knee on real text is at nine to twelve rather than the four to eight the earlier sweep reported, and the reason it is there is the saturation this page measured.

What is left open #

Whether the increment survives a rewrite. This file was edited steadily and never restructured. A history containing one wholesale rewrite should show the chain break — the worst depth falling back towards the offset and climbing again — and that is a shape nothing here has measured, because the two histories available are both incremental.

What the offset is a function of. Eight, nine, fifteen: three files, three offsets, and no model of what predicts them. The obvious candidate is the document’s own repetition measure, and the correlation between a single document’s r or z and its worst depth is a scatter plot over a few dozen files that nothing here draws. The measure that cannot see the alphabet is a reminder that the obvious measure is not always the one that predicts.

And whether saturation is the chain breaking or the parse flattening. Two mechanisms were offered above for why the depth stops at 19, and this page does not separate them. The separation is a measurement: follow the deepest position’s chain at each generation and see whether it still runs to revision 1. That is a few lines against a structure that already exists, and it would say whether a saturated cap is a property of the file or of the parse.

A last note on the instrument #

Every point on this page’s curve is a parse of a real collection, and there are fourteen of them — the first revision, the first two, and so on. Together that is about a million and a half characters parsed.

At the quadratic construction this strand started with, that would have been a measurement nobody would attempt. The parse in one pass of the text made it four seconds, which is the reason the curve exists at all rather than a single point with a sentence attached.

Worth saying because it is the pattern this whole strand keeps producing: the instrument arrived, the ceiling moved, and the questions that had been deferred for cost turned out to be a function call each.