Every essay — page 10
What a bound is Counting The floors What the machine does Structures Two parameters The other axis When the algorithm flips a coin What the libraries do When it does not fit One pass, and no room The data that is not a number When the algorithm is a table The index that replaces the text What is taught wrongly Ladders Objects Search
What the libraries do
None of the sorts measured in the other fields is what runs when a program calls sort. A library sort is not an algorithm but a policy — a set of decisions, each with a threshold somebody typed — and the thresholds are where its behaviour actually lives.
Pieces that fit the buffer
A sorted file with a late tenth appended costs the buffer-limited stable merge sort 2.93 moves a key at a buffer of a 64th, fifteen times the least any sort could move, and two thirds of it is the tail sorting itself. Taking the tail a buffer at a time, inserting each key into a sorted piece in the buffer and merging the piece into the head, was predicted to bring that under two moves a key at small buffers. It never comes within twice the merge sort: insertion costs a quarter of a piece a key, and the smaller the pieces the more often each one's merge crosses the head's top fifth. The same pieces sorted in place by merging do pay, at 2.41 moves a key, and for a reason the proposal did not name: a piece that fits the buffer merges into the head without a single rotation. The gain lasts only while the tail belongs near the top of the file.
How many pieces the head can afford
A sorted file of 65,536 keys with a late tenth appended in random order can be sorted by taking the tail a buffer at a time, sorting each piece, and merging each into the head. It beats the buffered merge sort at a 64th of the file and loses at smaller buffers, because every piece's merge crosses the head's top keys again. Merging the pieces with each other first, while a round costs less than the crossings it removes, was predicted to win at every buffer. It wins at none. The first round always costs more than no rounds — 18.97 moves a key against 16.04 at a 1,024th — because a group larger than the buffer crosses the head by rotation, and the cost falls under the merge sort's only when the rounds run all the way, which is the merge sort. The head can afford thirteen pieces and not twenty-six; beyond that the best a tail can do is be one run.
The rotation that could be priced
A sort that finds a sorted file with a late tail can send the tail's pieces straight into the head or merge them to one group first, and a rule that priced both ends as shifts chose wrongly at a buffer of a 128th, because a group longer than the buffer crosses the head by rotation. Priced instead from measurements of the library merge on synthetic runs, the long crossing comes within 3% of what the sort pays at every buffer and the choice at a 128th comes right. But the rule prices the pieces against the head as it stood before any of them joined it, and each piece also crosses the pieces before it: priced up to 37% low, they send the sort to the dearer end at a 256th.
The head each piece will meet
A rule that priced a sorted file's late tail two ways before moving anything chose the dearer end at a buffer of a 256th, because it priced every piece against the head as it stood before any piece joined it. Each piece also crosses the pieces before it, and those are known in advance: one binary search of each earlier, already sorted piece counts them. Priced against the head each piece will meet, the pieces come within 6% of what they cost at every buffer, and the rule chooses the cheaper end at all seven buffers and all ten reaches of the tail. A third of what each piece crosses turns out to be other pieces, as the arithmetic of the band says it must.
Every number of rounds, priced
A library merge sort given a file whose last tenth arrived late sorts the tail a buffer's worth at a time and then either sends every sorted piece into the head or merges the pieces first. A rule priced from measured tables chose the cheaper of the two ends at every buffer. Priced the same way at every number of rounds in between, it was predicted never to choose a partway number and to price every one within 6%. It chooses the cheapest number of rounds at all seven buffers on that input and at 14 of 15 settings across reaches and buffers; the one partway optimum among them — six rounds of seven, by 1% — it misses by choosing five, 3.8% dear. But the estimates are not all within 6%. At the three smallest buffers the first round is priced 15% to 25% wrong, high at one buffer and low at the others, because its pairs of pieces cross the head in a way no table of single runs describes; the rule survives it because one round is never close to the cheapest.
When the algorithm flips a coin
A skip list's shape is a sequence of coin flips rather than a property of its keys. Where the randomness is the structure rather than a rule applied to one, the distribution is the result and the average is the least of it.
A structure made of coin flips
Insert the same 512 keys into a skip list twice, once sorted and once shuffled, from the same seed, and the two structures are identical — the same 11 levels, the same height for every key, the same silhouette. Nothing about the data reached the layout. The 1,064 coin flips did all of it.
The height is a distribution, and the coin is a parameter
A skip list over 2,048 keys is described as being about log₂ n levels tall. Across two hundred builds of exactly those keys its height ranged from 9 to 19. The number in the description is the mean of something, and choosing the coin is choosing which something.
One pass, k slots, and two randomness budgets
Reservoir sampling takes a uniform sample of k items from a stream of unknown length in one pass and k slots. The textbook version and a second version draw from exactly the same distribution, and at 65,536 items one of them spends 1,356,399 random bits and the other spends 9,380.
A filter that is allowed to be wrong
A Bloom filter holding four thousand keys in five thousand bytes answers membership in four memory probes and gets 1.14% of its negative answers wrong. It never gets a positive one wrong. That asymmetry is the whole design, and the rate it makes errors at is a third quantity beside the operation count and the space.
A hash is a family, not a function
Two thousand and forty-eight keys into two hundred and fifty-six buckets. Under a hash that takes the low bits of the key, all 2,048 land in bucket zero and 255 buckets are empty. Under a multiplier drawn at random, the worst bucket holds 11. The keys are the same keys, and they are the multiples of the table size.
The second choice
Two hundred and sixty thousand keys into as many buckets. Under one hash the busiest bucket holds eight; under two, with each key going to whichever of its two is emptier, it holds four. The mean is exactly one in both. Nothing is rearranged afterwards, no key is ever moved, and the whole of the improvement is in a decision taken once, at the moment the key arrives.
An insertion that can fail
Every randomised structure in this field buys an expected cost and accepts a tail. Cuckoo hashing buys a worst case — a lookup examines exactly two slots, for any keys, always — and pays for it in the construction, which can fail outright. On a table of four thousand slots the construction never fails below 0.45 keys per slot and fails nineteen times in twenty above 0.55.
A match decided by a number
Rabin–Karp replaces a comparison of two strings with a comparison of two integers, and pays for it only when the integers agree by accident. On 65,521 windows at a modulus of 1,009 it verified 79 times against a predicted 64.9. On a text of 1,024 characters chosen with the modulus in hand it verified at 64 windows out of 64 possible, each one costing fifteen of the pattern's sixteen characters — and the closed form is silent about that, because it assumes nobody chose the text.
The evidence a filter cannot remove
A Bloom filter never says no about a key it holds, and that is its whole guarantee. Clear the bits of a thousand deleted keys and it starts saying no about 638 of the thousand it still holds. A counter in every cell repairs it at four times the space; a fingerprint repairs it at twice, and acquires a condition on the caller that neither of the others has.
The estimate that is a median of means
An estimator with a 70% spread is not usable and an estimator with a stated failure probability is. The construction that turns the first into the second is two lines long, it is where every delta in this field comes from, and its exponential is measured here by counting failures rather than by evaluating a bound.
The independence an estimator spends
Every sketch's analysis begins by assuming a truly random hash, and nobody comes back to that line. Independence has a degree, the degree is enumerable over a small field, and an estimator's mean and its variance spend different amounts of it.
The intersection two filters cannot report
Two Bloom filters over sets that share five hundred keys, ANDed bit by bit. The result never denies a shared key, and it looks like a filter of the intersection. It is not one — a key in only one of the sets passes it 1.8% of the time where a real filter of the intersection passes none, and reading the intersection's size off its bits gives 900.
More hashes or wider buckets
A cuckoo table with two hash functions and one slot per bucket cannot be built past about half full. Give it a third hash function and it builds to 0.92. Keep two hashes and give each bucket two slots and it builds to 0.89; four slots, past 0.95. Every shape keeps the worst-case lookup the plain table was built for, and every shape pays for its threshold in a different place.
The tie that breaks left
Two choices per key, the emptier bucket wins, and when the two are equally full a coin decides. Replace the coin with a rule — split the table into halves and always send a tie to the left one — and on a million keys the buckets holding three or more fall from 9,316 to 4,694, and the busiest bucket drops from four to three. The hashing, the probes and the keys are unchanged, and the rule spends no randomness at all.
A filter past its design size
A Bloom filter sized for two thousand keys at one per cent answers yes to 15.6% of absent keys at four thousand and 68.1% at eight thousand. Nothing fails and nothing warns. A stack of filters that adds a tighter layer whenever the top one fills holds 2.0% at eight thousand, under a bound it can state in advance — in 2.9 times the bits of one filter sized for eight thousand from the start.
Choices that are not independent
The power of two choices is analysed for choices drawn independently, and computing four independent hashes per key costs four hash evaluations. Compute two and take the choices to be h₁, h₁ + h₂, h₁ + 2h₂ and h₁ + 3h₂, and the choices are about as far from independent as they could be. On a million keys the buckets holding two or more come to 147,536 against 147,367 for four independent hashes, and the busiest bucket holds three either way.
A filter that grows by moving a bit
A table of fingerprints can double in place, moving one stored bit of every fingerprint into its slot number, and so grow as one structure with one lookup where a stack of Bloom filters adds layers. Its false-positive rate is fixed by the fingerprint's length and not by the table, so with nothing reserved it doubles as the keys double — 0.69% at a forecast of 2,000, 5.7% at eight times that. Reserve three bits at the start and it holds 0.66% at eight times, in 294,912 bits, exactly what a table built for sixteen thousand keys would hold and fewer than the stack's 428,938. The reserve is a forecast of growth, and past it the rate climbs again.
Two hash values and the keys they copy
A Bloom filter that makes its k bit positions from two hash values, as h₁ + i·h₂, answers yes to 1.6% of absent keys on a 64-bit filter where k independent hashes answer 0.69%. The penalty is not the one expected. With the step forced odd no key ever repeats a bit, while a quarter of independent keys do. What costs the filter is a query whose start and step reproduce a stored key's whole progression, which happens with probability 4n/m², measured to within a few per cent from 64 bits to 4,096. The penalty fades as the filter grows and returns as the hash count rises — 1.13 times at seven positions on 1,024 bits, 5.35 times at thirteen.
The bits given to the wrong keys
A fingerprint table that gives later arrivals longer fingerprints holds 3.6% where a table that reserves nothing holds 21.1%, and it never runs out of reserve because it has none. It also dies at exactly the same size as the table that reserved nothing — 32 times its forecast, on the same key — because every generation shares one quotient, and the generation with the shortest fingerprint is the one that arrived first.
Positions confined to one line
A Bloom filter lookup reads 5.55 cache lines because its six positions are scattered across the whole filter. Confining them to a 512-bit block makes it exactly one, and costs 7% more false positives at eight bits a key. At sixteen bits a key the same block costs 91%, and the two-value trick that is free across a whole filter costs another 135% inside one — because a block is a small filter, and small filters are where the penalty lives.
Two blocks and the chances they add
Send each key to the emptier of two 512-bit blocks and the busiest block of a filter at sixteen bits a key holds 35 keys instead of 51. The false-positive rate gets worse: 0.0997% against 0.0854%. At eight bits a key it nearly doubles. A lookup cannot tell which block a key went to, so it has to ask both, and asking twice is two chances to be wrong. At every density a filter is commonly built at, the repair that tames a hash table's worst bucket buys a filter nothing that a block twice as wide does not.
A block the lookup can work out
Sending each key to the emptier of two blocks flattens the load and doubles the chance of a false positive, because a lookup cannot know which block was chosen. Give each block a threshold on a hash of the key instead and the lookup can work it out: one block read, one chance, and 46% of the load balance kept. At sixteen bits a key that is 0.0618% against one block's 0.0854% and two blocks' 0.0997%. The threshold costs 1.5% of the budget and two bits of it are nearly as good as sixteen.
The day a filter cannot grow
A fingerprint table dies when its quotient reaches its shortest fingerprint, and a filter cannot lengthen a fingerprint because it does not keep its keys. The store it filters does. Rebuilt from that store whenever its own count says its rate has passed 1%, a table grown a thousandfold never exceeds 1.05% and ends holding exactly what a reserve of ten bits holds — 18.9 bits a key — having read the store 1.34 times over. The reserve paid its bits early: 34.8 a key at four times the forecast, where the rebuilt table held 18.4. Which one is cheaper depends on whether the growth arrives.
A penalty set by the block
A blocked Bloom filter pays a penalty for its uneven block loads, and a threshold that lets a lookup work out its block repays about a third of it — measured on 2,048 keys, with a prediction that larger filters would widen the gain. From 2,048 keys to 131,072 nothing moves: one block holds 0.086% to 0.090% against a computed 0.086%, and the threshold design 0.060% to 0.065%. The busiest block grows and the rate does not follow it. What sets both the penalty and the repair is the keys a block holds. A threshold turns out to be worth one doubling of the block's width, and its advantage shrinks from 40% at sixteen keys a block to between 5% and 13% at 128.
The bits a second threshold costs
A blocked Bloom filter whose first block carries a threshold was proposed a second threshold on each key's second block, with a third block for keys both refuse. It does what it was meant to: at 512-bit blocks it removes nearly a third of the load spread the first threshold left. And the rate does not fall — 0.066% against 0.062% — because the second table, paid for in blocks, raises the rate the filter would have with no spread at all by more than the narrower spread saves. The threshold was stored in more bits than it needs: at four to six bits, one threshold beats the eight-bit design by about a tenth on one run, and a second threshold of the best width ties it at 512-bit blocks.