A kick that moves the oldest

A cuckoo table gives every key two buckets, chosen by two hashes, and a lookup reads the first, then the second if the key is not there. The bucket that fits a line made each bucket hold eight keys so that a bucket is one read, and at high load a new key often finds its first bucket full. The table makes room by kicking: it moves a resident of the full bucket to that resident’s other bucket, which may itself be full and kick again, up to a cap, and a key the chain cannot place goes to a small overflow block for its region of the table. The keys a capped chain leaves behind measured what the cap leaves there, and a kick that looks before it moves and a look that spreads the room tried reading the residents’ other buckets before moving any of them.

Overflow holds the old keys charged those designs for lookups as well as insertions. A key in its first bucket costs one read to find, in its second two, in overflow three. Blind kicks under a cap of two were the cheapest design up to thirty lookups an insertion, whether the lookups were spread evenly or asked mostly of recent keys, and the reason was in where the keys lived. Every kick moves a resident outward, and a key that has been in the table longest has been kicked most: under blind kicks the oldest tenth of the keys had 26% in overflow and 35% in second buckets, the newest tenth under 1% and 4%. The keys a recency-skewed workload asks for most were the keys that had drifted least.

That essay’s closing section asked whether a table could choose which of its keys pay for the room. The kick picks a resident at random. It could pick the oldest, the one least likely to be asked for under recency, which a bucket can find from an age kept beside each entry. The prediction was that under recency the mean lookup would fall from 1.09 reads to about 1.04 at 95% load, since the newest half of the keys would almost never leave their first buckets, and that under even lookups nothing would change, since an even workload does not care which keys move. It named the risk: the oldest resident’s other bucket may be full of old keys too, so chains may lengthen and insertions cost more than the lookups save.

Two choices of resident #

The table, the churn and the charges are the earlier essays’. The table holds 16,384 keys in buckets of eight, filled to a load and then churned — eight rounds of deleting a random key and inserting a fresh one for every slot — so that what is measured is the table’s steady state, not its first fill. A lookup by recency asks for the key of recency rank $r$ in proportion to $1/(r + 1)$; an even lookup asks for every stored key alike.

Two changes were made, each choosing the oldest. Under blind kicks, the resident moved out of a full bucket is the one inserted longest ago rather than one drawn at random; the random draw is still made, so the stream of fresh keys is identical under both choices. Under the one-level look, which reads every resident’s other bucket before moving any, the resident moved is the oldest whose other bucket has room, rather than the first found. Ages are insertion times, kept beside each key; a key being placed is the newest of all and is never chosen.

Lower by recency, and evenly too #

Moving the oldest resident instead of a random one takes a lookup by recency from 1.084 reads to 1.040 at 95% load, as predicted — and an even lookup from 1.420 to 1.331, which was predicted not to move; the look that moves the oldest with room reads 1.064 by recency, for 7.70 reads an insertion. The prediction’s number was right, and its reason for the second half was wrong. An even workload does not care which keys move, but it does care how many keys sit away from their first bucket, and the oldest kick changes that: under random kicks 23.5% of the keys are in their second buckets and 9.3% in overflow, and under the oldest kick 11.3% and 10.9%. Half as many keys pay a second read, a sixth more pay a third, and the even mean falls by a tenth of a read.

The insertions cost the same. Blind kicks under a cap of two read 1.627 buckets an insertion with random choice and 1.610 with the oldest — the chains are, if anything, slightly shorter, 0.61 kicks an insertion against 0.63. Choosing the oldest needs the ages, one small field per entry, and a scan of the full bucket’s eight ages, which is inside the bucket the insertion has already read. The look that moves the oldest with room reads every resident’s other bucket, 7.70 reads an insertion against the first-found look’s 4.34, and saves less by recency than the blind kick does.

A table sorted by age #

Moving the oldest sorts the table by age: the newest three tenths of the keys almost never leave their first buckets — at most 0.2% of a tenth elsewhere, against 4.5% to 18.7% under random kicks — and the oldest tenth has 56% in overflow where random kicks left 26%. A random kick spreads its displacements over every key in proportion to how long it has been exposed to them, which is why the drift outward is gradual under random choice. The oldest kick concentrates them. A new key is never moved until every key that arrived before it in its bucket has gone, and each kick moves the bucket’s oldest outward, so the table settles into layers: new keys at home, keys of middle age in their second buckets, and the oldest in overflow.

That is why both lookup means fall. Under recency the newest keys are asked for most and are all at home. Evenly, the table has fewer keys away from home in total, because the oldest kick moves the same few keys repeatedly rather than many keys once each: a key already in its second bucket that is the oldest there is kicked back to its first, and the keys that end in overflow are those whose two buckets are both full of keys younger than they are. The cost lands on the oldest tenth, 56% of which is three reads away, and a workload that asked for old keys would pay it.

The cap raised #

The risk the proposal named arrives with the cap: at a cap of two the oldest kick leaves 10.9% of the keys in overflow against 9.3%, but at a cap of 32 it leaves 6.6% where random kicks leave none, for 6.10 kicks an insertion against 3.23. A longer cap gives a random chain more chances to find a bucket with room, and at 32 it nearly always does. An oldest chain does not use those chances the same way. Its choices are deterministic given the table, and the plates are consistent with chains that keep choosing the same few old keys — a key kicked from one bucket arrives in its other, is the oldest there, and is chosen again when the next chain passes — so that a longer cap buys mostly more kicks of the same keys. The chains were not traced here, and that account is the likeliest one the counts allow rather than one they show.

Under recency the cap of 32 with the oldest kick still reads well for lookups, 1.037 a lookup, the lowest of any blind design, because its overflow holds old keys. But it pays 7.10 reads an insertion for it, and its even lookups, 1.295, sit barely under the cap of two’s. The oldest kick is a cap-of-two design.

Every mix #

Charged for insertions and lookups by recency together, blind kicks that move the oldest under a cap of two are the cheapest design at every mix measured, from 0.1 lookups an insertion to 100 — 3.6% under random kicks at ten lookups an insertion and 4.0% at a hundred. The earlier essay’s winner up to thirty lookups was blind kicks under a cap of two; the oldest version of it costs the same to insert with and less to look up with, so it wins wherever that design won and further. Under even lookups the same design is cheapest to thirty lookups an insertion, and at a hundred the oldest kick at a cap of eight edges past it, 134.2 reads against 134.7 for the hundred and one operations.

The looks lose more ground. Reading every resident’s other bucket buys the table fewer overflow keys, but under recency overflow holds keys nobody asks for, and the look’s reads an insertion are paid on every insertion. A look that moved the oldest with room, and also kicked the oldest when the look found nothing, reads 1.053 by recency and 1.288 evenly — the lowest even mean of any design — for 7.70 reads an insertion, which only pays at about a hundred even lookups an insertion.

Across loads #

At every load from 90% to 97% the oldest kick under a cap of two brings a lookup by recency to about 1.04 reads — 1.034, 1.040 and 1.043 against 1.071, 1.084 and 1.087 — and an even lookup down by eight or nine hundredths of a read, while overflow rises from 6.6%, 9.3% and 9.8% to 8.6%, 10.9% and 11.7%. The gain does not depend on load in the range measured, and neither does its price: about one and a half to two points more of the table in overflow. That price matters to one workload these plates do not charge much, lookups of keys that are absent, which read both buckets and the region’s overflow block whenever the block holds anything; a table with more keys in overflow has more regions with something in their block.

Why the newest stay home #

The layering is a consequence of a rule and not of the workload, which is why it helps the even lookups too. Under the oldest kick a key can leave its first bucket only by being the oldest resident of that bucket when an insertion finds it full. A bucket holds eight keys, and keys arrive in a bucket at random times, so a newly inserted key has, on average, seven older neighbours that must all leave before it can be chosen. Each of those leaves only by being kicked or deleted, and at 95% load deletions come at the rate churn sets: a key that has lived through a few rounds of churn has outlived most of its neighbours. So the probability that a young key has been displaced falls off very steeply with youth, which is the shape of the plate: under 0.2% of each of the newest three tenths away from home, 1.4% of the fourth, 5.3% of the fifth.

Random kicks have no such floor, however long a bucket’s other residents have lived. A key inserted a moment ago is as likely to be the one kicked as any resident, one chance in eight each time its bucket overflows, and the newest tenth of the keys has 4.5% away from home for that reason. Room the chains could not reach found that a cuckoo table’s empty slots end where its chains cannot find them; the oldest kick decides, in addition, which keys end where their lookups cannot find them quickly, and it puts there the keys that have had longest to be asked for already.

Who pays for the room #

The earlier essay’s question was whether a table can choose which of its keys pay for the room, or only how much room it pays for. It can choose, and choosing changes how much room it pays for as well. A table that always moves its oldest key concentrates every displacement on a minority of keys and leaves the rest at home, so fewer keys are away from home and more of those that are sit in overflow. The total cost of a lookup falls on both workloads measured, and the cost of being old rises: an old key is three times as likely to be in overflow as under random kicks.

That is a trade the workload decides. A tag that answers more than yes and two probes are two misses both found that what a hash table’s layout costs is set by which keys are asked for, not by the table alone. Under recency, the oldest kick is cheaper at every mix; under even lookups it is cheaper to thirty lookups an insertion; under a workload that asks for the oldest keys — an archive scanned in order of arrival, say — it would be the worst design measured, and that workload was not run.

What the table does not show #

One table size and bucket. Sixteen thousand keys in buckets of eight. The layering by age depends on buckets holding several keys whose ages differ, and a table with buckets of one or two would sort itself far less.

Ages that are free. The ages are insertion times kept beside each key at no charge here. A real table pays bits for them, or approximates age by position in the bucket, which a key’s arrival order sets until a kick reorders it.

Two lookup workloads. Recency in proportion to $1/(r + 1)$ and even. A workload that asks for keys by age in the other direction was not run, and absent-key lookups were charged only in passing.

A cap of two. The oldest kick’s gains are at a cap of two; at higher caps it leaves more in overflow than random kicks do, and the reason was inferred from the counts rather than traced.

Still open: an oldest that has not just moved #

The plates leave one fault in the oldest kick, and it is the one that stops it from using a longer cap. At a cap of 32 a random chain almost always finds room and an oldest chain leaves 6.6% of keys in overflow for twice the kicks. The likeliest reason is that an oldest chain keeps choosing keys it has just moved: a key kicked into its other bucket is old, so it is often the oldest there, and the next chain through that bucket moves it back. A kick could exclude any resident moved within the last few insertions — or simply the key that arrived in this bucket by the kick before it in the same chain — and take the oldest of the rest.

The measurement that follows gives the oldest kick that exclusion, with a memory of the last kick, the last chain, and the last sixteen insertions, at caps of 2, 8 and 32, and charges the same lookups and insertions. The prediction is that at a cap of 32 the excluded oldest kick leaves under 1% of keys in overflow for under four kicks an insertion, while keeping a lookup by recency near 1.04, and that at a cap of two nothing changes, since short chains rarely return to a bucket. It could fail if the cycles are not between buckets a chain revisits but between chains: the old keys that are moved repeatedly may be moved by different insertions, far apart, and a memory short enough to be cheap would not see them. The question is whether the oldest kick’s trouble at long caps is a loop inside a chain, or a property of always choosing by age.