A waste charged to what arrived

A growing collection’s document array names, for every character, the document it belongs to, and the array is the length distribution found it best coded by a Huffman code over the documents’ lengths. A collection that grows needs an escape in that code for documents added after the fit, and a rule for when to refit. Three essays have now argued about the rule on one history: a source directory replayed from twenty files to 222 over 47 versions, its characters growing from 319 thousand to 6.9 million, with every rule charged two things — the loss its code in force has against a Huffman code refitted at every version, in bits a symbol averaged over the versions, and the characters it reads, in whole-array refits and in rebuilds of the escape’s subtree between them, counted in final arrays.

Refitting when the escape is wrong refitted when the escape’s share of characters passed twice its code word’s share, held back until the characters had grown by a quarter since the last refit: 0.098 bits a symbol for 4.52 arrays. A price that cannot see the array tried to replace the hold with a price and lost, because the array’s size cancelled from both sides. The quarter was a lucky number charged the choice as it is: waiting reads the escape’s subtree at every version, and keeps whatever loss a refit would remove; refit when the waiting’s reading since the last refit, plus that removable waste at an exchange rate of characters per bit, passes the array. That price beat the hold wherever both read more than about five arrays — 0.080 bits a symbol for 5.04 arrays at a rate of two — and showed that the hold’s quarter was one good setting between two worse ones.

It lost one stretch. Over versions 0 to 14, where the directory grows by a third in some versions and by nothing in others, the price lost 0.116 bits a symbol where the hold lost 0.073. Its closing section located the reason in a single multiplication. The removable waste was charged as the loss a symbol times every character stored, so a version that added nothing counted for as much waste as a version that added a third of the collection. The hold counts growth, and early in a history growth is what matters.

The proposal was to charge the waste on what arrived: the loss a symbol a refit would remove, times the characters added at that version, rather than the characters stored. The rebuild reading was already counted in characters added, since the escape’s subtree grows only with new documents, so both halves of the waiting cost would then be paced by arrivals. The prediction was that the first stretch’s loss would fall from 0.116 to under 0.08 at about the same reading, and that the middle and late stretches would change little, their growth being slower and steadier. The named risk was the quiet versions — eighteen and nineteen add nothing — which a rule charged by arrivals will let a stale code serve for free.

The same history, one multiplication changed #

Everything is the earlier essay’s except the charge. The same 47 versions; the Huffman code fitted to the documents’ lengths with the escape weighted as one document; the same rebuild reading at every version without a refit; the same refit condition, waiting cost since the last refit passing the characters stored. The removable waste at a version is still the Huffman code in force’s bits beyond those of the Huffman code a refit would install there, escape included, computed from the lengths alone. It is now multiplied by the characters that version added. A version that adds nothing still rebuilds the escape’s subtree over everything added since the last refit, but it adds no waste at all.

That change alters what the exchange rate means. Charged on storage, a rate of two characters a bit put the price at about five arrays read. Charged on arrivals, the same rate charges a twentieth as much waste or less, since a typical version adds a few per cent of what is stored, and the rule waits far longer. So the rate is swept wider, from nought to 256, and the two rules are compared where their readings agree.

Nearly one frontier #

Charged on the characters that arrived, the waste price draws nearly the frontier it drew charged on every character stored: at 5.5 arrays 0.081 against 0.070 bits a symbol, at 6.0 arrays 0.059 against 0.060, at 6.8 arrays 0.045 against 0.048 — worse at the cheap end, within a hundredth from six arrays up. Over the whole history the change in charge is close to a change in exchange rate. Both rules refit when a running sum passes the array; the arrivals rule’s sum grows more slowly and its rate has to be about twenty times higher to read the same, and having been scaled that way the two schedules fall on nearly one curve.

Nearly is the point. At the cheap end, around five arrays, the arrivals rule is a hundredth of a bit worse, and it is at the cheap end that the earlier essay’s price beat the hold by least. From six arrays up it is slightly better, by two or three thousandths, and at seven arrays it loses 0.042 where the stored rule loses 0.046 and the hold’s best setting near there loses 0.060. The frontier says the change is not a better rule. It says the change moves the loss around inside the history, and the next plate is where it moves.

The stretch it won and the stretch it gave away #

Charged on arrivals, the price’s first stretch falls to 0.073 bits a symbol, the hold’s 0.073, where charged on storage it lost 0.116 — and its middle stretch rises from 0.051 to 0.087: the stretch the stored price won is the one the arrivals price gives away. The first part of the prediction holds, at a reading half an array higher than the stored price’s: the early loss is now exactly the hold’s, to three places, and for a reason the next plate makes plain. The second part fails. The middle stretch was the stored price’s best, a third of the hold’s loss there, and charged on arrivals it gives up most of that advantage; the late stretch moves less, from 0.074 to 0.084.

Each of the three schedules is now best somewhere and worst somewhere. The hold is best early and worst in the middle. The stored price is worst early and best in the middle and late. The arrivals price is the hold early and between the two afterwards. No schedule measured on this history wins every stretch, and the earlier essay’s question — whether a schedule can be judged on one history when its best threshold is the one that happens to land after a pair — is sharper for it: the three rules differ less in their totals than in which part of the history they are good at.

Where each one refits #

Through version 18 the arrivals price refits at exactly the hold’s versions — 0, 2, 3, 6, 9, 11 and 13 — where the stored price refits at 0, 3, 6, 9, 12 and 15; after that the arrivals price refits six more times, the stored price five. Charging the waste on arrivals made the price into the hold for the first eighteen versions. That is the strongest form the first prediction could have taken: the rule did not merely approach the hold’s early loss, it chose the hold’s schedule, because in the early history the hold and the arrivals price are reading the same thing. A quarter’s growth since the last refit and a quarter’s growth’s worth of waste are, early on, the same signal.

They part where the history goes quiet. Between versions 14 and 32 the directory grows in bursts with long pauses: versions 17, 18 and 19 add nothing, 23 adds nothing, and 26 to 28 add a few dozen characters between them. The hold refits at 21 and 25, after bursts. The stored price refits at 15, 21 and 25. The arrivals price refits at 19 — on a version that added nothing, because the escape’s rebuilds still accrue — and then at 22 and 25. The plate shows the difference in where the refits fall; the next shows what that difference costs on the versions between.

What a quiet version costs #

On the ten versions between 13 and 34 that add under a fifth of a per cent, the arrivals price leaves a stale code losing 0.057 bits a symbol on average where the stored price’s code loses 0.030: those versions charge it nothing, and they are stored as long as any other. The risk the proposal named is the one that arrived. Versions 16, 17 and 18 show it most clearly. Version 16 adds 139 thousand characters, enough to make the Huffman code in force 0.223 bits a symbol worse than a refit, and the arrivals price charges that loss on the 139 thousand characters that arrived — not enough to fire. Versions 17 and 18 add nothing, so they add no waste, and the stale Huffman code goes on losing 0.223 bits a symbol on all 2.38 million characters stored, for two more versions, at no charge.

The stored price sees the same versions differently. It refitted at 15 and its code at 16 to 19 loses 0.027; it charges every version for the waste on everything stored, so a stale code standing over a large collection is expensive whether or not anything arrived. The plate also shows the opposite case, which is why the totals stay close: at versions 13 and 14 the arrivals price, having refitted at 13 like the hold, loses 0.022 where the stored price, which waited for 15, loses 0.107. And at 24, a large arrival of 313 thousand characters, the stored price’s code loses 0.274 where the arrivals price’s loses 0.115.

What the plate decides is the question the earlier essay ended on: whether the loss a stale code causes belongs to the characters that made it stale or to the characters it is asked to code. On this measurement it is the second. The mean loss is averaged over versions, each version’s loss is a loss on every character it stores, and a stored character is coded by whatever code is in force when it is read, whenever it arrived. A charge that follows the arrivals measures the cause of the staleness and misses most of its cost.

Twenty times the rate #

To read the same, the arrivals price needs an exchange rate twelve to twenty-four times the stored price’s — about the ratio of the characters stored to those a version adds — and at each reading the two lose within 0.033 bits a symbol of each other. The plate makes the frontier’s resemblance arithmetic. Over this history the characters a version adds are, on a typical version, a few per cent of those stored, and a rule charged on arrivals reaches the same reading when its rate makes up that factor. The ratio is not constant — it grows from twelve at 4.5 arrays to twenty-four at seven — because the collection’s growth slows as it gets larger, so a later version’s arrivals are a smaller share.

That drift is also the shape of the trade. At the cheap end, where the rule refits rarely, a large rate on arrivals behaves like a small rate on storage except on the quiet versions, and the quiet versions are where the history’s long stale stretches are; the arrivals rule is worse there by up to 0.017. At the expensive end, where both refit often, the quiet stretches are short whoever refits, and the arrivals rule’s better timing early in the history shows through: 0.042 against 0.046 at seven arrays. At 4.5 arrays, the cheapest reading compared, the order turns over again: the arrivals rule loses 0.120 where the stored rule loses 0.153, and the hold, which is cheapest of the three there, 0.101.

What the two charges are measuring #

The stored charge is a statement about the present. It says: this Huffman code is wrong by so much a symbol on everything the directory holds now, and every version this lasts costs that much. It is right about the cost and blind to the cause; it cannot tell a code made stale by a large arrival from a code that has been slightly wrong for a long time, and early in the history, when each arrival is a large share of what is stored, it is slow to respond to the first kind because a waste that grows with the whole collection is small while the collection is small.

The arrivals charge is a statement about change. It says: this much new material has come in under a code that does not fit it. It responds to the first kind of staleness immediately, which is why it chooses the hold’s schedule early, and it forgets a stale code as soon as nothing new arrives, which is why it loses in the quiet middle. Choosing a growth factor prices a dynamic array in the same two currencies: what a resize costs is set by what is stored, and when to resize by what arrives. The document array has met the distinction before, in the escape’s weight rather than the refit’s timing: one doubling late weighed the escape by the share of characters that arrived since the previous refit, against the share still to come.

The shape arrived early and the bytes late is the reminder of why this history makes the distinction visible: it found the spread of the files’ sizes set early, 0.88 at 56 files and 0.90 at 222, and a code fitted early still losing badly by the end. A Huffman code depends on more than the spread, and what arrives in bursts is the rest of it. A history that grew evenly would make both charges nearly proportional and both rules nearly the same. The collections the saving was quoted for found that the document array’s saving itself depends on which collection it is measured on, and so, it now appears, does the rule for keeping it.

What one history cannot settle #

One collection. A source directory with bursts of growth and long pauses, refitted against a single code family. A collection that grew steadily would not separate the two charges, and one that shrank as well as grew would charge removals, which this replay never sees.

The escape’s weight. Under the escape weighted as half the coding space a refit removes nothing, as the earlier essay found, so both charges are nought and the rule refits only to stop rebuilding; the arrivals charge changes nothing there. Under an escape weighted by growth the arrivals rule refits less often and loses more — 0.251 bits a symbol for 4.59 arrays at a rate of two, against 0.178 for 6.60 on storage — which the plates above do not show.

Means over versions. Every loss is averaged over versions, so a quiet version counts as much as a busy one. A store that weighted versions by how often they are read would price the quiet middle differently, and if old versions are rarely read, the arrivals charge may be the right one after all.

Still open: a refit called by either charge #

The plates say each charge is right about one kind of staleness. The arrivals charge fires on a burst, which is when the Huffman code becomes wrong; the stored charge fires on a wrong code that lasts, which is when the wrongness becomes expensive. A rule can listen to both. Keep both running sums since the last refit — the rebuilds plus the removable waste on arrivals at one rate, and the rebuilds plus the removable waste on storage at another — and refit when either passes the array.

The measurement that follows sweeps both rates over the same history and keeps the undominated pairs. The prediction is that the combined rule takes the hold’s schedule through version 18 and the stored price’s afterwards, so that its stretches come to about 0.073, 0.05 and 0.075, and its whole-history loss to about 0.065 at about 5.5 arrays — under both single charges by about a hundredth. It could fail on the reading: a rule that refits whenever either sum fires refits at the union of two schedules, and the union of the hold’s early refits and the stored price’s later ones may read six arrays or more. The question is 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.