Algorithms & Data Structures
the bound is a claim, and it is checkable
Theme

The thread: The structure decides the count — page 3

Page 3 of 3, continuing the same thread in the same order.
a second hash, unordered0.054 entries read on an absent key14.435.79 storedthe bits below the bucket, unordered0.059 entries read on an absent key14.435.79 storedthe bits below the bucket, sorted0.057 entries read on an absent key8.975.21 storedthe bucket's own bits, sorted5.743 entries read on an absent key11.275.80 storedtag comparisons an absent key's lookup makes8,192 slots · buckets of 8 · 8-bit tags38% fewer What the machine does

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.

 phrases examined per probethe linear scan207.0sorted, with a running maximum10.9 — 19xthe running maximum costs 2,821 bits — 21.6% of the index40 of 40 positions checked, and the two agree at all of them238 phrases · 6,144 characters19x on the scan What the libraries do

The scan the order does not touch

Two hundred and seven phrases examined per probe, against eleven. A running maximum of the source regions' right ends lets a leftward walk stop for good, and it costs twenty-two per cent more bits.

 501001500.2000.4000.6000.800load: keys held ÷ slotsbytes held per keythe entry, 32 bytesslotted entriespacked, a pointer a bucketpacked, groups of 4 bucketspacked, groups of 1616,384 slots, buckets of 8, 32-byte entrieslabels at the lowest load What the machine does

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.

 1248163210010³spare entries a group of 16 buckets keepsbytes moved an insertionslack at the endslack spread, region rewrittenslack spread, nearest gapborrowedslotsload 0.5, groups of 16dashed: the slotted layout What the machine does

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.

 05001e+31.5e+3load when the insertion is madebytes moved an insertion50%70%90%95%spare divided evenlyspare by recent insertionsspare by room leftfixed slots16 spare a region of sixteen bucketsdashed: fixed slots What the machine does

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.

 05001e+31.5e+3load when the insertion is madebytes moved an insertion50%70%90%95%no capcap 2, overflow in the sparecap 2, overflow in a blocksixteen spare a region, divided by room leftcharged since the previous tenth What the machine does

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.

 1/41/81/161/641/2561/10240.10.3131030buffer, share of the inputmoves a keythe libraryruns read, no trimruns read, trimmedsixteen batches, 5% overlap, 65,536 keysschedule smallest-first What the libraries do

The skip the split already made

A stable merge with too small a buffer is split by rotation, and the rotation was proposed to be the waste: gallop from each end of a merge first, set aside what is already in place, and rotate only the rest. On a sorted file with late arrivals the gallop sets aside two thirds of the keys in its split merges and saves half a per cent of the moves, because the library's split — halve one run, binary-search the other — had already found those stretches by bisection and moved nothing there. Where the gallop pays is the merge that fits the buffer, which copies its whole shorter run out and back: on sixteen overlapping batches it takes the sort from 1.92 moves a key to 0.13, and makes a larger buffer stop costing more.

 filter bits for each overflow keyfailed lookups that reach a block0246810120%25%50%75%100%at 95% loadat 90% loadone filter16,384 absent keys, cap of twodashed: one Bloom filter at those bits What the machine does

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.

 125102050buffer, as a share of the inputwrites ÷ the floor1/41/161/641/2561/1024sixteen batches, 5% overlapa random tenth appendeda late tenth appendedfour runssixteen runsrandom keys65,536 keys, trimmed sortone: the floor itself What the libraries do

The moves no stable sort can skip

Any sort must move every key that starts out of place, and with one spare cell it must spend one more move on each cycle of the permutation. Against that floor, a stable merge sort trimmed to the keys not already in place moves 1.46 times the least possible on records written in overlapping batches — the two thirds the prediction named, and for its reason. On a sorted file with a late tenth appended it was predicted within twice the floor and moves 15 times it, because the late tenth arrives in random order and sorting it among itself is two thirds of the work.

 00.0200.0400.0600.0800.10002468operations, in multiples of the table's 16,384 entriesshare of keys in overflowkeys stay, 9.2%home at every deletion, 4.0%home when open, 4.9%16,384 entries, buckets of eight, cap of two95% load What the machine does

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.

All threads