An old key is a crowded key

A kick that moves the oldest changed one choice in a cuckoo table. When a new key finds its first bucket full, the table moves a resident of that bucket to the resident’s other bucket, which may be full and send another on, up to a cap of kicks; a key the chain cannot place waits in a small overflow block. Moving the oldest resident rather than one at random sorted the table by age. The newest three tenths of the keys almost never left their first buckets, a lookup asked mostly of recent keys fell from 1.084 bucket reads to 1.040 at 95% load, and even lookups fell too, from 1.420 to 1.331, since fewer keys in all sat away from home. Under a cap of two kicks it was the cheapest design at every mix of lookups to insertions measured.

At longer caps it went wrong. A random chain allowed 32 kicks almost always finds room, and leaves 0.01% of the keys in overflow; an oldest chain allowed 32 kicks left 6.6%, for 6.10 kicks an insertion against 3.23. That essay offered an explanation the counts allowed but did not show: the oldest kick keeps choosing keys it has just moved, since a key kicked into its other bucket is old, so it is likely to be the oldest there and to be moved back by the next chain through that bucket. Its closing section proposed sparing such keys — the oldest resident not moved within the last few insertions, or not moved by this chain — and predicted that at a cap of 32 the spared kick would leave under 1% of keys in overflow for under four kicks an insertion, keeping a lookup by recency near 1.04, with nothing changed at a cap of two. It named the way to fail: if the repeated moves were spread across chains far apart, a short memory would not see them, and the trouble would be a property of always choosing by age.

Three memories #

The table, churn and charges are the earlier essays’: 16,384 keys in buckets of eight at 95% load, churned eight rounds so that what is measured is a steady state, a lookup charged one, two or three bucket reads for a key in its first bucket, its second or overflow, and asked by recency in proportion to $1/(r + 1)$ or evenly. A key not stored is charged both buckets and its region’s overflow block, if the block holds anything.

Three memories were given the oldest kick. Under the first, a chain passes over any resident it has already moved and takes the oldest of the rest. Under the second, the kick passes over any resident moved by the previous insertion’s chain or this one. Under the third, any resident moved within the last sixteen insertions. If every resident of a bucket was spared, the kick would take the oldest regardless; that fallback was counted, and never happened. A second count was added for every chain: whether the key just kicked found room in its other bucket, which is the event that ends a chain.

No loop to break #

Sparing the keys an oldest kick has just moved changes almost nothing at caps of two and eight and little at 32: sparing this chain’s moves leaves 7.1% of the keys in overflow against 6.6%, sparing the last sixteen insertions’ 5.0% — the long chains were not looping. At a cap of two the chain’s memory cannot matter, since a chain of two kicks visits three buckets and almost never returns to one of them, and the table is identical to the bit. At a cap of 32 a chain can return, and sparing its own moves makes it slightly worse, which says that the keys it would have moved back were, on balance, good choices. Remembering the previous insertion’s chain as well adds nothing: it is the same table as remembering this chain alone, at every cap, so chains do not meet each other’s recent moves either.

Sixteen insertions’ memory is the only one that moves the number, by a quarter, and it does so at a cost of more kicks and more keys in second buckets, 19% against 16%. It is not a loop broken; it is the kick made a little less faithful to age, which the next plates show is the whole of what helps. The prediction’s under 1% is not reached by any memory, and its premise, that the oldest chain was undoing its own work, is refuted by the first row of the plate.

Where the chains land #

An old key’s other bucket is a crowded one: at a cap of 32 a resident kicked at random finds room in its other bucket 22% of the time, the older of two 19%, of four 15%, and the bucket’s oldest 7% — a key grows old in a table that kicks the oldest because both of its buckets stay full. The chain ends at the first kicked key whose other bucket has room, so this share is what sets how long chains run and how often they reach the cap. A random resident’s other bucket is any bucket, and at 95% load a fifth of the buckets reached this way have room. The oldest resident’s other bucket is not any bucket.

The reason is in what makes a key old in this table. Under the oldest kick a key leaves a bucket only when it is the oldest resident there and an insertion finds the bucket full. A key in an uncrowded bucket is rarely in a full bucket at all, so it is rarely kicked, but it is also rarely the oldest of anything for long, since its neighbours come and go with the churn. A key that survives to be the oldest in its bucket has survived there, and the keys that are oldest in both of their buckets are the keys whose buckets are both persistently full — the crowded corners of the table. Kicking the oldest sends the chain to exactly those corners.

So the trouble at long caps was the one the proposal named as the alternative: a property of always choosing by age, not of a short loop. Choosing by age selects keys by their buckets’ fullness, and a chain that follows such keys walks from full bucket to full bucket.

The older of a few #

Drawing a few residents and kicking the oldest of them trades the oldest kick’s lookups against the random kick’s chains: at a cap of 32 the older of four reads 1.055 a lookup by recency for 5.83 an insertion and leaves 0.5% in overflow; but the oldest kick at a cap of two reads 1.040 for 1.61, and no drawn rule at any cap reaches it. The draw interpolates as it should. Each resident added to the draw makes the kicked key a little older and its chain a little longer: at a cap of 32 the older of two takes 0.56 more reads an insertion than a random kick for 0.037 less a lookup, the older of four 1.60 more for 0.069 less. Overflow rises from nought to half a per cent, far under the oldest kick’s 6.6%.

None of that beats the short cap. The oldest kick at a cap of two gets the whole of the age-sorting at a chain of at most two kicks, because it never has to find room far away: a key it cannot place goes to overflow, and under recency overflow holds keys nobody asks for. Lengthening the cap is a way of keeping keys out of overflow, and the plates have been saying since overflow holds the old keys that under recency that is not worth paying for. The draw is a better long-cap design than the oldest kick, not a better design. The keys a capped chain leaves behind measured how much overflow each cap leaves under random kicks; under recency the right cap was always the short one, and choosing by age makes it shorter still.

Even lookups #

Under even lookups every move toward the oldest helps, at every cap — the random kick at a cap of 32 reads 1.426 a lookup with no overflow, the older of four 1.323 with 0.5%, the oldest 1.295 with 6.6% — because keys moved by age leave fewer keys in second buckets, and overflow is the price. At a cap of 32 a random kick leaves 43% of the keys in their second buckets; the older of four 31%; the oldest 16%. A table that concentrates its displacements on a few old keys has fewer keys displaced, and an even workload pays a second read for each one.

The even lookups make the draw look better than the recency plate did. The older of four at a cap of 32 reads 1.323 an even lookup with half a per cent in overflow; the oldest kick at a cap of two reads 1.331 with 10.9%. For a workload that asks for all keys alike and cares about overflow — because its absent-key lookups read the overflow block — the drawn rule at a long cap is the better design, and the next plate prices exactly that.

Keys that are not there #

Overflow is paid for by lookups of keys not stored: at ten lookups an insertion the oldest kick at a cap of two is cheapest while every lookup is for a stored key, 1.092 reads an operation, but its regions all have overflow, so an absent key costs three reads, and from half the lookups absent the two-level look, which leaves none, is cheaper. Every design that leaves overflow anywhere in a region charges an absent lookup in that region three reads, and at 9% to 11% of keys in overflow every one of the table’s regions has some. The two-level look leaves none and charges two. At a quarter of lookups absent the oldest kick still wins, 1.538 against 1.586; at a half the look wins, 1.794 against 1.983.

The drawn rule never wins here. The older of four at a cap of 32 leaves overflow in half the regions, so its absent lookups cost two and a half reads, but its insertions cost 5.83, and at ten lookups an insertion that is too much to recover. Room the chains could not reach found that a cuckoo table’s empty slots end where its chains cannot find them; the oldest kick’s overflow ends in every region, because its chains reach the crowded corners in all of them.

What the counts establish #

The closing question was whether the oldest kick’s trouble at long caps is a loop inside a chain, or a property of always choosing by age. The first plate rules out the loop at every memory tested: sparing a chain’s own moves makes the table worse, and sparing the previous chain adds nothing. The second shows the property directly: the oldest resident’s other bucket has room a third as often as a random resident’s. Age, in a table that kicks by age, is a measurement of crowding, and a rule that chooses the oldest chooses the key whose way out is most likely blocked.

That is also why the oldest kick works so well at a cap of two. A short cap does not ask the oldest key to find a way out; it asks it to step aside, once or twice, and then accepts overflow. The rule’s strength and its weakness are the same fact seen at two cap lengths.

Reading room against reading age #

The cuckoo designs measured in these essays have split, from the start, into those that read before they move and those that do not. A kick that looks before it moves read every resident’s other bucket and moved the first with room; a look that spreads the room moved the one whose other bucket was emptiest. Both pay a read for every resident, which at buckets of eight is the reason their insertions cost four to seven reads where a blind kick costs under two. The bucket that fits a line made the resident’s own bucket one read; the residents’ other buckets are eight more.

The oldest kick reads nothing extra and chooses by a field already inside the bucket. What these plates show is that the field it reads carries information about the very thing the looks pay to read: an old resident is, more often than not, a resident whose other bucket is full. At a cap of two that is harmless, since the chain gives up quickly. At a cap of 32 it is the worst possible information to act on, and a blind kick that ignores it does better. So the choice of whom to kick is not free of the question of where there is room; it answers it badly, by proxy.

That is the pattern two probes are two misses found on a different axis: a table’s cost is set by where its accesses land, and a rule chosen for one property of the keys quietly decides another.

What the table does not show #

One size, one bucket, one load. The plates are at 95% load in buckets of eight. The crowding that makes old keys hard to place is a property of a full table, and at 90% the long-cap oldest kick may behave differently; it was not run here.

Ages for free. Ages are kept beside each key at no charge, and so are the spared-move memories. A memory of sixteen insertions’ moves is a small hash set; a real table would pay for it, and it buys a quarter of the overflow at a long cap.

Draws from one generator. The drawn residents come from the same random stream as the random kick, so a draw of four makes three more draws than a random kick and shifts the stream of later choices. The comparison between draw sizes is therefore between different random tables, not one table with a parameter turned.

Still open: room counted, not age #

If the oldest kick fails at long caps because age is a proxy for crowding, a kick could read the crowding directly. The first-found look already reads every resident’s other bucket and moves the first with room, and the look that moved the oldest with room was dearer than the blind oldest kick, 7.70 reads an insertion. Between them is a kick that reads nothing extra: each bucket can keep, beside its residents’ ages, one bit per resident saying whether that resident’s other bucket had room the last time it was checked, refreshed whenever a chain passes through. A kick could move the oldest resident whose bit says room, and the oldest overall if none does.

The measurement that follows keeps those bits, refreshed by every chain and look that reads a bucket, and charges the same workloads at caps of two, eight and 32. The prediction is that at a cap of 32 the bit-guided oldest kick leaves under 1% of keys in overflow for under five reads an insertion, keeping a lookup by recency under 1.045, because it sends chains away from the crowded corners while still choosing by age, and that at a cap of two it matches the plain oldest kick. It could fail on staleness: a bit set when a chain last passed may be wrong by the time it is read, since a bucket with room fills within a few insertions at 95% load. The question is whether a table can remember where its room is cheaply enough to steer by it, or whether room at this load moves faster than any memory of it.