Refitting when the escape is wrong

One doubling late tried to repair the weakest part of a growing index’s document array. The array names, for every character of a collection, the document it belongs to, and the array is the length distribution found that the best code for it is a Huffman code over the documents’ lengths. A collection that grows needs a way to name documents added after the Huffman code was fitted, and the Huffman code has one: an escape, a code word that says “a document added since the fit”, followed by a small code over the added documents. Replayed through a source directory’s history, from twenty files to 222 over 47 versions, the escape was where the loss went. Refitting each time the files doubled and rebuilding only the escape’s subtree in between was the best schedule measured, and the escape’s weight at each refit decided the rest. Weighted by the share of characters that arrived since the previous refit, it lost 0.518 bits a symbol; weighted as half the coding space from the start, 0.389; weighted by the growth since a half start, 0.356, the best a store could compute; weighted by the growth still to come, which no store can know, 0.183. Every schedule rewrote the array 5.65 times over.

That page’s conclusion was that the rewriting belongs to the schedule. Its closing section proposed a different clock. At every version the store knows how many characters its escape is naming, because the escape’s subtree is rebuilt at every version from the added files’ lengths. The escape’s code word, $\ell$ bits, stands for a share $2^{-\ell}$. When the share actually behind the escape passes that by more than a factor of two, the escape’s code word is wrong by a bit, and a refit would correct it. The proposal predicted the clock would refit about six times over the history instead of four, at different versions, for a mean loss under a quarter of a bit and about the same rewriting. It named the failure: the first stretch, where the share behind the escape climbs from nothing to two thirds in nine versions and would cross a power of two four times.

The clock, and the hold #

The history, the Huffman code and the charges are the earlier page’s. The array at each version is coded by the Huffman code fitted at the last refit — and the comparison that matters is always against the Huffman code refitted at that version, not against the plain array, the trap a saving quoted without its collection found — every document added since named through the escape and then 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 rewriting is the bytes every refit and every subtree rebuild reads, counted in final arrays.

The clock refits at the first version, and afterwards at any version where the share of characters behind the escape exceeds a factor times $2^{-\ell}$. Factors of 1.5, 2, 4 and 8 were run. The clock fires only upward: just after a refit nothing is behind the escape, its share is nought, and a clock that also fired on a share too small would refit at every version. A second rule was added after the first was measured: a hold, under which the clock may not fire until the collection’s characters have grown by a factor since the last refit — a quarter or a half. The escape is weighted at every refit as the earlier pages weighted it, and the clock is reported first with the escape weighted as one average document, which gives it a long code word to watch.

Better than every doubling, once held #

A clock read off the escape, held until the characters have grown by a quarter, loses 0.098 bits a symbol for 4.52 final arrays read — under every doubling schedule on both counts: the best a store can compute loses 0.356 for 5.65, and even the escape weighted by the growth to come loses 0.183. The clock with no hold loses less still, 0.042 at a factor of two, and pays for it by reading 10.59 arrays, nearly twice any doubling schedule. Held to a half, it loses 0.189 for 3.84.

The prediction is right about the loss and wrong about almost everything else. It expected about six refits; the clock with no hold makes twenty-five. It expected about the doubling schedule’s rewriting; the clock with no hold rewrites nearly twice as much. It expected a loss just under a quarter of a bit; the clock reaches a sixth of that. The proposal had the direction right — watching the escape is a better clock than counting the files — and the scale wrong, and the hold is what turns the right direction into a schedule worth running.

Where the reading goes #

The frontier plate counts every byte a schedule reads, and splitting that count shows why the clock can refit more often than the doubling schedule and still read less. Every schedule reads two things: the whole array at each refit, and at every other version the escape’s subtree, rebuilt over the documents added since the last refit. The doubling schedule reads 1.60 final arrays in its four refits and 4.06 in rebuilding the escape’s subtree, because between refits that are twenty versions apart the subtree comes to cover most of the collection and is rebuilt at every one of those versions. The held clock reads 3.52 arrays in its eleven refits and 1.00 in rebuilds. The clock with no hold reads 10.59 in refits and almost nothing in rebuilds, since it refits nearly every time anything arrives.

So the doubling schedule’s rewriting was mostly not refitting at all. It was the price of an escape left to grow: every version between refits rebuilds a subtree over everything added since, and a schedule that refits rarely rebuilds a large subtree many times. The collections the saving was quoted for found that what a compressed document array saves depends on the collection it is measured on; what it costs to keep compressed depends, in the same way, on how its growth is spread over its history, and a schedule that ignores that spreading pays for it in subtree rebuilds. A refit costs more than a rebuild, but it empties the escape, and the clock’s refits are timed to empty it when its share has just grown enough to matter.

What the clock watches #

The clock watches one number, the share of characters named through the escape, which climbs after each refit until it passes twice what the escape’s code word assumes; held until the characters have grown by a quarter, the clock refits eleven times in 47 versions. After each refit the escape’s share starts from nothing and grows as files are added; the share the escape’s code word assumes is fixed until the next refit, and is small, because an escape weighted as one document among dozens gets a code word of four to seven bits. The two lines cross, the clock fires, the new code gives the escape a new code word, and the climb starts again.

Seven of the eleven refits are in the first fourteen versions, where twenty files become fifty and the share behind the escape climbs fastest. That is the stretch the proposal expected to be expensive, and it is: the array is small there, so those refits read little, but the clock with no hold made thirteen refits in the first sixteen versions. The hold stops the clock from refitting twice inside one quarter’s growth, which in the first stretch means not refitting at consecutive versions.

Where each schedule refits #

Doubling the files refits four times, at versions 0, 10, 22 and 44; the clock with no hold refits 25 times, thirteen of them in the first sixteen versions, where twenty files become sixty; held to a quarter’s growth it refits eleven times, and held to a half seven. The doubling schedule’s refits are spaced by the file count, which in this history grows fast early and slowly late, so its last two refits are twenty-two versions apart. The clock’s refits follow the characters behind the escape, and late in the history, when a few large files arrive, the share behind the escape climbs quickly even though the file count barely moves. The held clock refits at versions 37 and 43, where the doubling schedule’s next refit would have waited until 44.

That is the earlier page’s finding seen from the clock’s side. One doubling late said the growth seen is the growth to come one doubling late, because this directory’s growth slowed at every doubling. A clock that counts files measures the wrong growth. A clock that reads the escape measures the growth that costs bits, the characters named through a code word that was not fitted to them, and does not care how many files carry them.

The loss at every version #

The held clock’s loss is under a tenth of a bit at 30 of the 47 versions and peaks at 0.418; the best doubling schedule a store can compute is under a tenth at 10, over half a bit at 11, and peaks at a full bit. The doubling schedule’s full bit is its escape weighted as half the coding space: just after a refit nothing is behind the escape, and every document’s code word is one bit longer than it needs to be for nothing. Its half-bit stretches are the long gaps between late refits, where the escape names more and more characters through a code word fitted to fewer.

The clock’s loss has a different shape. It rises after each refit as the escape fills, and is cut off by the next refit before it rises far. Its highest point, 0.418, comes at version 20, inside a stretch where the hold has kept it from the refits the clock with no hold made at versions 15, 16 and 20; the clock with no hold peaks at 0.231. The hold is a trade between that peak and the rewriting, and a quarter’s growth is the point on the frontier plate where it costs least. A mean over 47 versions hides which versions pay, and here the versions that pay most under doubling are the late ones, where the array is largest and every bit a symbol is the most characters’ worth.

An escape the clock can see #

The clock can only see an escape whose code word is long: weighted as one document the escape starts at four bits and the clock refits eleven times for a mean loss of 0.098; weighted as half the coding space it starts at one bit, the share behind it never passes twice a half, and the clock refits only at the start. With one refit, the escape weighted as half the coding space loses 0.384 bits a symbol, about what doubling loses under the same weight, and the clock reads 17 arrays rebuilding an escape subtree that grows to most of the collection.

This reverses the earlier page’s ranking of the weights. Under doubling, the escape weighted as one document was the worst, 0.622, because between refits it names a growing share of the characters through a code word sized for one document. Under the clock, that weakness is exactly what makes the escape a good instrument: a code word that assumes a small share is wrong as soon as the share grows, and the clock reads the wrongness and corrects it. A weight that hedges, half the coding space, is never far wrong and so is never corrected.

A clock read off the structure #

The day a filter cannot grow rebuilt a filter from its store when its own count of keys said its false-positive rate had passed a threshold, a clock read off the structure rather than off the calendar, and found it better than rebuilding on a schedule. The escape clock is the same idea for a code. The structure carries, at every moment, a measure of how wrong it is — the share behind the escape against the share the escape was sized for — and a refit made when that measure crosses a threshold is made when it is needed.

The hold is the part the proposal did not have, and the part that makes it a schedule. A threshold on wrongness alone refits whenever the Huffman code is wrong by a bit, which in a small and fast-growing collection is nearly always; choosing a growth factor is the classical reminder that a structure which resizes whenever it is full resizes too often unless it resizes by a factor. The hold is that factor: the Huffman code may be wrong, but it is refitted only once the collection’s characters have grown enough for the refit to be worth its reading. Together the two read the right growth and refit at a pace the rewriting can bear.

What one history cannot settle #

One directory. Every number is one source directory’s history, whose growth was fast early, slow in the middle and lumpy late — a real history rather than a generated one, the reason a corpus that was not generated gave for using it. A collection that grows evenly would give the doubling schedule less to lose and the clock less to catch.

One shape of code. The array is coded by a Huffman code over lengths with one escape. A code with several escapes — one for each era of additions — would let a refit touch only part of the Huffman code, and a code word is at least one bit is the reminder that an escape weighted as half the coding space cannot be made shorter than the one bit it already is.

Factors on a coarse grid. The clock was run at factors of 1.5, 2, 4 and 8 and holds of nothing, a quarter and a half. A hold of a third, or one that grows with the collection, was not run, and the frontier between 3.84 and 4.52 arrays read is drawn from two points.

Still open: a hold set by what the refit will cost #

The hold is a fixed share of growth, and the plates say its right value depends on where in the history the collection is: early, a refit reads a small array and a quarter’s growth is a few versions; late, a refit reads a large one and a quarter’s growth is many. A hold could instead be set by price. The rewriting a refit costs is the array’s current size; the loss it removes is the bits a symbol the escape is wasting times the characters that will be coded before the next refit. A clock could refit when the waste accumulated since the last refit, in bits, passes the bytes a refit would read.

The measurement that follows gives the clock that rule — refit when the bits lost since the last refit exceed the array’s size times a constant, swept — and charges it as here. The prediction is that it lands on the frontier at least as well as the best fixed hold, at about 0.08 bits a symbol for 4.5 arrays, because it refits early in the history when refits are cheap and late only when the waste has grown large. It could fail on the late history: the waste accumulates slowly there and the rule would wait, as the doubling schedule did, while a few large files sit behind a code word fitted before they arrived. The question is whether a refit can be priced in the same units as the loss it removes, or whether the bytes a refit reads and the bits a code wastes are costs no single exchange rate makes comparable.