A bit that remembers room

A bucketed cuckoo table gives each key two buckets of eight slots, and when a new key finds its first bucket full the table moves one of that bucket’s residents to the resident’s other bucket, which may be full in turn and send another on, up to a cap of kicks; a key the chain cannot place waits in a small overflow block. A kick that moves the oldest chose the resident by age. Moving the oldest rather than a random one sorted the table by age, kept the newest keys in their first buckets, and brought a lookup asked mostly of recent keys from 1.084 bucket reads to 1.040 at 95% load — under a cap of two kicks the cheapest design measured.

At longer caps it failed. With a cap of 32, random kicks left no keys in overflow and the oldest kick left 6.6%, and an old key is a crowded key found out why. It had blamed a loop — an old key kicked away and kicked straight back — and sparing recently moved keys did nothing. The reason was the destination. A random resident’s other bucket had room 22% of the time at that cap; the oldest resident’s, 7%. A key that has sat in a bucket longest is a key whose other bucket has been full the longest, so age, under the oldest kick, measures crowding, and a chain steered by age is steered into the crowded corners of the table.

That essay’s closing section proposed reading the crowding directly. Each bucket could keep, beside its residents, one bit per resident saying whether that resident’s other bucket had room the last time it was checked, refreshed whenever a chain passed through; the kick would move the oldest resident whose bit said room, and the oldest overall if none did. The proposal called this a kick that “reads nothing extra”. The prediction was that at a cap of 32 it would leave under 1% of keys in overflow for under five reads an insertion, keeping a lookup by recency under 1.045, and that at a cap of two it would match the plain oldest kick. The named risk was staleness: at 95% load a bucket with room fills within a few insertions.

What a chain can know #

Before anything was measured, building the bit exposed a problem the proposal had passed over. A bit about a resident’s other bucket can be written only by reading that bucket, and a blind chain reads exactly one bucket a step: the one it kicks into. It learns whether that bucket has room, and the bucket’s residents stay where they are, carrying no information about where they would go. The one key whose bit the chain can set for nothing is the key it has just placed — and that key’s other bucket is the bucket it was just kicked out of, which the chain has just filled. Every bit a blind chain writes for free is 0.

So a bit that says room has to be bought. The version measured here buys it at the only moment a key’s other bucket is not known to be full: when a fresh key is placed directly in its first bucket, the table reads the key’s second bucket — one more bucket read, charged to the insertion — and records whether it had room. A fresh key that enters by kicking a resident out gets 0, since its second bucket is unread, and every key placed by a kick gets 0 for the reason above. The kick moves the oldest resident with a 1, and if no resident has one, the oldest of all. Everything else is the earlier essays’: 16,384 slots in buckets of eight, filled to 95% and churned eight times its capacity by deleting a random key and inserting a fresh one, with insertion reads and lookups charged as before — one bucket read for a key in its first bucket, two in its second, three in overflow.

A memory that is mostly right #

When the bit chooses the key to move, that key’s other bucket has room 66%, 61% and 59% of the time at caps of 2, 8 and 32 — the memory is mostly right — but it chooses too rarely to matter: over all kicks the guided table finds room 54%, 26% and 9%, against random kicks’ 53%, 32% and 22% and the oldest kick’s 46%, 21% and 7%. The risk the proposal named turns out to be the smaller of the two problems. A bit written when a key was placed, and read some time later when a chain arrives at that key’s bucket, is right about three times in five; a bucket’s room does change in between, but not so fast that the memory is worthless. Three in five is several times what either the random or the oldest choice gets at the longer caps.

The trouble is the other two in five of the kicks at a cap of two, and nearly all of them at 32. Those are kicks into buckets where no resident carries a 1, and there the rule moves the oldest of all, as the plain oldest kick does — so at the longer caps the guided table finds room almost exactly as often as the oldest kick, 9% against 7%. The memory is accurate and mostly absent.

How many kicks a bit could guide #

The bit guides 40%, 12% and 4% of kicks at caps of 2, 8 and 32: a moved key’s bit is always 0, since its other bucket is the one it left, so the longer the chains the fewer residents carry a 1 — while writing the bits costs 0.57, 0.48 and 0.45 reads an insertion. The decline is the arithmetic of the first section working itself out. Every kick replaces a resident with the key being placed, and that key’s bit is 0; every chain of length $k$ writes $k$ zeros into $k$ buckets. At a cap of two, chains are short and many buckets keep a fresh key or two with a 1. At a cap of 32, chains average more than five kicks an insertion, and the 1s are kicked out faster than fresh keys arrive to replace them.

The bits’ price falls slightly as the cap grows, for the same reason: a fresh key pays for its bit only when it lands in its first bucket directly, and at long caps a larger share of fresh keys land by kicking. At every cap the price is close to half a read an insertion, which at a cap of two is a third more than the whole of the plain oldest kick’s insertion cost, 1.61 reads. The proposal’s “reads nothing extra” was the claim that broke first, and it broke by a third.

Overflow at a long cap #

At a cap of 32 the room bit leaves 5.2% of the keys in overflow for 6.82 reads an insertion — not the predicted under 1% for under five — against the plain oldest kick’s 6.6% for 7.10 and random kicks’ none for 4.23. The prediction fails on both counts and by large margins. The bit moves the oldest kick a little way toward random kicks: fewer keys in overflow, slightly fewer reads, because the 4% of kicks it guides find room three times as often as the oldest kick’s. It moves it a fifth of the way. Random kicks, which choose nothing, still do best at this cap by every measure of insertion.

At a cap of two the bit does what no other kick here does: it leaves fewer keys in overflow than random kicks, 8.5% against 9.3%. That is the one place where the bit guides enough kicks to change the table, and where the rule’s prediction — that it would match the oldest kick — is wrong in the other direction: the oldest kick at a cap of two leaves 10.9%. But the insertion reads include the bits’ price, 2.20 against 1.61, and for a cap-two table the bits cost more than the overflow they save.

What steering by room costs the lookups #

A lookup by recency reads 1.072, 1.068 and 1.064 under the room bit at caps of 2, 8 and 32, between random kicks and the plain oldest kick’s 1.040, 1.039 and 1.037: a kick steered by room is a kick no longer steered by age, and newer keys are moved in its place. The third prediction, a lookup by recency under 1.045, fails at every cap, and the reason is built into the rule. The residents with a 1 are fresh keys that landed in their first buckets and have never been moved — the very keys the oldest kick protected. Choosing the oldest of them is choosing a key younger than the bucket’s oldest, and a key moved to its second bucket costs a lookup two reads instead of one. Under the bit the table holds 23% of its keys in their second buckets at a cap of two, where the oldest kick holds 11%.

The even lookup tells the same story without the weighting: 1.402 at a cap of two, against the oldest kick’s 1.331 and random kicks’ 1.420. The rule is closer to random than to the design it was meant to improve, because it spends its choice on a different property. Age and room pull the kick in different directions, and a rule that takes room when it can and age when it cannot gets some of each benefit and all of neither.

Every design, priced together #

Charged for an insertion and its lookups by recency together, the room-bit kick is the cheapest design at no mix from 0.1 to 100 lookups an insertion; its best setting trails the best design by between 0.04 and 0.54 reads an operation. At every mix the cheapest design is still the plain oldest kick under a cap of two, which overflow holds the old keys had found cheapest of the random designs’ rivals, and a kick that moves the oldest made cheaper still. The room bit’s best setting is also at a cap of two, and it loses most where insertions dominate — half a read an operation at one lookup an insertion or fewer, which is the bits’ price almost exactly — and least where lookups dominate, since its lookups are only three hundredths dearer.

So the bit loses twice: once at insertion, for the read that writes it, and again at lookup, for the newer keys it moves away from home. Neither loss is large. Together they make it the wrong design at every workload measured.

Worth most where it is rarest #

The plates contain a crossing that neither the proposal nor its risk anticipated. The bit’s value as information is how much better it does than the choice it replaces — the oldest kick, which is what the rule falls back to — and that rises with the cap: at a cap of two the key the bit chooses finds room 66% of the time against the oldest key’s 46%, twenty points; at a cap of eight, 61% against 21%, forty points; at a cap of 32, 59% against 7%, fifty-one points. Long chains are the ones that wander into crowded buckets, and there a memory of where room was is worth the most.

Its coverage falls along exactly the same axis — 40%, 12%, 4% of kicks — because long chains are also the ones that write zeros fastest. The product of the two, the extra kicks that find room because a bit was there, is small at every cap: about eight kicks in a hundred at a cap of two, five at eight, two at 32 — which is, to the point, the guided table’s lead over the oldest kick in the first plate. That is the whole of what the bit adds, and it is why the guided table’s room-after-kick sits so close to its unguided neighbour’s.

Staleness, the named risk, is visible in the gap between the bit’s three in five and certainty. A bit written when a fresh key arrived is read when a later chain reaches the same bucket, and at 95% load, in two cases in five, some other chain has by then taken that bucket’s last free slot. A fresher memory would close part of that gap and leave the coverage untouched, so freshness is not where the bit’s shortfall lies.

Where the information was #

The plates leave the proposal’s idea standing and its premise refuted. The idea was that a table could steer its kicks by where its room is rather than by a proxy for it, and the bit, when it has something to say, is right three times as often as age is at the longer caps. The premise was that the information comes free with the chains, and it does not, because a blind chain is blind in exactly the direction the bit needs: it sees where a key is going, never where the keys it leaves could go.

There is one operation in the table that reads every resident’s other bucket, and it is the look. A kick that looks before it moves introduced it: before kicking anyone, read each resident’s other bucket and move one that has room, if any does. The look is expensive — the look that moved the oldest resident with room cost 7.70 reads an insertion — and its answers are thrown away when the insertion ends. A look that spreads the room moved whichever resident left the most room behind, and threw those answers away too. A look is the one moment the bits proposed here could be written correctly for a whole bucket at once.

Room the chains could not reach found, under a cap of two at 95% load, 13.8% of the table’s entries standing empty while 9.2% of its keys waited outside their buckets. That is the same fact seen from the other end: room exists, and the operations that move keys do not learn where it is. The keys a capped chain leaves behind priced the search that does not know, finding five sixths of the bytes an insertion moves at that load in its kick chain, and most of them in the chain’s tail.

What the replay does not measure #

One way to buy the bit. The bit is set by one read when a fresh key lands in its first bucket. A table could instead refresh every resident’s bit whenever its bucket is read during a chain, at the cost of reading eight other buckets, which is a look by another name.

One table. 16,384 slots, buckets of eight, 95% load, one churn — the layout the bucket that fits a line chose so that a lookup never touches more than two cache lines and the table builds past 95%. At lower loads, room lasts longer, the bits would be right more often, and more fresh keys would land directly and buy one; at higher loads the reverse.

Reads, not time. A bit read and a bucket read are charged as the replay charges them, and the bit itself is not charged as space: one bit a slot, a sixty-fourth of a slot of eight-byte keys, which no plate here counts.

Still open: a look whose answers are kept #

The bit fails because the chains cannot write it, and the look writes nothing it learns. Join them. Let the table look only when a bucket’s stored answers are missing, and keep what it learns: when an insertion meets a full bucket whose residents have no bits, it reads their other buckets once, as the look does, records one bit per resident, and uses them; when a later chain arrives at the same bucket, it reads the bits instead of the buckets, and moves the oldest resident with a 1. A kick into a bucket clears the moved-in key’s bit, as before, so a bucket’s answers wear out as chains pass and are bought again when they run out.

The measurement that follows runs that kept look at caps of two, eight and 32, charging every look’s reads to the insertion that made it. The prediction is that at a cap of 32 it leaves under 2% of keys in overflow for under six reads an insertion, because most chains arrive at a bucket whose answers are still fresh, and that its lookups by recency stay near 1.07, as the bit’s did. It could fail on how fast answers wear out: at 95% load, a bucket’s room may change after a handful of insertions, and if the kept answers are mostly stale when used, the table pays for looks it cannot use. The question is whether a cuckoo table can remember where its room is at any price below a look per insertion, or whether at this load the room moves too fast for any memory to keep up.