A price that cannot see the array

Refitting when the escape is wrong found a good clock for a growing document array. The array names, for every character of a collection, the document it belongs to, and the array is the length distribution showed that its best code is a Huffman code over the documents’ lengths. A collection that grows needs a way to name documents added after that code was fitted, and the Huffman code carries one: an escape, a code word meaning “a document added since the fit”, followed by a small code over the added documents. The escape’s code word is $\ell$ bits long and so stands for a share $2^{-\ell}$ of the characters. When the share actually named through it passes twice that, the escape’s code word is wrong by a bit. A clock that refits at that moment, held back until the collection’s characters have grown by a quarter since the last refit, replayed through a source directory’s history from twenty files to 222 over 47 versions, lost 0.098 bits a symbol against the Huffman code refitted at every version, and read 4.52 final arrays’ worth of characters doing it. Every schedule that refitted when the files doubled did worse on both counts.

The hold was the part that made the clock work, and it was a fixed number: a quarter of the characters. That essay’s closing section noticed what was arbitrary about it. Early in the history a refit reads a small array and a quarter’s growth is a version or two; late, a refit reads an array twenty times the size and a quarter’s growth takes many versions. A hold could instead be set by price. What a refit costs is the characters it reads, which is the array’s current size. What it removes is the loss: the bits a symbol the stale code wastes, times the characters coded with it. A clock could refit when the waste accumulated since the last refit, in bits, passes the characters a refit would read, times a constant. The proposal predicted it would land at least as well as the best fixed hold, at about 0.08 bits a symbol for 4.5 arrays, because it would refit early, when refits are cheap, and late only once the waste had grown large. It named one way to fail, the late history, where waste accumulates slowly and the rule might wait while a few large files sat behind a code word fitted before they arrived.

One constant, in bits per character read #

The history, the Huffman code and the charges are the earlier pages’. At each version the array is coded by the Huffman code fitted at the last refit, with every document added since named through the escape and then through a Huffman subtree over the added documents’ current lengths. The loss at a version is its bits a symbol beyond the Huffman code refitted at that version — the Huffman code with no escape, fitted to every document’s current length, which is the comparison a saving quoted without its collection showed has to be made against the best code for the same collection rather than against the plain array. The reading is every character read by a refit and by every rebuild of the escape’s subtree, counted in final arrays: 6,912,669 characters is one.

The priced clock refits at the first version. At every later version it computes the loss the Huffman code in force would have there, which needs only the documents’ lengths: a store holds those as metadata, and fitting a Huffman code over 222 numbers reads nothing of the array. It adds that loss times the version’s characters to a running total, the waste, and if the waste has reached $c$ times the version’s characters it refits instead, and the waste starts again from nought. The constant $c$ is in bits wasted per character a refit reads. It was swept from 0.02 to 3.2, doubling each time from 0.05. There is no escape share, no factor and no hold: one constant, and the rule’s whole content is that the refit and the loss are measured against each other. The escape is weighted at every refit as one average document, the weight under which the escape clock did best.

Worse than the hold it was meant to replace #

Priced, the clock draws a single line from 0.026 bits a symbol for 11.76 final arrays read to 0.338 for 4.31, and at the 4.52 arrays the held escape clock reads, it loses about 0.119 where the held clock loses 0.098. The two points that straddle the held clock’s reading are the prices 0.4, which loses 0.082 for 5.19 arrays, and 0.8, which loses 0.119 for 4.51. The held clock lies under the line between them by about a fiftieth of a bit a symbol. The price does beat every doubling schedule, as the held clock did, and at its cheap end it reaches losses the held clock never offered: 0.033 for 8.01 arrays at a constant of 0.1, a third of the held clock’s loss for not quite twice its reading. But the question was whether the price could replace the hold at the hold’s own budget, and at that budget it cannot.

The prediction was wrong on its main claim and wrong about why it would be right. It expected the price to refit early, where the array is small and a refit cheap, and to save its refits for when the waste had grown. The plates below show it doing the opposite in the early history and doing about what the hold did late. The late history, which the proposal named as the risk, is where the price does least badly.

The size cancels #

Divided by the characters a refit would read, the waste the price watches is almost exactly the loss at each version since the last refit, summed — within 0.061 of it at every version — because the array’s size multiplies both sides of the rule. The waste at a version is its loss in bits a symbol times its characters, $n$. The cost of a refit there is $c$ times the same $n$. Between consecutive versions $n$ changes by a few per cent, so the rule “waste at least $c\,n$” is very nearly “the losses since the last refit sum to at least $c$”. The array’s size, which was the whole reason to price the refit, is on both sides of the comparison and drops out of it.

That is not a quirk of this history. A version’s waste is the stale code’s bits over the whole array, and the array is the same array the refit would read; any version-by-version accounting that charges waste at the size of the thing being coded and the refit at the size of the thing being read divides through by that size. What remains is a rule about time, counted in versions: refit once the stale code has lost $c$ bits a symbol, summed over the versions it has served. At a price of 0.8, that means refitting after a loss of about 0.4 for two versions, or 0.1 for eight, or 0.03 for nearly thirty. The plate shows that rhythm. From version 27 the loss is a hundredth of a bit a symbol a version and the waste creeps for five versions; from version 33 the loss is a fifth of a bit and the waste reaches the threshold in four.

So the proposal’s picture of a rule that is cheap to satisfy early and expensive late did not survive the arithmetic. A refit is cheap early, but the loss it removes is also small in bits, because there are fewer characters to waste it on, and the ratio of the two is the loss a symbol — which is no smaller early than late. If anything it is larger, and that is where the price loses to the hold.

Where each schedule refits #

The price does not refit early where refits are cheap: in the first fifteen versions, where twenty files become fifty, the held clock refits seven times and the price of 0.8 four, at versions 0, 3, 7 and 11. Over the whole history the two have about the same number of refits, eleven and nine, and the price spends the difference in the early stretch. The price of 0.4 refits twelve times and comes closer early, six, which is why its loss is lower; it pays for that with 5.19 arrays of reading rather than 4.52.

The early versions are the ones where the collection doubles fastest. Between versions 2 and 3 the characters grow by 43%, between 5 and 6 by 26%, between 9 and 10 by 12%. A code fitted at one of them is wrong at the next by a large fraction of a bit, because nearly a third of the characters are in documents it has never seen — the early shape and late bytes the shape arrived early and the bytes late first measured — and the escape names all of them through one code word sized for one document. The held clock refits there because the share behind the escape crosses twice its code word’s share in a version or two, and its hold, a quarter’s growth, is met in the same version or two. The price lets the loss run: at version 6 the price of 0.8 is carrying a waste of 0.74 bits a symbol, summed over three versions, and refits only at version 7.

The gap is all in the first stretch #

The price loses its whole gap to the hold in the first fifteen versions: there the held clock loses 0.073 bits a symbol and the price of 0.8 loses 0.168, while from version 30 to the end the two lose 0.098 each. The middle stretch goes the other way. From version 15 to 29 the held clock loses 0.124, its worst stretch, because the hold kept it from refitting at versions 15, 16 and 20, where the escape clock without a hold would have refitted; the price loses 0.095 there and the price of 0.4 0.060. The price of 0.4 is worse than the hold early and better in the other two stretches.

So the late history, which the proposal feared, is a tie, and the middle is a win for the price. The early history, which the proposal expected to be the price’s strength, is where it fails, and it fails because its unit of time is the version. A version is whatever the history happened to commit, and early in a project’s life a version can add a third of the characters, while late it can add almost nothing — versions 18 and 19 here change nothing at all. A rule that sums losses per version counts a version that changed nothing as a version of waste, and counts a version that grew the collection by 43% the same as any other. The hold counts growth instead, which is the thing that actually makes the Huffman code wrong, and in a history whose growth per version varies thirtyfold that difference decides the early stretch.

What the price leaves out #

A higher price reads less in refits and more in rebuilding the escape, so the total reading stops falling: 4.51 final arrays at a price of 0.8, 4.92 at 1.6, and never under 4.31 however high the price goes. At every version without a refit the escape’s subtree is rebuilt over the documents added since the last one. The longer a code is kept, the larger that subtree grows and the more versions it is rebuilt at, and at a price of 3.2 the rebuilds read as many characters as the refits do. The price of 1.6 reads more in total than the price of 0.8, though it refits one time fewer.

That is the second thing the proposal’s accounting left out, and it is the one where the reading goes had already measured for the doubling schedule: most of a rare-refitting schedule’s reading is not refitting at all but the price of an escape left to grow. The rule compares the waste with the cost of one refit, and is silent about the reading that not refitting incurs. Delaying a refit is not free in characters read; it moves them from the refit column to the rebuild column. A price that left them out was pricing half the exchange it meant to price, and the plate shows the price of the other half: below about 4.3 arrays, no constant buys anything.

The escape clock’s hold, by comparison, reads 3.52 arrays in refits and 1.00 in rebuilds, almost the split of the price of 0.8. Neither rule was told about rebuilds; the hold lands near the bottom of the total by accident, because a quarter’s growth is short enough that the escape’s subtree never covers much of the collection.

A loss no refit removes #

Weighted as half the coding space, the escape costs about a bit a symbol that no refit removes, and the price counts it as waste anyway: it refits 30 times in 47 versions, reads 16.56 final arrays, and loses 0.768 bits a symbol, twice what the held clock loses under the same weight. The loss at a version is measured against the Huffman code refitted with no escape at all. A code that gives the escape half the coding space makes every other document’s code word one bit longer — and a code word is at least one bit is why the escape’s own cannot be made shorter in return — so just after a refit it is a bit a symbol worse than the reference, with nothing yet behind its escape. A refit does not change that; it installs a new code with the same half-space escape and the same bit of loss. The rule sees a loss, sums it, finds it over the threshold within a version, and refits, and the refit buys nothing.

The held clock fails the other way under that weight, as the earlier essay found: the escape’s code word is one bit, nothing behind it can ever pass twice a half, and the clock never fires after the first version. Each rule is blind to something. The clock watches the escape and cannot see a code word that is too short to be wrong. The price watches the loss and cannot tell a loss a refit removes from a loss the Huffman code builds in. Under the weight read from the growth since the last refit, which starts at a half and then follows the history, the price does better than the clock, 0.178 to 0.384 — but only because the clock never moves at all.

Two units the rule did not make comparable #

The proposal asked whether a refit can be priced in the same units as the loss it removes. The answer the plates give is that this rule did price them in the same units, characters, and that pricing them in the same units was the mistake. The waste is bits over the array; the refit is the array read once; the ratio of the two is a loss a symbol, and a loss a symbol is not something a refit’s cost can ever be weighed against, because it has no size. The rule turned the question “is this refit worth its reading?” into “has the Huffman code been wrong for long enough?”, and answered the second with a clock that counts versions.

Choosing a growth factor is the classical case where the right unit is growth rather than time: a dynamic array that resizes by a constant factor pays a constant amortised cost per insertion, whatever the insertions’ timing, because the copies are charged against the elements that caused them. The escape clock’s hold is an amortisation of that kind: a refit, which costs the array, is allowed once the characters have grown by a quarter of the array, so each refit is paid for by the characters that arrived since the last. The price is not. It charges a refit to the versions that elapsed, and a version is not a cause of anything.

The day a filter cannot grow rebuilt a filter when its own count said its rate had passed a threshold, a clock read off the structure. Its threshold was a rate, a quantity without a size, and it worked because a filter’s damage is a rate. The price here put a rate, bits a symbol, on one side and a size on the other, and multiplied both by the version’s characters to make them look alike.

What one directory cannot settle #

One history. Every number is one source directory replayed version by version, the history a corpus that was not generated chose because nobody designed it. A history whose versions arrive at even growth would make the version a fair unit of time, and on it the price and the hold should agree. That was not run, and it is the obvious control.

The version as the unit of waste. The waste counts each version once, as though every committed state were coded and stored for the same length of time. A store that holds versions for different spans, or answers queries at a rate that depends on its size, would charge waste differently, and the size would then no longer cancel. That would be a different store, and was not measured.

A coarse sweep. Eight constants, doubling. The frontier between 0.4 and 0.8 is a straight line through two points, and the held clock’s lead of about 0.021 at its own reading is read off that line, not off a price that reads exactly 4.52 arrays.

The escape weighted as one document. The essay’s main comparison uses the weight under which both clocks do best. Under the other weights both rules fail for the reasons given, and neither is a fair test of pricing.

Still open: a price with the waiting in it #

The price fails for two separable reasons, and each points at a repair. The size cancels because waste and refit are charged in the same characters; and the rule leaves out the reading that not refitting incurs, the rebuilds of the escape’s subtree, which at a high price are half of everything read. Both are fixed by charging the choice as it actually is. At each version the store can compare two things it knows: the characters it reads if it refits now, the whole array; and the characters it reads if it waits, the escape’s subtree rebuilt over everything added since the last refit, which is the reading that waiting buys. The loss counts as well, at an exchange rate, but only the part a refit removes: the Huffman code’s bits beyond the Huffman code a refit would install, escape included, so that an escape weighted as half the coding space is not counted as waste.

The measurement that follows refits when the rebuild reading accumulated since the last refit plus the removable waste times a constant passes the characters a refit reads, with the constant swept as here, and charges the same three weights. The prediction is that with the waiting priced, the frontier passes under the held clock, to about 0.09 bits a symbol for 4.3 arrays, because a code is kept only while the reading it saves is larger than the reading it costs, and that the half-space escape stops refitting at every version. It could fail early, again: the rebuild reading is small while the escape is small, and in the first stretch, where the characters grow by a third a version, a rule paced by the escape’s subtree may still wait too long. The question is whether the right unit for a refit’s timing is the characters it saves rereading, or the growth that made it necessary — and whether, priced honestly, those turn out to be the same thing.