The thread: The structure decides the count — page 3
Three savings on one structure
A factor of eleven on an extension, a factor of seven on a branching search, and a sixth of the bits. Applied to one bidirectional index they do not give a factor of seventy-seven, and the reason is that two of the three are the same saving.
What is taught wronglyA walk that does not prune
Remove the emptiness test and the descent visits every node of the tree, returns exactly the same symbols with exactly the same intervals, and costs sixty per cent more. No test of the answer can see it.
StructuresA position split in two
Write each sorted position as a high part and a low part. Store the low parts packed and the high parts as a bit vector in which the k-th one sits at position (p >> w) + k. A select on that vector and a low read recover any position.
StructuresEvery copy points right
A greedy self-referential parse chooses each phrase's source from text already produced, so an occurrence copied from another lies strictly to its right. That one fact removes a visited set from a propagation, exactly as a left-first walk removed an array one strand ago.
The other axisHalf an index is three permutations
A phrase index stores a length, a source and a literal per phrase — and three orderings of its boundaries, at forty-five per cent of the structure. One of the three is the inverse of another, and nothing needs both at once.
StructuresTwo states per operator
Thompson's construction adds a bounded number of states per rule and no rule copies a sub-machine, so the machine is linear in the expression and is built in linear time. Every exponential in this field is somewhere else.
What the machine doesA 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.
What the libraries doThe 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.
What the machine doesEntries 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 other axisSparse on average, dense where it gathers
The r-index keeps one suffix-array value for every run of its transform and prices the set as Elias–Fano: on 32 exact copies of 2,048 characters that is 666 values among 65,537 positions at 9.04 bits a value, as though they were spread evenly. They are not — 663 sit in one copy. Cut into chunks of 32 values, each held by whichever of a bitmap, its own Elias–Fano or a run is cheapest, the same set costs 4.48 bits a value, under the 8.05 that any representation of an arbitrary set of that size must spend on some set. At a divergence of 0.0005 the saving is a fifth, and from one character in five hundred it is nothing but the select directory, which the chunks replace with reading. On the scattered marks of an ordinary index the partition saves only that directory too.
What the machine doesThe 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.
What the machine doesSpare 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.
The other axisCuts that follow the gathering
Cutting an r-index's run-start values into chunks of a fixed count left chunk edges inside the places the values gather. Choosing the cuts as a shortest path through the sorted values was predicted to save a further tenth on exact copies by cutting once at each edge of the gathering. It cuts there, and saves more than a quarter: two chunks, one of them a bitmap of 664 values that a select must scan from its start. Capped at the chunk's old size, the optimum keeps the reads and saves 9% on exact copies and 15% at a divergence of 0.0005. On moderately drifted copies the uncapped optimum is smaller and cheap to read at once.
What the machine doesThe 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 other axisA select that starts near its answer
The cheapest partition of an r-index's run-start values held exact copies in two chunks, one a bitmap of 664 values that every select scanned from its start: 1,065 bits read a select. Capping the chunks bought the reads back by giving up the saving. A select sample every 64 values inside each chunk, its bits charged in the same shortest path, was predicted to bring the uncapped optimum under 150 bits a select for under 3.5 bits a value. It reads 111 for 3.45, where the cap that reads as little costs 3.68. And the middle divergences, predicted to be untouched because their chunks were short, lose two fifths of their reads to the same samples.
What the libraries doThe 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.
What the machine doesThe 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 other axisA sample that has to be found
A select sample every 64 values inside the cheapest partition of an r-index's run-start values cut a select's reads from 1,065 bits to 111 on exact copies. Samples by count bound how many values a select passes, not how many bits it reads, so samples every 128 bits of a chunk's vector were predicted to read a third less on the sparse, drifted sets at the same cost. They bound the scan as promised, but a rank sample does not say which sample a select needs, and finding it by binary search costs a select up to a third of what it reads. The two kinds of sample end up on one frontier, and the rank samples' advantage is that they come in finer steps.
What the libraries doThe 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.
What the machine doesThe 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.
What the machine doesRoom 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.
What the libraries doPieces 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.
What the machine doesA 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.
What the libraries doHow 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.
What the machine doesA 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.
What the libraries doThe 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.
What the machine doesOverflow 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.
What the libraries doThe 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.
What the machine doesA 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.
What the machine doesAn 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.