What the machine does

A look whose answers are kept

A bit beside each resident of a cuckoo table, saying whether its other bucket had room, had to be bought by a read the blind chain never makes, and guided too few kicks to matter. The proposal joined it to the look: read a full bucket's residents' other buckets only when their answers are missing, keep the answers, and reuse them when a later chain arrives. Predicted: under 2% of keys in overflow at a cap of 32 for under six reads an insertion. Measured: 4.8% for 6.55. The answers a bucket keeps are the ones kicks write, and a kick can only write full, so 95% of kicks at that cap find no answer saying room. Re-reading the full answers empties the overflow, at 7.31 reads — three more than random kicks need for the same result. And the answers do not keep: one that says room is true a third of the time by the thousand insertions most of them wait, not much better than the 22% a random guess achieves.

A bucketed cuckoo table gives each key two buckets of eight slots. When a new key finds its first bucket full the table kicks one of the residents to that resident’s other bucket, which may be full in turn and send another on, up to a cap; a key the chain cannot place waits in a small overflow block, the arrangement the keys a capped chain leaves behind introduced. A kick that moves the oldest chose the resident to move by age, which keeps the newest keys at home and made a lookup asked mostly of recent keys the cheapest of any design at a cap of two. An old key is a crowded key found why the same rule failed at long caps: the resident that has sat longest is the one whose other bucket has been full longest, so a chain steered by age is steered into crowding, and at a cap of 32 it left 6.6% of keys in overflow where random kicks left none.

A bit that remembers room tried to steer by room instead, cheaply. A bit beside each resident would say whether its other bucket had room when last read, and the kick would move the oldest resident whose bit said room. The bit turned out not to be free. A blind chain reads only the bucket it kicks into, so the only bit it can write is the one for the key it has just moved — whose other bucket is the one it was just kicked out of, and full. A bit that says room had to be bought by reading every fresh key’s second bucket, about half a read an insertion, and at a cap of 32 it guided 4% of kicks and left 5.2% of keys in overflow for 6.8 reads.

That essay’s closing section proposed joining the bit to a kick that looks before it moves, the design that reads every resident’s other bucket before choosing. A look learns eight answers and throws them away. Keep them: when a chain arrives at a full bucket whose residents have no answer saying room, read the other buckets of the residents without an answer, as a look does, record each as room or full, and move the oldest resident whose answer says room. When a later chain arrives at the same bucket, use the answers instead of reading. The prediction was under 2% of keys in overflow at a cap of 32, for under six reads an insertion, because most chains would arrive at buckets whose answers were still fresh; and lookups by recency near 1.07, as the bit’s were. The risk was how fast the answers wear out at 95% load.

Three answers a resident can carry

Every resident now carries one of three answers: its other bucket had room when read, it was full, or nothing has been read. A fresh key placed in its first bucket carries nothing, so no read is bought at placement — the half read an insertion that the room bit spent on every key is gone. A key moved into a bucket by a kick carries “full”, as before, because its other bucket is the one it left and that bucket was full. A kick at a full bucket where no resident’s answer says room reads, once each, the other buckets of the residents with no answer, and keeps what it learns; then it moves the oldest resident whose answer says room, or, if none does, the oldest of all.

A second design asks whether the first is starved of answers rather than of reads. It does the same, except that a kick at a bucket with no answer saying room re-reads the residents whose answer says full as well as those with none: a bucket whose answers have all gone to “full” is looked at afresh every time a chain reaches it, and only answers that say room survive to be used later. Every other quantity is the earlier essays’: 16,384 slots in buckets of eight, filled to 95% and churned for eight times the table’s size — a random key deleted and a fresh one inserted, over and over — with reads an insertion counting every bucket read, lookups one read in a first bucket, two in a second and three in overflow.

The hero plate is the question the proposal named and could not answer in advance. At a cap of 32, a kept answer that says room and is used a few insertions after it was read is true between 36% and 62% of the time; by a thousand insertions or more it is true between 24% and 38% of the time, and that is where most kept answers are used, the median at about a thousand to two thousand insertions old. A random resident’s other bucket has room 22% of the time. A remembered answer is better than a guess, by a little, and gets worse the longer it is kept.

A bucket keeps the answers kicks write

At a cap of 32 the kept look moves the oldest resident with no answer saying room on 95% of kicks: the answers a bucket keeps are the ones kicks write, and a kick can only write "full"; re-reading those answers turns 89% of kicks into kicks that some answer chose — most of them an answer the same kick just boughtFor the kept look and the kept look that re-reads answers saying full, at 95% load: the share of kicks that moved a resident chosen by an answer read during the same kick, by an answer kept from an earlier kick, or — no answer saying room — the oldest resident. cap 2, kept: 17.1% fresh, 37.3% kept, 45.7% oldest; 0.14 looks an insertion buying 2.56 answers each; cap 2, re-read: 19.8% fresh, 79.7% kept, 0.5% oldest; 0.14 looks an insertion buying 8.00 answers each; cap 8, kept: 6.3% fresh, 11.6% kept, 82.2% oldest; 0.18 looks an insertion buying 2.04 answers each; cap 8, re-read: 27.9% fresh, 62.4% kept, 9.7% oldest; 0.56 looks an insertion buying 8.00 answers each; cap 32, kept: 2.0% fresh, 3.4% kept, 94.6% oldest; 0.17 looks an insertion buying 1.98 answers each; cap 32, re-read: 28.2% fresh, 61.0% kept, 10.8% oldest; 0.60 looks an insertion buying 8.00 answers each.an answer this kick boughtan answer kept from earlierno answer said room: the oldestshare of kickscap 2, kept look17%37%46%cap 2, full re-read20%80%cap 8, kept look12%82%cap 8, full re-read28%62%10%cap 32, kept look95%cap 32, full re-read28%61%11%95% load, buckets of eightwhat moved
Fig. 1 For the kept look and the kept look that re-reads answers saying full, the share of kicks that moved a resident chosen by an answer bought in the same kick, by an answer kept from an earlier kick, or by age with no answer saying room. Cap of 32, kept look: 2.0%, 3.4% and 94.6%.

At a cap of 32 the kept look moves the oldest resident, with no answer saying room, on 95% of its kicks: the answers a bucket keeps are the ones its kicks write, and a kick can only write “full”. The proposal pictured a bucket’s answers as the record of a look. In the table they are mostly the record of chains. A chain that passes through a bucket replaces one resident with the key it carries, and that key’s answer is “full”; by a cap of 32, chains have passed through most full buckets many times, and a bucket whose residents’ answers are all “full” or few "nothing"s triggers a look that buys, on average, two answers. The kept look makes 0.17 looks an insertion and each buys 1.98 answers; at a cap of 32 a kept answer saying room is found on 3.4% of kicks.

Re-reading the full answers changes the picture completely. Every kick that finds no answer saying room now reads all eight residents’ other buckets, so 89% of kicks at a cap of 32 are chosen by some answer; 28% of kicks use an answer bought by the same kick and 61% an answer kept from an earlier one. The design now really is the look the proposal described, with its answers kept, and the next plates measure what that look costs and buys. It makes 0.60 looks an insertion, eight answers each.

At a cap of two the difference is smaller, because a short chain rewrites few answers: there the kept look chooses by an answer on 54% of kicks, 37% of all kicks by an answer kept from earlier, and the re-reading design on 99.5%. The long caps are where the stale “full” answers pile up, and where the room the chains need is hardest to find.

Overflow at a cap of 32

At a cap of 32 the kept look leaves 4.8% of keys in overflow for 6.55 reads an insertion — not the predicted under 2% for under six; re-reading the answers that say full empties the overflow, 0.00%, for 7.31 reads, while random kicks at the same cap leave 0.01% for 4.23Keys in overflow and reads an insertion at 95% load: cap 2: random kick 9.26%, 1.627 reads; oldest kicked 10.94%, 1.610 reads; room bit 8.53%, 2.198 reads; kept look 8.22%, 2.019 reads; kept look, full re-read 7.05%, 2.783 reads. cap 8: random kick 2.66%, 2.803 reads; oldest kicked 7.84%, 2.935 reads; room bit 6.12%, 3.254 reads; kept look 5.35%, 3.117 reads; kept look, full re-read 0.34%, 6.922 reads. cap 32: random kick 0.01%, 4.226 reads; oldest kicked 6.62%, 7.098 reads; room bit 5.17%, 6.821 reads; kept look 4.84%, 6.555 reads; kept look, full re-read 0.00%, 7.309 reads.cap of 29.26% · 1.63 reads10.94% · 1.61 reads8.53% · 2.20 reads8.22% · 2.02 reads7.05% · 2.78 readscap of 82.66% · 2.80 reads7.84% · 2.93 reads6.12% · 3.25 reads5.35% · 3.12 reads0.34% · 6.92 readscap of 320.01% · 4.23 reads6.62% · 7.10 reads5.17% · 6.82 reads4.84% · 6.55 reads0.00% · 7.31 readsrandom kickoldest kickedroom bitkept lookkept look, full re-readshare of keys in overflow · reads an insertion95% load, buckets of eightoverflow · insertion reads
Fig. 2 Keys in overflow and reads an insertion at caps of 2, 8 and 32 for random kicks, the oldest kicked, the room bit, the kept look and the kept look re-reading its full answers. Cap of 32: random 0.01% for 4.23 reads; kept look 4.84% for 6.55; re-read 0.00% for 7.31.

At a cap of 32 the kept look leaves 4.8% of keys in overflow for 6.55 reads an insertion — not the predicted under 2% for under six; re-reading the answers that say full empties the overflow, 0.00%, for 7.31 reads, while random kicks at the same cap leave 0.01% for 4.23. The prediction fails on both of its numbers, and the reason is the previous plate. A kick that has no answer saying room moves the oldest resident, and the kept look is, 95% of the time at that cap, the oldest kick of an old key is a crowded key with a few reads added. It leaves 4.8% of keys in overflow where the oldest kick left 6.6% and the room bit 5.2%, an improvement of the same small size as the bit’s, for fewer reads than either.

The re-reading design is the first steering-by-room design to empty the overflow at long caps, and the reads are where it pays. At a cap of 8 it leaves 0.34% for 6.92 reads; at 32 nothing measurable for 7.31. Its chains are short — 1.5 kicks an insertion at a cap of 32, against random kicks’ 3.2 — because it nearly always moves a key whose other bucket really has room. But to know which key that is, it reads eight buckets at most kicks, 4.8 reads an insertion on answers alone, and a short chain of informed kicks costs more than a long chain of blind ones. Random kicks reach the same empty overflow at a cap of 32 for three reads fewer.

That is the trade a kick that looks before it moves found for the look itself, now found again with the answers kept. Keeping answers was meant to make the look cheap by making most looks unnecessary. In the kept look, most looks are unnecessary but the answers that make them so say “full”; in the re-reading design, the answers say room but are kept too long to be true.

What the table remembers

What the table remembers when the churn ends: under the kept look at a cap of 32, 83% of residents carry an answer saying full and 4% one saying room; 37% of the full answers and 63% of the room answers are no longer trueEvery resident of the table at the end of the churn, at 95% load, by its kept answer — room or full — and whether that answer is still true, or no answer: cap 2, kept: room, true 4.7%, room, now false 5.0%, full, true 32.9%, full, now false 35.7%, no answer 21.8%; cap 2, re-read: room, true 12.5%, room, now false 12.4%, full, true 27.3%, full, now false 22.1%, no answer 25.7%; cap 8, kept: room, true 2.1%, room, now false 3.3%, full, true 47.5%, full, now false 33.6%, no answer 13.6%; cap 8, re-read: room, true 5.0%, room, now false 12.6%, full, true 56.1%, full, now false 16.2%, no answer 10.1%; cap 32, kept: room, true 1.7%, room, now false 2.8%, full, true 52.4%, full, now false 30.8%, no answer 12.4%; cap 32, re-read: room, true 4.3%, room, now false 11.9%, full, true 58.9%, full, now false 15.2%, no answer 9.6%.room, trueroom, now falsefull, truefull, now falseno answercap 2, kept look33%36%22%cap 2, full re-read12%12%27%22%26%cap 8, kept look47%34%14%cap 8, full re-read13%56%16%10%cap 32, kept look52%31%12%cap 32, full re-read12%59%15%10%95% load, end of churnresidents' answers
Fig. 3 Every resident at the end of the churn by its kept answer — room or full — and whether it is still true, or no answer. Kept look at a cap of 32: room and true 1.7%, room and false 2.8%, full and true 52.4%, full and false 30.8%, no answer 12.4%.

When the churn ends, 83% of residents under the kept look at a cap of 32 carry an answer saying full and 4% one saying room; 37% of the full answers and 63% of the room answers are no longer true. The plate is the table’s memory at a moment, and more than a third of what it remembers is wrong. The “full” answers are mostly right because at 95% load most buckets are full most of the time, so an answer that says full is right for the same reason a guess of full would be. The “room” answers are the ones that matter, and they are the ones that decay: a bucket with room at 95% load has one or two free slots, and the next key to land there takes one.

The re-reading design remembers more room — 16% of residents carry an answer saying room — and it is wrong about 73% of those. Its answers are bought more often and kept as long, so it holds more of them and each is no fresher. That is the arithmetic behind the hero plate’s curve: the share of room answers still true falls from between two and three in five at a few insertions to about a quarter by the thousand at which most are used, and the second figure is most of what a kept answer is.

Deletions are part of the same churn. A key deleted from a bucket makes room there, and every resident elsewhere whose other bucket that is now carries a wrong “full”. Under the kept look nothing ever re-reads those answers, which is why 31% of all residents carry a false “full” and why the kept look, alone among the designs here, has more wrong answers than right ones about full buckets at a cap of two.

Lookups the kept answers protect

A lookup by recency reads 1.054, 1.050, 1.049 under the kept look at caps of 2, 8, 32 — under the room bit's at every cap, and still over the plain oldest kick's 1.040, 1.039, 1.037; evenly, the kept look that re-reads its full answers reads the fewest at every cap, 1.305, 1.272, 1.266Reads a lookup at 95% load — one for a key in its first bucket, two in its second, three in overflow — weighted by recency and evenly: cap 2: random kick 1.084 and 1.420; oldest kicked 1.040 and 1.331; room bit 1.072 and 1.402; kept look 1.054 and 1.321; kept look, full re-read 1.046 and 1.305. cap 8: random kick 1.110 and 1.436; oldest kicked 1.039 and 1.313; room bit 1.068 and 1.366; kept look 1.050 and 1.298; kept look, full re-read 1.061 and 1.272. cap 32: random kick 1.124 and 1.426; oldest kicked 1.037 and 1.295; room bit 1.064 and 1.352; kept look 1.049 and 1.297; kept look, full re-read 1.059 and 1.266.cap of 21.084 · 1.420 evenly1.040 · 1.331 evenly1.072 · 1.402 evenly1.054 · 1.321 evenly1.046 · 1.305 evenlycap of 81.110 · 1.436 evenly1.039 · 1.313 evenly1.068 · 1.366 evenly1.050 · 1.298 evenly1.061 · 1.272 evenlycap of 321.124 · 1.426 evenly1.037 · 1.295 evenly1.064 · 1.352 evenly1.049 · 1.297 evenly1.059 · 1.266 evenlyrandom kickoldest kickedroom bitkept lookkept look, full re-readreads a lookup beyond the first, by recency · and evenly95% load, buckets of eightbars start at one read
Fig. 4 Reads a lookup by recency — the newest key asked most — and evenly, at caps of 2, 8 and 32, every design. Kept look: 1.054, 1.050 and 1.049 by recency. Oldest kicked: 1.040, 1.039 and 1.037.

A lookup by recency reads 1.054, 1.050 and 1.049 under the kept look at caps of 2, 8 and 32 — under the room bit’s at every cap and over the plain oldest kick’s 1.040, 1.039 and 1.037; evenly, the kept look that re-reads its full answers reads the fewest at every cap. The proposal predicted lookups near 1.07, the room bit’s, and the kept look does better than that. Its kicks move the oldest resident most of the time, so it keeps most of the oldest kick’s sorting of the table by age, and it adds a few kicks steered by room that keep keys out of overflow; the newest keys stay at home almost as well as under the oldest kick.

The even lookup tells the other half. A key asked as often as any other costs one read in its first bucket, two in its second and three in overflow, and under random kicks at a cap of 32 a lookup reads 1.426 evenly — more keys in second buckets, because random kicks spread residents across both. The re-reading design reads 1.266, the fewest of any design at that cap: its kicks, chosen by room, put fewer keys in second buckets and none in overflow. A table whose lookups are spread over its keys rather than concentrated on its newest is the case where steering by room pays.

Every design, priced together

Charged for an insertion and its lookups together, the cheapest design by recency is the oldest kick at a cap of two at every mix from 0.1 to 100 lookups an insertion; with lookups spread evenly over the keys a kept look is cheapest only at 100Reads an insertion plus mix lookups at 95% load, for every design at caps of 2, 8, 32: the cheapest at each mix with lookups by recency and with lookups evenly. 0.1: by recency oldest kicked, cap 2 1.714; evenly oldest kicked, cap 2 1.744; 0.3: by recency oldest kicked, cap 2 1.923; evenly oldest kicked, cap 2 2.010; 1: by recency oldest kicked, cap 2 2.651; evenly oldest kicked, cap 2 2.942; 3: by recency oldest kicked, cap 2 4.731; evenly oldest kicked, cap 2 5.605; 10: by recency oldest kicked, cap 2 12.014; evenly oldest kicked, cap 2 14.924; 30: by recency oldest kicked, cap 2 32.820; evenly oldest kicked, cap 2 41.552; 100: by recency oldest kicked, cap 2 105.644; evenly kept look, cap 8 132.954.cheapest, lookups by recencycheapest, lookups evenly0.1 lookupsoldest kicked, cap 2oldest kicked, cap 20.3 lookupsoldest kicked, cap 2oldest kicked, cap 21 lookupsoldest kicked, cap 2oldest kicked, cap 23 lookupsoldest kicked, cap 2oldest kicked, cap 210 lookupsoldest kicked, cap 2oldest kicked, cap 230 lookupsoldest kicked, cap 2oldest kicked, cap 2100 lookupsoldest kicked, cap 2kept look, cap 895% loadper insertion and its lookups
Fig. 5 The cheapest design at each mix of lookups an insertion, from 0.1 to 100, with lookups by recency and with lookups evenly, every design at caps of 2, 8 and 32. By recency the oldest kick at a cap of two wins every mix; evenly, the kept look at a cap of 8 wins only at 100.

Charged for an insertion and its lookups together, the cheapest design by recency is the oldest kick at a cap of two at every mix from 0.1 to 100 lookups an insertion; with lookups spread evenly over the keys a kept look is cheapest only at a hundred lookups an insertion, by three thousandths of a read an operation. This is the measure the strand has used to settle which design a table should run. The oldest kick at a cap of two keeps winning by recency because it spends nothing on reading and keeps the keys that are asked at home; the overflow it leaves, 10.9% of keys, is paid only by lookups of old keys, which recency rarely asks.

Evenly, the kept look at a cap of 8 wins at a hundred lookups an insertion: its lookups read 1.298 against the oldest kick’s 1.331 at a cap of two, and at a hundred lookups an operation that difference outweighs its 1.5 extra reads an insertion. It is the one mix in fourteen that any design steered by room has won in this strand, and it is a narrow win, 132.95 reads against 133.26 for the next design. Overflow holds the old keys found the same structure: which design is cheapest is a statement about who asks, and room matters to a table only when its old keys are asked as often as its new ones.

Room moves faster than a memory of it

The question the proposal ended on was whether a cuckoo table can remember where its room is at any price below a look an insertion, or whether at 95% load the room moves too fast. The plates answer it plainly. A kept answer that says room is right about half the time when it is a few insertions old and about a third of the time at the ages at which kept answers are used; a design that keeps answers cheaply keeps mostly “full”, and a design that keeps answers saying room has to buy them at nearly a look an insertion. Neither is cheaper than the blind kick that reads only the bucket it moves into and asks nothing of memory.

What a kept answer remembers is a fact about one slot in a bucket with one or two free. Room the chains could not reach showed that at this load the free slots are a small and shifting set, and every insertion either takes one or moves one; a memory of where one was is out of date after a few insertions that land near it. A table with more slack — at 90% load, say — would have more free slots per bucket and slower decay, and a kept answer would stay true longer. That is a different table, and the strand has measured its designs at 95% throughout because that is where cuckoo tables are pressed hardest.

The positive result is the re-reading design’s lookups. A table that pays for its insertions in reads and is asked evenly over its keys gets the fewest reads a lookup of any design, and no overflow at long caps. That is a real setting — a table built once and read many times, uniformly — and the kept answers are worth something there, though not because they are kept: they are worth what a look is worth, and the keeping spares about three looks in five.

What the churn does not measure

One load, one bucket size. 95% load in buckets of eight. At lower loads the room changes more slowly, and kept answers would decay more slowly; that was not measured.

One kind of churn. Uniform deletions of stored keys, each followed by one fresh insertion. A workload that deletes the newest keys, or inserts in bursts, would change both which answers go stale and how fast.

Reads counted, not timed. Every bucket read costs one, whether it is the next bucket in a chain or one of eight read by a look; on a machine the eight reads of a look are independent and can overlap, which a count does not show.

Still open: answers that expire

The plates say a kept answer is worth keeping for a few dozen insertions and nearly worthless after a thousand, and that both designs here keep answers forever — the kept look its "full"s, the re-reading one its "room"s. An answer could carry its age. Store beside each resident the insertion count at which its answer was read, coarsened to a few bits, and treat an answer older than some horizon HH as no answer at all, so a bucket re-reads exactly the answers old enough to have gone stale and keeps the young ones.

The measurement that follows runs that expiring answer at horizons of 16, 64 and 256 insertions at caps of 8 and 32, charging the bits for the ages in the table’s space and every read to its insertion. The prediction is that at a horizon of 64 and a cap of 32 it leaves under 1% of keys in overflow for under six reads an insertion — fewer than the re-reading design, since about half its looks are of answers too young to need it, and more true room answers than either design here, since none is older than 64 insertions. It could fail on the horizon itself: the hero plate shows answers losing truth from the first few insertions, so a horizon short enough to keep them true may be short enough that nearly every answer has expired when a chain reaches it, and the design becomes a look at every kick. The question is whether the room of a nearly full table has any memory at all that is worth its bits, or whether at 95% load the only answer that is right is the one read just now.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

The objects this essay names

Each one links to every other essay that touches it.

Cuckoo hashingDesign parameterHash tableLoad factorMeasured countWorkload