Design parameter — where it appears
Named by 60 essays across 7 fields — each of them below, with the objects they name alongside it.
The bound a block can and cannot have
Knuth's condition turns an interval table's cubic fill into a quadratic one by bounding each cell's best split between its two neighbours'. A blocked fill cannot use it a cell at a time, and the two cells that bound a block lie outside the block — one to its left, one below it. The schedule has finished both for ten per cent of the blocks, the bound then removes eleven per cent of the splits, and it removes half a per cent of the cache misses, because the splits it skips are the ones already in the cache.
What a planner pays to find out what to pay
Insurance against a row estimate is set from the error's median and spread, and a running system knows neither — it has to fit them from executed queries. Fitted from one query the divisor costs 1.263 times the better plan against 1.215 for a planner that never insures at all, so learning is worse than not learning until about sixteen queries have run. The tail, though, is bought immediately: one observation already holds the worst case to 24.7 against 36.6.
A decay measured from where it started
An exponentially decayed counter is one number because its weights fade by elapsed time alone. Forward decay keeps a polynomial weight in one number too, by measuring each arrival from a fixed landmark. Its memory is then a share of the time since that landmark: at β = 2 an arrival counts half at 29% of that time. Anchored at the start of a stream, it takes 5.3 seconds to register a fourfold rise twenty seconds in and 83 seconds when the rise comes at five minutes.
The sibling a full leaf asks first
The rule databases use to fix ascending inserts fills their leaves completely and collapses to 53.4% when one key in a hundred arrives late. A leaf that offers a key to a sibling before it splits, and splits two full leaves into three when neither will take one, holds 84.2% on the same stream — and is better with a trickle of late keys than without one, because a perfectly ascending stream has no sibling with room.
What a heavier tail actually buys
Four decays, each tuned until it is equally quiet on a stream with nothing happening, then given one burst. At a burst of three hundred they see it for 54, 63, 68 and 104 seconds — indistinguishable. At nine thousand the exact polynomial reaches 384 seconds and the exponential 156. The shape of a tail does not decide how far back a scheme can see. It decides how fast that distance grows with the size of the event, and the exchange rate is the reciprocal of the exponent.
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.
The read a filter has no key for
A Bloom filter on every run of a log-structured store turns a lookup for a missing key from a read of every level into a fraction of one — 0.72 transfers across eight levels at five bits a key, and 0.00027 at twenty. A range query over the same store reads nine transfers at five bits and nine at twenty, because a filter answers whether one named key is in a run and a range has no key to name.
A detector that learns its own quiet
A burst detector built from a fast decayed counter needs a threshold, and the one it was measured with came from sixty independent runs of the background — an oracle no deployed system has. Two counters and a running mean square of their difference can supply it from the stream itself, and on a stream that does not move they hit a 5% false-alarm rate at every setting tried. What they lose is the burst: a scale that learns every reading learns the burst as noise and forgets it in 20 to 40 seconds whatever its size. Holding the scale while alarmed brings the oracle's horizon back for small bursts, turns a slow drift into an alarm that will not stop, and still cannot see past the lag at which the slow counter holds more of the burst than the fast one.
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.
A key passed along the row
A full B+-tree leaf that offers a key to its immediate neighbours before splitting leaves an ascending stream 67.2% full. Let it look one sibling further and the same stream fills its leaves completely, 2,048 leaves where there were 3,048, for about the same key moves. On random keys each doubling of the reach adds a few points of fill and more writes than it saves, and at the whole parent a key travels sixteen leaves on average. On a stream that is mostly in order the same reach costs almost nothing.
The clock a burst cannot outlast
A burst detector that holds its scale while alarmed keeps a burst visible to a ceiling set by two half-lives, and cannot stop alarming on a slow drift. The repair proposed for it was a schedule: learn again once an excursion has outlasted anything a burst could produce. Timed by how long the alarm has lasted, the schedule changes almost nothing, because on a gentle rise the alarm breaks every few seconds and the clock never reaches the ceiling. Timed by how long the difference between the counters has stayed positive, it keeps every burst to within about a second of the ceiling and falls below the target false-alarm rate on steep drifts — and one quantity, the drift's offset measured in spreads of the difference, says where it still fails.
A lookup that stops caring how wide an entry is
Buckets of eight entries aligned to a cache line read 1.20 lines a lookup when an entry is eight bytes and 19.25 when it is 128, because the bound was arithmetic about alignment and the arithmetic stops holding. Keeping one byte of each key's hash in a separate array and the entries in a parallel one reads 2.21 lines at every width from four bytes to sixty-four — and for a key the table does not hold, 2.05 against 31.98.
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 planner that knows how sure it is
A planner that fits its insurance divisor from a handful of executed queries under-insures, because a spread fitted to a small sample is biased low. The textbook repair is to use the upper end of a confidence interval on the spread instead of its centre. At a read ratio of four it makes the planner worse than trusting its estimate for longer — until sixty-four queries rather than sixteen — and it buys the worst case immediately, from 22.4 times the better plan to 6.2 after two queries. The bound is not a correction towards the truth. It is a dial between two different planners.
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 runs a range query can skip
A Bloom filter over key prefixes can tell a range query that a run holds nothing it wants, which a filter over keys cannot. On a four-level store of a million keys, a range expected to hold one key costs 4.76 transfers with no such filter and 2.41 with one built on 20-bit prefixes. The best length moves two bits for every tenfold longer range. By a hundred keys the most any range filter could save is a fifth of a transfer, because only the smallest level is ever empty. And the same memory spent on 20-bit prefixes makes a lookup for an absent key three times dearer.
The slope the slow counter already shows
A burst detector built from a fast and a slow decayed counter reads a steady rise in its background as an offset in their difference, β(R − 1)H/ln 2, and alarms on it. Every repair so far waited the offset out. This one subtracts it: the slow counter's own change over one slow half-life is a reading of the slope, and the offset follows from it. At R = 16 the corrected detector alarms on 5.5% to 7.8% of readings on rises that make the held scale alarm on 11% to 63%, and it costs a burst at most 3.7 seconds of detection. The estimate has to be quick: four times slower, it has recovered only 71% of the offset when alarms start to count.
A reach that follows the stream
A full B+-tree leaf that passes keys along its siblings wants a short reach on random insertion and the whole parent on a nearly ordered stream, and a tree is never told which it is receiving. Let the reach double after every 64 overflows whose walks averaged two siblings or less and halve otherwise, and it finds the whole parent on every ordered stream. On random keys it lands on the fixed reaches' own frontier. On a stream that turns from random to ordered halfway it beats every fixed reach, by 57 leaves at the same writes. It notices a turn to random in 62 insertions and a turn to order in 779. Below a target of 1.75 siblings it thrashes on ordered keys.
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.
The digit a pass chooses for itself
A radix sort's digit width trades passes against the streams each pass scatters into, and the best width depends on the keys and the cache together: 8 bits for uniform keys through 32 KB, 11 through 256 KB, 16 for keys with few distinct values. A digit widened because the previous pass's counts were concentrated cannot find it, since in a least-significant-first sort one digit's counts say nothing about the next. One read that counts every byte at once, and a sample to size each field, can. Charged for both, the resulting plan is never worse than 1.23 times the best fixed width on any keys or cache measured. The best single fixed width reaches 1.50, and 11 bits reaches 3.61.
The rise the correction kept subtracting
A burst detector that subtracts a rising background's offset, read off its own slow counter, goes on subtracting it after the rise has stopped. The prediction was a deficit for about one slow half-life that would cost bursts of 300 arrivals. Measured, the deficit is deeper and longer: down to 1.46 spreads below zero, below half a spread for seventeen minutes after a 40% rise. Bursts of 300 are never missed. What the deficit costs is small bursts — 30 arrivals caught 27% of the time where the rise saw 77% — and a fifth of a large burst's visible time.
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 small levels' share of a range filter
Prefix filters on a four-level store were proposed a prefix length each, on the reasoning that one length is a compromise between levels whose densities differ 43-fold. Each level does want its own length, 18 to 22 bits, and that recovers a quarter of the gap to a perfect range filter. The gap is mostly not about length. Three fifths of it is false positives. Moving filter bits from the largest level to the small ones — 12, 12, 8 and 3 bits a key instead of 5 each — recovers more than half of it at the same memory, and matches one shared length given twice the memory.
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.
The resolution a range filter can afford
A prefix filter on each level of a log-structured store answers a range by asking one question for every prefix the range touches, and each can be wrong. A filter holding prefixes at every length from 16 to 24 bits could ask each range at the resolution it needs, and was proposed as the repair. At the store's five bits a key it costs 5.69 transfers a range query where one length a level costs 4.32, because a short range is asked only at the finest length, and that filter now holds a fraction of the memory. Asked at every length it recovers most of that, and seems to overtake the single length at twelve bits a key — but only a single length chosen for five bits. Chosen again for each memory, one length a level beats every multi-resolution design at every memory measured, because the resolution a level can afford is itself set by its memory.
A threshold knows only its own block
A blocked Bloom filter that gives each block a threshold on a hash of the key lets a lookup work out which of two blocks a key went to, and it spends a small table to do it. Sharing one threshold among a group of blocks would shrink the table, and was proposed as the next saving. It is a loss at every group size. With one four-bit threshold a block, 512-bit blocks reach a false-positive rate of 0.061%; shared by a pair, 0.071%; shared by sixteen, 0.100%, worse than no threshold at all. Neighbouring blocks fill at unrelated moments, so a shared threshold closes when the first of its group does, and every key it turns away lands in a second block chosen at random.
One length for the gaps and the clusters
On uniform keys one prefix length a level, chosen for its memory, beat a filter holding every length from 12 to 24 bits. Clustering the keys was predicted to reverse that, because coarse prefixes between clusters are empty and a coarse filter can then say no to a long range in one question. Clustering alone does not: whether ranges fall in the gaps or at the keys, one length re-chosen for that workload still wins, since it moves coarse for the gaps and fine for the keys. The multi-resolution filter wins only where a clustered store is asked both — by 0.17 transfers a query at ten bits a key on sixteen clusters — and it wins on short ranges inside the clusters, not on long ones between them.
A check as slow as what it checks
A burst detector that subtracts a rising background's offset goes on subtracting it after the rise ends, and loses small bursts in the trough that opens. Capping the subtraction by what the difference itself shows, averaged over one slow half-life, was predicted to close the trough to under half a spread. It lifts it from 1.46 spreads to 1.24, because that average is as late as the estimate it checks. Averaged over a quarter of the time it lifts it to 0.70 and catches small bursts in the trough more often than any other design but the one that alarms on a fifth of its readings. Neither cap helps after a large burst, which every slope correction reads as a rise.
Two hashes that shared their low bits
Two pages on blocked Bloom filters with thresholds each recorded an instability they could not explain: a false-positive rate that collapsed on one seed at 256-bit blocks, and a pair of four-bit thresholds measuring 0.169% where its neighbours measured 0.08%. Both came from how a hash was brought into range. Every filter took its block and its ordering value as a modulo of a multiply-shift hash, and the low bits of such a hash depend only on the low bits of the key, so the two values were dependent whenever the block count had a factor of two to spare. At 992 blocks the threshold filter measures anything from 0.185% to 0.645%; read from the hash's top bits, 0.126% to 0.133%.
Two lengths that do the work of eleven
On keys that cluster, asked both between the clusters and at them, a prefix filter holding every length from 12 to 24 bits beat one length a level by 0.17 transfers a range query, and a pair of lengths — one coarse, one fine — was proposed to recover nearly all of that. It recovers more than all of it: 0.23 transfers at ten bits a key, and at four bits, where the eleven lengths lose to one, the pair still saves 0.18. The coarse filter takes under 2% of a level's memory, and the eleven-length filter was leaving its finest length as little as 14% and cannot give it more without starving the lengths its descent passes through. The store predicted to defeat a pair, with gaps at two scales, does not. The saving is bought in questions: the pair asks its filters more often than the eleven lengths do.
A code that has to fit its worst line
A blocked Bloom filter's four-bit thresholds are far from uniform: two blocks in five never close, and the rest crowd into the upper values, an entropy of 2.4 to 2.8 bits. A table coded from that distribution was predicted to match the four-bit rate on under three bits a block. Packed end to end it does, at 2.65 to 3.03 bits, and it costs every lookup a second read for the index. Packed a fixed number to a cache line it needs no index, but every line must hold its worst run of long code words, which costs 3.19 bits at 64-bit blocks and eighty-three code words decoded a lookup. Where the table is large enough for the saving to show, a plain three-bit table gets part of it with none of the costs.
The filter rebuilt with every write
A log-structured store chooses a range filter's two prefix lengths when it writes a level, and a filling store's small levels hold only the keys that arrived last. Choosing at every write was predicted to keep the lead a pair chosen once on the full store has, except where keys arrive a cluster at a time and a small level's choice goes stale when the next batch lands elsewhere. It cannot go stale: a levelled store changes a level's keys only by rewriting it, and rewriting it rebuilds the filter. Choosing at every write and choosing once then differ by at most 2.3% of what a perfect filter saves, on both arrival orders, at two bits a key and at ten, and choosing costs twenty-eight times the hashing. What the order of arrival changes is the store: filled a cluster at a time, its small levels hold one cluster each, and at two bits a key the same filter captures 94% of a perfect filter's saving against 68% shuffled.
A bit for whether it closed
Almost half of a blocked filter's threshold table says one thing: this block never closed. Store that answer as a bit a block, and a closing value only for the blocks that did, found by counting the ones before it. At 64-bit blocks the prediction was 3.1 bits a block and two cache lines. Packed end to end it lands at 3.15 bits and 2.5 lines; packed a line at a time it reads two lines and counts one word, and costs 3.64 bits, because every line must hold the most closings any line happens to draw. At 512-bit blocks, where three blocks in five close, it saves under a tenth of a bit.
One bit a key, divided
A levelled store of a million clustered keys, each level's range filter a pair of prefix lengths chosen when the level is written, captures 68% of a perfect filter's saving at two bits a key spread evenly when its keys arrive shuffled, and 94% when they arrive a cluster at a time. The proposal was to divide the memory by what each level's filter saves per bit, and it predicted the memory would leave the small levels, whose keys the arrival order had already sorted out. It goes the other way, as it did for single prefix lengths, and much further: the small levels take twelve to sixteen bits a key, the deepest level one, and the store captures 99% of a perfect filter's saving on both orders while leaving part of the budget unspent. Divided, one bit a key on average does what four bits spread evenly cannot.
The worst of more lines
A blocked Bloom filter's threshold table, stored as a bit for whether each block closed and a value for each block that did, packed a fixed number of blocks to a cache line, costs 3.64 bits a block at 64-bit blocks because every line must hold the most closed blocks any line draws. Sizing the line for the mean plus one standard deviation, and moving a line's excess values to a shared overflow, was predicted to cost about 3.25 bits and send under one closed lookup in a hundred to a third line. The lookups behave as predicted: 0.6% read the overflow, 2.003 lines a lookup. The bits land at 3.38, because every line must carry the offset where its moved values begin. What the measurement found instead is that the worst line is a property of how many lines there are: 3.38 bits at two thousand blocks and 3.62 at a hundred and twenty thousand, while the line sized for the usual line costs the same at every size.
A division chosen before the queries arrive
A levelled store's range-filter memory, divided among its levels by trying every assignment against the store's own queries, captures 99% of a perfect filter's saving on both arrival orders, with the small levels at twelve to sixteen bits a key and the deepest at one. A store writing a level cannot try every assignment, but it knows its levels' sizes, and a rule giving each level δ more bits a key for every factor of four it is smaller was predicted to match the fitted division on the shuffled store and to land near the even split's 94% on the store filled a cluster at a time. It matches the fitted division on both: 97.2% to 99.0% shuffled and 99.7% to 99.9% filled a cluster at a time from one bit a key up, with δ chosen on a sample of queries and charged on others. One δ of four, set before any query, is within a point and a half everywhere from one bit a key up. The rule fails exactly where the proposal said: a δ of six or more at one bit a key gives the deepest level nothing, and the shuffled store falls from 97.2% to 73.9%.
An offset that only has to reach its neighbours
A blocked Bloom filter's threshold table, its cache lines sized for the mean number of closed blocks plus one standard deviation and their excess values moved to a shared overflow, cost 3.38 bits a block where 3.25 was predicted, because every line carries a nineteen-bit offset into the overflow. Grouping lines, each line's offset reaching only its group's part and each group's position held once in an array of its own, was predicted to cost 3.31 bits a block for 2.0064 lines a lookup. It costs 3.301 for 2.0060, as predicted. But the nineteen bits were mostly an offset sized to address a table of moved values, when the overflow this table has needs eleven: sized for the overflow it has, the ungrouped line costs 3.337 for no extra line at all. Grouping's further three hundredths cost a line a moved lookup, and spent on room instead, that line buys more. At equal lines a lookup the grouped table is the dearer, by a hundredth to nine hundredths of a bit.
The sizes a store passes through
A levelled store's range-filter memory can be divided by its levels' sizes alone, a few more bits a key for every factor of four a level is smaller than the deepest, and on the full store that rule matched the division fitted to the store's own queries at every budget. Through the fill it does not. At a bit a key or less it falls up to 17 points of a perfect filter's saving behind on the shuffled store and 26 on the store filled a cluster at a time, and every large loss has the same cause: part way through the fill the deepest level is a smaller share of the store, and the rule gives it nothing.
A floor under every level
A levelled store's filter memory divided by its levels' sizes lost up to 26 points of a perfect filter's saving part way through its fill, every large loss a level given no filter at all. A floor of half a bit a key under every level was predicted to close every gap above five points at one bit a key and cost nothing at two and four. It closes them: the worst gap at one bit falls from 17 points to 4 on the shuffled store and from 25 to under 1 on the clustered one, and nothing moves at two bits and up. At half a bit a key the floor is the whole budget and the rule becomes the even split, which the clustered store wants half way through and the shuffled store, at the same sizes, loses 35 points by.
A reserve sized for the spill
A split threshold table gives every line the same room, the mean number of closed blocks plus some standard deviations. Giving each line room for the mean and each group of 64 lines a shared reserve at one standard deviation of the group's total was predicted to cost about 3.24 bits a block for 2.006 lines a lookup, under the best ungrouped line. The reserve it predicts holds 52 values where the group's lines spill 145: it is full in every group, the spills go on to a third line, and the table lands on the ungrouped curve. Sized for the spill instead, the reserve puts the table under that curve at every room, by two to three hundredths of a bit a block.
The room the lines lend
A blocked filter's threshold table gives each 512-bit line room for its closed blocks' values, and a group reserve sized for the spill had just put it under the ungrouped curve. A line under its room leaves slots empty that are already paid for, so its neighbours' spills could be carried forward into them, with no reserve at all: predicted at about 3.12 bits a block for 2.012 lines a lookup. The bits are right and the lines are not. At room for the mean a carried value passes 12.8 lines before it finds a slot, because a run of lines that is room-for-the-mean on average is a queue with nothing to spare. Given three quarters of a deviation of room, the walk falls under two lines and the carried table lands a hundredth of a bit under the reserve.
A span the queries do not see
A rule for dividing a levelled store's range-filter memory by its levels' sizes, with a floor of half a bit a key, came within five points of the division fitted to the store's own queries at every budget from one bit up — but at half a bit the shuffled and the clustered store wanted opposite divisions of identically sized levels. A level's fences, its first and last keys, say how much of the key space it spans, and a clustered level spans little. Scaling each level's bits by that span was predicted to close the half-bit gap and change nothing above. It changes nothing at half a bit — where the floor is the whole budget, so there is nothing left to scale — and from one bit up it puts the clustered store 30 points behind the fitted division, where the floored rule was within one. A level holding one cluster spans 0.4% of the key space and meets 4.4% of the queries, because half of them start at a stored key: the fences measure the key space, and the queries are aimed at the keys.
A walk that stops at two lines
A blocked filter's threshold table, its lines sized for the mean number of closed blocks and each line's surplus carried forward into the next lines' empty slots, was cheapest in bits — 3.113 a block — and dear in lines, 2.183 a lookup, because a carried value joins a queue with no slack and walks 12.8 lines. Capping the walk was predicted to keep most of the bits, about 3.13, for under 2.02 lines, two hundredths under a reserve sized for the spill. Capped at two lines, the walk sends 53% of its carried values to overflow, and the table costs 3.180 bits a block for 2.027 lines. That is a hundredth under the spill-sized reserve at the same lines and a few thousandths under the uncarried line's curve: at room for the mean most of what joins the queue would wait more than two lines, so the overflow becomes the reserve by another name. With room to spare, every cap loses to the reserve.
Eight cells at once
The anti-diagonal fill order exists because its cells do not depend on one another, and every table filled here has been walked one cell at a time anyway. Computed eight at a time, a step touches 5.71 cache lines on the layout that stores the table by diagonals and 10.87 on the one that stores it by rows — and per cell the first keeps falling to 0.42 while the second stops at 1.27. The prediction that a diagonal step would touch three or four lines was wrong, and line-aligning each diagonal only takes it to 4.94.
A tag that answers more than yes
A byte of hash in front of each entry has one bit of output per slot: this tag matches or it does not. Cut it from an ordered field instead and a bucket's tags can be kept sorted, so a lookup stops at the first tag above its own — 8.97 comparisons for an absent key instead of 14.43, for 3.55 tag-byte shifts an insertion. The obvious ordered field is the trap. Take the tag from the bucket index's own bits and every key in a bucket shares them: 5.74 entry reads on an absent key instead of 0.054, a hundred and seven times more.
Entries found by the rank of their tag
A bucket whose tags are kept sorted is an index: the position a tag is found at is its rank, and a rank can address an entry. Drop the fixed slots and pack each bucket's entries in tag order, and a cuckoo table of 32-byte records holds 36.1 bytes a key at half load where slots hold 66.1, and 34.3 against 36.7 at 0.9. Every insertion pays for it by moving the entries after its rank: 99 bytes against 36 at half load, 586 against 105 at 0.9. The prediction that packing would lose above 70% load was about the wrong quantity.
The request no price of memory would make
libstdc++'s stable_sort asks for a buffer of half the input. Priced in element moves against the memory held, every buffer from nothing to a buffer as large as the input has a range of memory prices at which it is the cheapest — except that one. A quarter of the input costs 1.4% more moves; a full buffer, merging out of place, saves 8% more for twice the memory; and the half-sized request sits above the line between them at every size measured. The record size, predicted to move the answer, does not: moves and memory both cost in proportion to it.
The slack an insertion can reach
A cuckoo table whose entries are packed by tag rank holds half the bytes of a slotted one at half load, and pays by shifting entries on every insertion. It was proposed to keep a few spare entries at the end of each group's region. Charged the copies a full region costs, that slack helps only with the copies: at groups of 16 buckets an insertion still moves over a thousand bytes, against 36 for slots. The same slack divided among the buckets, with an insertion borrowing the nearest free entry, moves 347 — and the group size, which multiplied every earlier cost, stops mattering.
Spare where a bucket can use it
A cuckoo table packed by tag rank keeps a few spare entries in each region of sixteen buckets, and every time a region runs out it divides its spare among the buckets again. Divided evenly, most of the spare ends up in buckets that are already full, which never grow — they kick. Divided in proportion to where insertions have been landing, as proposed, more of it does, and an insertion at 90% load moves 1,159 bytes against 1,005. Divided by the room each bucket has left, only 3% of it is stranded, and at 95% load an insertion moves 10 to 17% less than with an even division. None of the three comes near the half-load figure, because all of the growth from half load to 90% is the cuckoo kicks' own cost.
A request that reads the input first
A stable sort that asks for its buffer before it has looked at the input asks for half of it, whatever the input is. One pass to find the input's natural runs lets a merge ask only for the shorter run of each merge it will make. On input of four long runs that takes the moves from 17 a key to under 3, and on a sorted file it makes no moves at all. The buffer it needs barely falls: on anything from two runs to four thousand it asks for 36 to 45% of the input, because a balanced schedule's last merge joins two halves of the file. The request falls only where one run dominates. On a sorted file with a tenth of it appended at random, it asks for 3.7% of the input.
The buffer a schedule cannot bend
A stable merge sort that reads its input's runs first needed 36% to 45% of the input as buffer, because a balanced schedule's last merge joins two halves of the file. The repair proposed was to set the buffer first and choose a schedule whose merges fit it. No schedule can: merging the smallest pieces first still ends with two large pieces on almost every input, and every merge that does not fit is split by rotation. The extra moves are all rotations, six to eight and a half a key at a sixteenth of the input on every input, so the two costs simply add. Reading the runs still beats the library at every buffer on every input made of runs, and the schedule matters only where one run is most of the file.
The keys a capped chain leaves behind
At 95% load five sixths of the bytes a packed cuckoo table moves on an insertion are its kick chain, and the chain is mostly tail: capping it at two kicks removes 72% of the kicks. The proposal was to put the key still displaced into an overflow held in its region's spare, and it predicted that the bytes moved would halve. They fall by 13%. A key placed in the spare costs 1,819 bytes to insert, six kicks' worth, because the free slot nearest the region's end is far away and every entry between moves. The same cap with the overflow in a separate block halves the bytes as predicted, for a byte a key and an overflow that every failed lookup has to read.
The lookups a filter turns away
A capped cuckoo table keeps its stopped keys in an overflow block a region, and at 95% load every lookup for an absent key reads those blocks — 1.93 of them, because a key could have been stopped in either of its buckets' regions. A Bloom filter over each region's overflow at eight bits a key was predicted to let about 2% of those lookups through. It lets 2.07% through, and the prediction was right for two wrong reasons that cancel. Filing every stopped key under its first bucket halves the rest, and then the lookups the filter cannot help, the 3.9% of keys that really live in the overflow, are what is left to pay.
The block already open
A cuckoo table that caps its kick chain at two keeps the keys it stopped in an overflow block a region, and with a filter in front of each block a successful lookup's cost is set by the share of keys living there: 3.7% after one fill to 95%. Under deletions and insertions in equal numbers it was predicted to climb without limit unless every deletion moved a stopped key home. It does not climb without limit; it settles, at 9.2%. Homing at every deletion holds it at 4.0%, as predicted — by reading a block on 98% of deletions, and by sending a quarter of the insertions that follow to the overflow, because a key moved home takes the slot the next key needed. Moving keys home only when their block is already open for another reason holds the overflow at 4.9% for 0.07 blocks a pair more than leaving keys alone, and costs less than leaving keys where they stopped from one and a half successful lookups a deletion.
Room the chains could not reach
A cuckoo table that caps its kick chain at two, churned at 95% load, keeps 9.2% of its keys outside their buckets while 13.8% of its entries stand empty. Keeping a few entries in each region aside for the keys the cap stops, at the same memory, was predicted to remove most of the overflow for a tenth of a kick an insertion. It removes none of it: the share outside the buckets stays at 9.2% with up to eight entries kept back, because a key is stopped by the pair of buckets its chain visits, never by a region short of room. What the reserve changes is where the stopped keys sit, and that is worth having. Read with the region's header, four entries a region take the overflow blocks from 9.2% of keys to 6.1% when keys stay and from 4.9% to 2.3% when keys go home with an open block, for no kick anyone can measure — until the reserve takes room the chains were using, at sixteen entries when keys stay and at eight when they go home.
A kick that looks before it moves
A cuckoo table that caps its kick chain at two, churned at 95% load, keeps 9.2% of its keys in overflow while 13.8% of its entries stand empty. A kick that first reads the other buckets of a full bucket's residents and moves one with room was predicted to remove most of the overflow for about three bucket reads an insertion that meets a full bucket. One level of looking leaves 0.20% in overflow and two levels leave none, for 5.7 reads an insertion that meets a full bucket. But blind kicks under a cap of 32 leave 0.02% for the same 4.2 reads an insertion, so the empty room was never out of a blind chain's reach: the cap of two kept it empty. What looking saves is the thing the cap was introduced to save. The blind chain that reaches the room rewrites 4.2 entries an insertion; the look rewrites 1.8, and at 97% load 2.1 against 7.2.
A look that spreads the room
A cuckoo table's insertion that meets a full bucket can look at its residents' other buckets before moving anyone, and the look that stops at the first with room leaves 0.20% of keys in overflow at 95% load. Moving the resident to the emptiest of the eight instead was predicted to leave none, for one and a half more reads, by spreading the table's free slots rather than consuming them where they are found. It leaves 0.08% for 2.8 more reads, and at 97% load it barely helps. The room does spread, and spread room is still room a look cannot reach: one more level of looking, at fewer reads, leaves none.
Overflow holds the old keys
A cuckoo table that kicks blind under a cap of two leaves 9% of its keys in overflow, and every way of searching harder for room leaves fewer. Charged for its lookups as well as its insertions, the overflow was predicted to make a deeper search pay from ten lookups an insertion. It does not: blind kicks under a cap of two are the cheapest table up to thirty lookups an insertion when stored keys are asked for evenly, and at every mix measured when they are asked for by recency. Searching harder also moves keys into their second buckets, which every lookup pays for, and the keys a kick leaves in overflow are the old ones, not the new.
A kick that moves the oldest
A cuckoo table full to 95% makes room for a new key by kicking a resident of the full bucket to its other bucket, and blind kicks under a cap of two were the cheapest design for lookups as well as insertions — with every key drifting outward with age, so that overflow held the oldest keys. Choosing which resident to kick, the oldest rather than one at random, was predicted to bring a lookup asked by recency from 1.09 reads to about 1.04 and to change nothing for even lookups. It brings recency to 1.040, and even lookups fall too, from 1.420 to 1.331, because a table that always kicks the oldest sorts itself by age: the newest three tenths of the keys almost never leave their first buckets, and the oldest tenth is 56% in overflow. It is the cheapest design at every mix of lookups to insertions measured. The risk named, chains that lengthen, arrives only with the cap: at a cap of 32 the oldest kick leaves 6.6% of keys in overflow where random kicks leave none.
An old key is a crowded key
A cuckoo table that makes room by kicking each full bucket's oldest resident keeps its newest keys at home and brings a lookup asked by recency to 1.04 reads, the cheapest design measured — but only at a cap of two kicks. At a cap of 32 it leaves 6.6% of its keys in overflow where random kicks leave none, and the explanation offered was a loop: an old key kicked to its other bucket is old there too, and the next chain moves it back. Sparing every key the chain has already moved changes nothing at caps of two and eight and makes cap 32 slightly worse, 7.1%; sparing the last sixteen insertions' moves gets it to 5.0%. There was no loop. A kicked resident's other bucket has room 22% of the time when the resident is chosen at random and 7% when it is the oldest: in a table that always moves the oldest, a key grows old because both of its buckets stay full. Kicking the older of four drawn at random keeps much of the gain at a long cap, 1.055 reads by recency and 0.5% overflow, and still costs more than the oldest kick at a cap of two.
Named alongside it
The objects these essays reach for when they reach for this one.
Bloom filterHonest limitFalse-positive rateMeasured countThresholdBlocked filterCuckoo hashingHash tableLoad factorSpace time tradeLsm treeSpace accounting