A refit either charge can call

A document array names, for every character of a collection, the document the character belongs to. The array is the length distribution found it best coded by a Huffman code over the documents’ lengths, so that a long document’s name is short. A collection that grows breaks that Huffman code a little with every version: new documents arrive through an escape, which refitting when the escape is wrong introduced, and a Huffman code fitted to an old length distribution goes on charging the new one. A refit reads the whole array and rewrites it. Not refitting costs two things: the bits the stale code wastes, and the escape’s subtree rebuilt at every version over everything added since the last fit.

The strand has been looking for the rule that decides when. A price that cannot see the array charged the choice as it is: refit when the rebuild reading since the last refit, plus the waste a refit would remove times an exchange rate, passes the characters a refit reads. A waste charged to what arrived then changed one multiplication — the waste a symbol times the characters each version adds, instead of times every character stored — and found the two charges drawing nearly one frontier while losing in opposite stretches. On versions 0 to 14, where the directory grows by a third in some versions and not at all in others, the arrivals charge lost 0.073 bits a symbol and the stored charge 0.116. On versions 15 to 29 the stored charge lost 0.051 and the arrivals charge 0.087.

That essay’s reading was that each charge is right about one kind of staleness. Charged on arrivals, the rule fires on a burst, when the Huffman code becomes wrong. Charged on storage, it fires on a wrong code that lasts, when the wrongness becomes expensive. Its closing section proposed listening to both: keep both running sums since the last refit and refit when either passes the array. The prediction was that the combined rule would take the hold’s schedule through version 18 and the stored charge’s afterwards, losing about 0.073, 0.05 and 0.075 over the three stretches and about 0.065 over the whole history at about 5.5 arrays — a hundredth under both single charges. The risk was the reading: a rule that refits whenever either sum fires might refit at the union of two schedules and read six arrays or more.

Two sums, one refit #

The history and everything measured on it are the earlier essays’: 47 versions of a source directory, from twenty files to 222, the array coded by a Huffman code over the files’ lengths with an escape weighted as one document, every version’s loss measured against a code refitted at that version. The cost axis is the bytes read by refits and rebuilds over the history, in units of the final array.

At every version after a refit the rule computes the removable waste a symbol — the Huffman code in force’s bits beyond those of the Huffman code a refit would install now, the escape included — and adds to two sums. The stored sum gains the version’s rebuild reading plus a rate $r_S$ times the waste a symbol times every character stored. The arrived sum gains the same rebuild reading plus a rate $r_A$ times the waste a symbol times the characters the version added. If either sum would pass the version’s characters, the rule refits and both sums start again from nought.

With $r_A$ at nought the arrived sum is the rebuild reading alone, which the stored sum already contains and exceeds, so the pair $(r_S, 0)$ is the stored charge alone, refit for refit; the measurement checks that it is. The same holds the other way round. So one grid of rates — $r_S$ at 0, 0.5, 1, 2, 3, 4, 6 and 8 characters a bit, $r_A$ at 0, 8, 16, 24, 32, 48, 64 and 128 — holds the two single charges as its two edges and 49 pairs between, and every comparison below is made on that one grid, so that a pair cannot look better merely for having been swept more finely.

The pairs’ frontier lies on or under both single charges everywhere, as it must — the singles are on the grid — and under them by a little. At 5.5 arrays it loses 0.067 bits a symbol against the better single charge’s 0.071; at 6.0 arrays, 0.059 against 0.059; at 6.8 arrays, 0.039 against 0.045. The best pair near the prediction’s reading is $r_S = 2$, $r_A = 32$: 0.070 bits a symbol for 5.31 arrays.

So the prediction comes close in the loss and misses in the margin. A hundredth under both single charges was predicted; the frontier is four thousandths under the better one at 5.5 arrays, nothing at 6.0, six thousandths at 6.8. And the arrivals charge’s own frontier on this grid is better than the earlier essay’s at 5.5 arrays, because the grid holds a rate of 48 the earlier sweep did not — 0.077 for 5.27 arrays, cheaper and better than the rate of 32 beside it. Some of what a combined rule might have been credited with was in the single charge all along.

What the second sum buys, reading by reading #

Read as a margin, the gain is small everywhere and absent in places. It is two thousandths at 4.7 arrays, under half a thousandth at 5.1, 5.2 and 6.0 arrays — where the best schedule on the grid is one charge alone — three thousandths at 5.7 and 6.2, and largest at the expensive end, six thousandths at 6.7 arrays, where the pair $(6, 128)$ reaches 0.039 for 6.70 arrays against the stored charge’s 0.046 for 6.47 and the arrivals charge’s 0.045 for 6.80.

Measured against the loss itself the margin is not nothing: a seventh of the loss at 6.7 arrays. Measured against what separates the strand’s rules from each other it is: the quarter’s hold, the rule all of this began from, lost 0.098 for 4.52 arrays, and the waiting price at either charge lost 0.07 to 0.08 around five arrays. The second sum is a refinement of the price, not a different kind of rule.

The stretches #

The pair’s stretches are the prediction’s in two places of three. Over versions 0 to 14 it loses 0.073, the hold’s figure and the arrivals charge’s. Over versions 30 to 46 it loses 0.074, the stored charge’s. Over versions 15 to 29 it loses 0.060 — between the stored charge’s 0.051 and the arrivals charge’s 0.087, and a hundredth above the prediction’s 0.05.

The middle stretch is where the two charges disagree most, and the pair resolves the disagreement by taking neither side. The stored charge alone did well in the middle because it refitted at versions 15 and 21, early in the quiet stretch, before a stale code had been charged on a large array for long; the arrivals charge did badly there because a quiet version adds almost nothing and so charges almost no waste, and a code fitted at 13 lasted to 19. The pair refits at 13 because the arrivals sum calls it, which is the hold’s and the arrivals charge’s refit, and that resets the stored sum to nought — so the stored sum, which alone would have called a refit at 15, starts its count again at 13 and calls one at 17. One refit at 17 in place of two at 15 and 21 is the hundredth the middle stretch did not get.

Which sum calls which refit #

Through version 13 the pair refits exactly where the arrivals charge and the hold do — 0, 2, 3, 6, 9, 11 and 13 — and the prediction’s “through version 18” holds in shape: the next refit, at 17, is the stored sum’s. From version 25 on, the pair refits where the stored charge does — 25, 35, 42 and 45 — save that its last refit is at 45 where the arrivals charge’s is at 46. Of its twelve refits after the first, five are called by the arrivals sum alone, two by the stored sum alone and five by both at once, the both-at-once refits being versions where the two sums happened to pass the array together.

The proposal’s risk was that the union of two schedules would read six arrays or more, and it does not arrive. The pair reads 5.31 arrays, more than the stored charge alone at rate 2 (5.04) and less than the arrivals charge alone at rate 32 (5.49). It is not the union of the two schedules. A refit called by either sum resets both, so each sum starts again at every refit the other calls and fires later than it would have alone; the pair’s thirteen refits are the arrivals charge’s thirteen, rearranged, not its thirteen plus the stored charge’s eleven.

That is what lets the rule listen to both at so little cost, and it is also why it gains so little. Two sums that reset each other mostly agree on when a refit is due, because each refit removes the waste both of them were counting. Where they disagree — the middle stretch, and the expensive end — the gain is the few thousandths the plates show.

Version by version #

The version plate shows what the means average over. The stored charge’s worst version is version 11, at 0.366 bits a symbol: it did not refit at 11, where the arrivals charge and the hold did, and the Huffman code fitted at 9 met a burst of new files. The pair’s worst is version 21, at 0.245, the same version and the same loss as the arrivals charge’s worst — the Huffman code fitted at 17 meeting the next burst at 21, which the stored charge alone had refitted for.

So the pair removes the stored charge’s worst version and inherits the arrivals charge’s. Its peak loss is a third under the stored charge’s, and its mean is under both, but at no version is it better than both of its parents at once by more than four thousandths of a bit; it is seldom worst and seldom best.

Where the strand’s rules now stand #

Laid side by side, the strand’s refit rules form a sequence of single changes, and the pair is the last of them. The shape arrived early and the bytes late showed that a code fitted once loses up to two bits a symbol by the end of the history, so some refitting is necessary. One doubling late refitted on a fixed schedule, every doubling of the files, and found that the escape’s weight was the decision that mattered most. The escape clock refitted when the escape carried too much, and needed a hold; the quarter was a lucky number found that the hold’s best value moved with the history and that the quarter had been a good guess rather than a principle. The waiting price replaced the hold with an exchange rate between reading and waste. The arrivals charge changed what the waste is multiplied by. The pair keeps both multiplications.

Each step changed the loss at about five arrays by less than the step before. The clock with its hold reached 0.098 bits a symbol at 4.52 arrays; the waiting price about 0.08 at five; the pair 0.070 at 5.31. Measured at about five arrays, the two steps gained about a fifth and then about an eighth, and the second sum gains a twentieth at 5.5 arrays and nothing at six. That is the shape of a strand approaching the best a schedule of refits can do on this history with this escape, and the next rule worth measuring is not obviously a further refinement of the price. What would move the frontier more is the escape — the word a new document arrives through — which every rule since the first has held at the weight of one document.

What a rule can know #

The essay before asked whether a refit rule can know both why a code went stale and what its staleness costs, or whether every schedule on a bursty history must choose which of the two it is late for.

The plates say a rule can know both, cheaply, and that knowing both is worth little on this history. Knowing why — a burst of arrivals — and knowing how much — a stale code over a large array — are two readings of the same waste a symbol, multiplied by two different counts of characters, and on a history where most large arrivals come into an already large array the two counts rise together. They part only on quiet versions, where storage is large and arrivals are small, and on burst versions after a long quiet, where arrivals are large and the stored sum has been accumulating for a while. Those are the versions where the pair differs from either single charge, and they are a minority of the 47.

A refit priced before it is made and a refit that changes one landmark asked the same question of landmark placements for graph search, and met the same economy there: a rebuild is worth its price only once a cost that accumulates has passed it, and the hard part is choosing which accumulating cost to count. Here two candidates for that cost mostly agree, and what they disagree about is a few versions, and which few depends on the history.

What one history cannot settle #

One history. Every number is from one directory’s 47 versions. A history with long quiet stretches and rare large bursts would separate the two sums more often than this one does and give the pair more to gain; one that grows steadily would give it less.

One grid. The rates are eight a charge, sixty-four pairs. A finer grid would find pairs a little better and singles a little better too, as the rate of 48 on the arrivals charge already showed; the margins here are margins on this grid.

One escape. The escape is weighted as one document. Under the half-space escape a refit removes no waste, as the earlier essays found, and both sums are the rebuild reading alone, so the pair is the single rule.

Means over versions. Every loss is averaged over versions. A store that weighted recent versions more would price the late stretch, where the pair follows the stored charge, above the early one.

Still open: a rate that reads the history #

The pair keeps two rates fixed for the whole history, and the stretch plate shows each charge wanting a different rate at different times: the arrivals charge’s 32 is right early and too slow in the quiet middle, the stored charge’s 2 is too eager early and right late. Both rates are exchange rates between characters read and bits wasted, and nothing in the rule requires them to be constant.

The measurement that follows sets a single stored charge’s rate from what the history has done since the last refit — the share of the characters stored that arrived in that interval — scaling the rate down when arrivals have been a large share, so that a burst raises the bar a stale code must clear, and up when they have been small. The prediction is that one charge with a rate that reads the history reaches the pair’s 0.070 at 5.3 arrays and its first stretch, 0.073, while refitting at version 15 in the middle where the pair waited until 17, bringing the middle stretch to about 0.055. It could fail on the scaling: a rate that falls during a burst refits later during the burst, which is exactly when the earlier essays found the Huffman code becoming wrong. The question is whether the exchange rate between reading and waste is a property of the store, fixed once, or of the history the store has been through.