The quarter was a lucky number

A growing collection’s document array — the array that names, for every character, the document it belongs to — is best coded by a Huffman code over the documents’ lengths, as the array is the length distribution found, and a collection that grows needs an escape in that code for documents added after the fit. Refitting when the escape is wrong refitted the Huffman code when the share of characters named through the escape passed twice the share its code word stands for, held back until the characters had grown by a quarter since the last refit. Replayed through a source directory’s history, from twenty files to 222 over 47 versions, that clock lost 0.098 bits a symbol against the Huffman code refitted at every version and read 4.52 final arrays’ worth of characters in refits and rebuilds of the escape. Every schedule that refitted when the files doubled did worse.

A price that cannot see the array tried to replace the hold, a fixed quarter, with a price, and failed for two reasons it could separate. Refitting when the bits wasted since the last refit reach a constant times the characters a refit reads puts the array’s size on both sides of the comparison, so the size cancels and what remains is a clock counted in versions; and the rule weighs the refit only against the loss, though waiting is also paid in characters read — at every version without a refit, the escape’s subtree is rebuilt over everything added since the last one. At the hold’s reading the price lost about 0.119 where the hold lost 0.098.

That essay’s closing section proposed charging the choice as it actually is. Refitting now reads the array. Waiting reads the escape’s subtree, at this version and every version until the next refit, and keeps whatever loss the Huffman code in force has that a refit would remove. A rule could add up the waiting’s reading since the last refit, add the removable waste at some exchange rate of characters per bit, and refit once the sum passes the array. The prediction was that the frontier would pass under the held clock, to about 0.09 bits a symbol for 4.3 arrays, and that an escape weighted as half the coding space would stop refitting at every version. It named the early history as the risk: the rebuilds are small while the escape is small, and in the first stretch, where the characters grow by a third in a version, a rule paced by them may wait too long.

Waiting, priced in characters #

The history, the Huffman code and the charges are the earlier pages’. At every version after the first the rule computes two things. The rebuild reading is the characters in documents added since the last refit, which is what rebuilding the escape’s subtree reads. The removable waste is the Huffman code in force’s bits beyond those of the Huffman code a refit would install at that version — the same escape weight, escape included — times the version’s characters. Both are computed from the documents’ lengths alone. The rule keeps a running total of the rebuild reading plus the removable waste times a rate, and refits when the total, with this version’s share added, reaches the version’s characters; then the total starts again from nought.

The rate is in characters per bit. At a rate of nought the rule refits whenever the rebuilds since the last refit have read one whole array, and ignores the loss. At a rate of sixteen a bit of removable waste counts as much as sixteen characters of rebuild. Rates of 0, a quarter, a half, and 1 to 16 doubling were run. The removable waste replaces the earlier price’s loss because the earlier price counted the escape’s own coding space as waste, and a refit does not remove that.

The escape clock’s hold was run as a sweep this time, at holds from nothing to a doubling of the characters, because the earlier essay ran three — nothing, a quarter and a half — and reported the quarter as the clock’s good setting.

Better than the hold, except at the hold’s own point #

Priced with the reading that waiting costs, the rule beats the hold wherever both read more than about five final arrays — 0.080 bits a symbol for 5.04 where the hold’s best gives 0.088, 0.052 for 6.38 against 0.066 — and loses only at the quarter’s own point, 0.098 for 4.52 arrays, where the waiting price gives about 0.147. At its cheap end it reaches 0.034 bits a symbol for 7.90 arrays at a rate of sixteen, where the swept hold gives about 0.052 at the same reading. Against the size-blind price it is better at five arrays and within a few thousandths of it, slightly behind, from six arrays to eight: the two rules agree once refits are frequent, since a rule that refits every two or three versions has little rebuild reading to count.

The prediction was right that the frontier would move under the hold and wrong about where. It expected 0.09 for 4.3 arrays. At 4.29 arrays the waiting price loses 0.213, at a rate of a quarter, and nothing the rule offers reaches the quarter’s corner of the plot. The interesting point on the plate is not the new line at all. It is that the hold’s line, swept, is not a line: its points jump back and forth in reading as the hold rises, and only a few of them survive as undominated. The quarter is one of the survivors, and it sits far below its neighbours.

A quarter among worse neighbours #

The quarter is a lucky setting: held to growth of 1.25 the clock loses 0.098 bits a symbol for 4.52 final arrays, but held to 1.2 it loses 0.112 for 5.35 and held to 1.33 it loses 0.149 for 4.65 — worse on both counts on both sides. A schedule whose loss and reading move in opposite directions as a parameter turns is a trade; one whose neighbours are both worse on both counts is a coincidence of that parameter with something in the data. The sweep shows the second. From a hold of 1.5 upward the clock gets worse on both counts at once again: held to 1.75 it loses 0.464 for 4.28, held to a doubling 0.458 for 5.15, since the rebuilds of an escape left to cover most of the collection outweigh the refits saved.

The earlier essay quoted the quarter’s 0.098 as the clock’s result and drew the frontier between a quarter and a half from two points. Both statements were true of the settings run. What the sweep adds is that the clock’s frontier has no smooth shape for a rule of any kind to approach, so a rule judged against its best point is being judged against the best of ten draws.

Two arrivals that come in pairs #

Either side of a quarter the hold refits at nearly the same versions and misses by one: versions 20–21 and 24–25 each grow the collection twice running — by 7% then 9%, and by 10% then 7% — and held to 1.2 the clock refits at versions 20 and 24, between the two arrivals, where a quarter refits at 21 and 25, after both. The first seven refits are the same under both holds. Then 1.2’s lower threshold is met one version sooner, and its code is fitted to a collection that is about to grow by another 9% or 7%. That code is wrong as soon as it is fitted, the share behind its escape climbs at once, and the clock with 1.2’s hold refits again four versions later, still a version early. The quarter, waiting one version more, fits both halves of each pair.

That is what luck means here. The quarter is not a better rule than 1.2 in any sense a store could know; it is the threshold that, on this history, happens to fall after both halves of two paired arrivals. A history that brought its large changes in single versions, or in threes, would favour a different hold, and one where the pairs were spaced differently would favour another. One doubling late found that the growth already seen predicts the growth to come only one doubling late, because this directory’s growth slowed at every doubling; the same history’s arrivals are lumpy at a finer scale too, and a rule tuned to its lumps is tuned to this history.

The waiting price refits at versions 21 and 25 at a rate of two, after both halves of each pair, without being tuned to them. Its threshold is met by an accumulation rather than a jump, and a pair of arrivals adds to the rebuild reading for two versions before the total crosses.

The early stretch, still #

The waiting price still loses the first stretch — 0.116 bits a symbol in versions 0 to 14, where the hold at a quarter loses 0.073 — and wins the other two, 0.050 against 0.124 in the middle and 0.074 against 0.098 late. The hold of 1.15, which reads about what the waiting price reads, loses 0.066 early and 0.079 late, and is the fairer comparison: at matched reading the price wins the middle stretch by 0.037 and the late one by a few thousandths, and gives back half a tenth of a bit a symbol in the first fifteen versions.

So the risk the proposal named is the one that occurred. Early in the history the escape is small, because it has been only a version or two since the last refit, and the documents behind it are few; the rebuild reading accumulates slowly while the loss per version is large. At a rate of two characters a bit, the removable waste then dominates the total, and the rule behaves like the size-blind price it was meant to correct, counting versions. In the first stretch, where a version can add a third of the characters, that is the wrong unit, and the hold’s unit, growth, is right.

A price that cannot see the array blamed the early loss on the version as the unit of waste. The waiting price inherits that unit for its loss term, and the plate shows it inheriting the failure with it.

What the rule reads #

With the waiting priced, rebuilding the escape never reads more than 2.16 final arrays; at a rate of nought — refit when the rebuilds since the last refit have read one array — the rule refits seven times and its two halves are nearly equal, 2.55 and 2.16, and from a rate of one the refits take over, 3.62 against 1.00. The rate of nought is the rule choosing a growth factor would recognise: a structure that pays as much in upkeep as in rebuilding has balanced its two costs, and the total is within a constant of the cheaper one. The rule loses 0.292 bits a symbol there, because it ignores the loss entirely.

The same balance appears in the hold’s numbers. The hold at a quarter reads 3.52 arrays in refits and 1.00 in rebuilds, nearly the split of the waiting price at a rate of one, 3.62 and 1.00. Neither rule was tuned to that split, and both arrive at it because a refit roughly every quarter’s growth keeps the escape’s subtree small enough that rebuilding it costs about a quarter of what refitting does. The difference between them is entirely when the refits fall: the hold’s are placed by growth, the price’s by an accumulation of rebuilds and waste, and on this history the hold’s are placed better early and worse late.

The rebuild total also explains why the size-blind price could not read under 4.3 arrays however high its constant: it counted none of these characters, and they grew as its refits thinned. A rule that counts them cannot let them grow past the array between refits, by construction, and its reading is bounded by its refits plus at most one array’s worth of rebuilding per refit.

A code that should not be refitted #

Under an escape weighted as half the coding space a refit never removes a bit — the Huffman code in force is as good as the one a refit would install at all 47 versions — so the waiting price refits only to stop rebuilding, seven times for 4.72 arrays, and loses 0.599 bits a symbol where the Huffman code fitted once and never refitted loses 0.384, for 17.04 arrays of rebuilding. That half of the prediction holds: the half-space escape stops refitting at every version, as it did under the size-blind price. But what it shows is stranger than the prediction. A code whose escape takes half the coding space is a two-level code, documents known at the fit in one half and every later document in the other, and the later half is rebuilt at every version as a Huffman code of its own. Refitting moves documents from the later half to the earlier, which gives them nothing, and resets the later half to empty, which wastes its bit. The refits buy reading and cost loss.

So under that weight the trade runs backward. The fewer the refits, the lower the loss and the higher the reading, all the way to a code that is never refitted, and a rule that prices waiting can only choose a point on that trade by its exchange rate. A code word is at least one bit is the reason the half-space escape cannot be made cheaper in return: its own code word is already one bit, and an escape that hedges cannot be wrong in the direction a refit corrects.

What the history decides #

Paired arrivals. The quarter’s advantage is two pairs of versions, and nothing here says how common such pairs are in directory histories. Another history would place the hold’s lucky points elsewhere. The sweep of holds is the measurement that matters, and it was run on one history.

One unit of waste. The loss term still counts each version once. The early stretch is lost because of it, and a rule whose loss term counted characters arriving rather than versions elapsing was not run here.

Rates on a doubling grid. Eight exchange rates. The waiting price’s frontier between rates of one and two is read through two points, and its loss at the quarter’s reading is read off the line between rates of a quarter and one.

Reading, not time. Every cost here is characters read. A store whose refits run in the background and whose rebuilds run on the query path would weigh the two differently, and the rate would then have a price outside the history.

The shape arrived early and the bytes late and the collections the saving was quoted for both found that a document array’s numbers are numbers about one collection. The schedules that keep it compressed turn out to be the same: a threshold that looks like a result can be a coincidence with the history’s lumps, and only a sweep says which.

Still open: waste counted by what arrived #

The waiting price loses only the first stretch, and loses it for the reason the size-blind price lost it: its loss term adds the removable waste once a version, so a version that changed nothing counts as much as one that added a third of the collection. The hold is right early because it counts growth. A rule could count both of its costs by what arrived: the rebuild reading is already counted in characters added, and the removable waste could be charged per character that arrived since the last refit — the loss a symbol times the characters added at that version — rather than per character stored.

The measurement that follows charges the waste that way, keeps the rebuild reading and the exchange rate, and sweeps the rate as here, on the same history and the same three weights. The prediction is that the first stretch’s loss falls from 0.116 to under 0.08 at about the same reading, because a version that adds a third of the characters then counts for a third of an array of waste, and that the middle and late stretches change little, since growth there is slower and steadier. It could fail on the quiet versions: versions 18 and 19 add nothing, and a rule charged by arrivals will let a stale code serve them for free, which is right for the rule and wrong if those versions are stored as long as any other. The question is whether the loss a stale code causes belongs to the characters that made it stale or to the characters it is asked to code — and whether a schedule can be judged on one history when its best threshold is the one that happens to land after a pair.