Overflow holds the old keys

A look that spreads the room compared the ways a cuckoo table can make room for an insertion that meets a full bucket. The table holds 16,384 entries in buckets of eight, each key in one of two buckets its hashes choose. Blind kicks move a random resident to its other bucket, up to a cap, after which the displaced key is filed in its region’s overflow block; a look reads the residents’ other buckets first and moves one with room; a two-level look searches the residents of those buckets too. Every design was judged on two numbers, the share of keys it leaves in overflow and the bucket reads an insertion pays, and at 95% load they ranged from blind kicks under a cap of two, 9.2% in overflow for 1.63 reads, to the two-level look, nothing in overflow for 4.31.

Its closing section noticed that the exchange rate between the two numbers had been left open. A key in overflow is not free to keep, even in a region’s spare entries: a lookup of it reads both its buckets, finds nothing, and reads the overflow block, three reads where a key in its first bucket costs one, and it pays them every time the key is asked for. A table read ten times for every write should spend reads at insertion to keep keys out of overflow. The prediction was that at one lookup an insertion the first-found look under a cap of two would be the cheapest table at 95% load, and that by ten lookups an insertion the two-level look would be cheapest at every load from 95% up. It named the risk that the keys in overflow are the most recently inserted, and that recent keys are the ones looked up most.

The overflow’s price is real and smaller than the price nobody had counted. And the named risk runs the other way.

Charging the lookups #

The table and its churn are the earlier essays’ exactly: the fill to the load, then eight rounds of churn in which a random key is deleted and a fresh one inserted, keys the cap stops filed in their region’s overflow block and staying there. Seven designs are run: blind kicks under caps of 2, 8 and 32; the first-found look under caps of 0 and 2; the emptiest-bucket look under a cap of 2; and the two-level look. At the end of the churn every stored key’s place is read off the table, its first bucket, its second, or overflow, together with when it was inserted.

A lookup of a stored key reads its first bucket, then its second if the key is not there, then its region’s overflow block if it is in neither: one, two or three reads. A lookup of an absent key reads both buckets, and the overflow block when its region’s block holds anything, with no filter in front of it to turn the lookup away. Lookups of stored keys are drawn either evenly over the stored keys or in proportion to $1/(r+1)$ for a key’s rank $r$ by recency, the newest first. A design’s cost is its insertions’ reads plus, for each insertion, the reads of a given number of lookups, from a tenth to a hundred.

Blind kicks, nearly everywhere #

At 95% load, with stored keys asked for evenly, blind kicks under a cap of two are the cheapest table at every mix up to thirty lookups an insertion: 15.83 reads an insertion at ten lookups, against 17.95 for the first-found look and 18.10 for the two-level look. The prediction expected the deeper search to have paid by then. It pays only past about 46 lookups an insertion against the first-found look and 65 against the two-level look, and at a hundred lookups an insertion the first-found look under a cap of two is the cheapest.

The arithmetic is two differences. The two-level look spends 2.68 more reads an insertion than blind kicks under a cap of two, and saves 0.041 reads a lookup; the first-found look spends 2.71 more and saves 0.059. A lookup saving of four or six hundredths of a read takes fifty or sixty lookups to repay three reads at insertion. The prediction priced the saving at what overflow costs, two extra reads for each of 9% of keys, about 0.18 reads a lookup. The measured saving is a third of that or less.

Where the keys live #

Every way of searching harder for room moves keys into their second buckets: blind kicks under a cap of two leave 67.3% of keys in their first bucket and 23.5% in their second, the two-level look 62.1% and 37.9%, and blind kicks under a cap of 32 only 57.4% in their first. A key in its second bucket costs a lookup two reads, and a search that keeps a key out of overflow does it by moving residents along their chains, each move sending a key to its other bucket, which half the time is its second.

So the overflow’s saving is partly given back. Blind kicks under a cap of 32 leave essentially nothing in overflow and their lookups cost 1.426 reads, more than under a cap of two at 1.420, because the 9% they keep out of overflow they mostly keep in second buckets, along with a tenth of the table’s other keys that their long chains moved there. The looks do better because they move one resident a step to a bucket that has room, rather than a chain of residents to wherever the chain leads; the first-found look leaves 64.1% of keys in their first bucket, and its lookups are the cheapest of any design but the emptiest-bucket look.

The two costs can be set side by side, read for read. Under blind kicks with a cap of two a lookup of a stored key pays 0.186 reads beyond its first bucket for the keys in overflow, two extra reads each for 9.3% of them, and 0.235 for the keys in their second buckets. Under the two-level look it pays nothing for overflow and 0.379 for second buckets. The deeper search removes 0.186 reads a lookup of overflow and adds 0.144 of second buckets: it gives back three quarters of what it saves. The first-found look gives back less, since its single-step moves leave more keys at home, and nets 0.059 a lookup, the largest saving of any design over blind kicks at a cap of two and still only about a forty-sixth of its own extra cost at insertion.

The keys a capped chain leaves behind counted the keys a chain strands. The other half of what a chain does is the keys it relocates, and on a table whose lookups try the first bucket first, a relocation costs as surely as a stranding does, at half the price and on many more keys.

The newest keys stay home #

Under blind kicks with a cap of two, the newest tenth of the stored keys has 0.6% of its keys in overflow and 4% in their second buckets; the oldest tenth has 26.1% and 35%. The closing section named as its risk that overflow would hold the most recent keys, which are the ones a cache-like workload asks for most. It holds the oldest.

The reason is in what a kick does. A key being inserted takes a slot in its first bucket if there is room, and otherwise displaces a resident, and the key that ends a chain under the cap, the one filed in overflow, is the last resident displaced, not the new key. A new key starts life in its first bucket nearly always, and is moved out only when a later insertion’s chain passes through it. The longer a key has been in the table, the more chains have had the chance to move it, so a key’s place drifts outward with its age: first bucket, then second, then overflow. Under the first-found look the drift is the same and slower, since a look moves one resident a step rather than a chain.

When stored keys are asked for in proportion to their recency, blind kicks under a cap of two are the cheapest table at every mix measured, up to a hundred lookups an insertion, at every load: at 98% load and ten lookups an insertion, 12.59 reads an insertion against 17.25 for the first-found look and 21.22 for the two-level look. A lookup by recency costs 1.09 reads under blind kicks with a cap of two and 1.11 under the two-level look, because the keys being asked for are the ones that have not yet been moved, and the cheapest design to insert is also the cheapest to read.

The one workload that pays for the search #

For lookups of keys that are not in the table, the two-level look is the cheapest design from ten lookups an insertion at every load from 95% up. This is the prediction’s second half, true for the one kind of lookup the overflow cannot hide from. An absent key must be looked for everywhere it could be, both buckets and, if its region’s overflow block holds anything, the block. Under blind kicks with a cap of two every region’s block holds something, so every absent lookup reads three; under the two-level look almost no region’s does, and it reads two. A saving of a whole read a lookup repays the deeper search’s 2.7 reads at insertion in three lookups, and by ten lookups an insertion nothing else comes close.

The overflow blocks’ occupancy is what an absent lookup pays for, and it falls much faster than the overflow share. Under blind kicks with a cap of two every one of the 128 regions holds something in its block at 95% load; under the first-found look with a cap of two, 0.24% of keys are in overflow but they are spread over 27% of the regions, and an absent key costs 2.27 reads; under the emptiest-bucket look 11% of regions, 2.11 reads; under the two-level look none. A design that strands a few keys strands them in many places, and an absent lookup cannot know in advance which regions are clean.

A real table’s lookups are a mixture, and the mixture decides the design. A store serving mostly hits wants the cheapest insertion; one serving mostly misses, a membership test in front of a slower store, wants the deepest search it can afford. A tag that answers more than yes and the filter essays before it found the same division along a different line: what a structure is for decides which of its costs counts.

Every load, every mix #

Across four loads and seven mixes, blind kicks under a cap of two are the cheapest table in 23 of 28 settings when stored keys are asked for evenly, in all 28 when they are asked for by recency, and in only the lightest mixes when the keys asked for are absent. The five exceptions for stored keys all lie at thirty lookups an insertion or more, where the looks’ slightly cheaper lookups finally repay their dearer insertions.

That reverses the earlier essays’ ranking for most workloads. On their two numbers, overflow and insertion reads, blind kicks under a cap of two were the worst design measured, and the two-level look the best. With lookups charged for where keys actually live, the design that left 9% of its keys in overflow is the cheapest for every workload that asks for keys the table holds, until it is read thirty times for every write.

What the prediction got right #

The closing section predicted that at one lookup an insertion the first-found look would be cheapest at 95% load, and that by ten lookups an insertion the two-level look would be cheapest at every load from 95% up. At one lookup an insertion blind kicks under a cap of two are cheapest, by more than two reads. By ten lookups an insertion the two-level look is cheapest only when the keys looked up are absent; for keys the table holds, blind kicks stay cheapest to thirty lookups an insertion, and by recency to a hundred.

It priced overflow at its own cost and missed the cost of the relocations every search for room makes, which put a fifth of the keys in their second buckets under the deeper searches. And it named the risk that overflow would hold the newest keys, which the workloads that favour recent keys would punish. Overflow holds the oldest: a kick strands a resident, never the key being inserted, and the keys a recency-skewed workload asks for are the ones no chain has yet touched. The question was whether a table’s search depth should be set by its load alone or by how often what it stores is asked for. It is set by which keys are asked for, and by whether they are there.

That moves the choice from the table to its workload. The same table at the same load, under the same churn, has a different cheapest search according to whether its lookups find what they look for. A table probed mostly for keys it lacks, such as the table a hash join fills from its smaller input when most probes miss, wants the two-level look; one probed mostly for keys it holds, and most of all for its recent ones, wants the blind kicks and their stranded old keys.

What the lookups assume #

The first bucket first. A lookup reads its first bucket and then its second, which is what makes two probes two misses whenever the second is needed. A table that read both at once, as a cache-line pair, would charge a key in its second bucket the same as one in its first, and the relocations would cost nothing; then the overflow’s price is all that is left, and the deeper searches would win sooner.

Two popularities. Lookups drawn evenly over the stored keys, or by recency with weights $1/(r+1)$. A workload skewed toward some keys for reasons unrelated to their age would see the even case’s numbers.

Deletions at random. The churn deletes a key chosen evenly, so an old key is as likely to leave as a new one. A workload that deleted its oldest keys first, as a cache evicting by age does, would empty its overflow blocks by itself, since the keys there are the old ones, and the age profile here would be cut off at its far end.

One table. The earlier essays’ table and churn, one seed a design; the costs compared are differences of a few hundredths of a read a lookup, and the orderings hold at every load.

Still open: a kick that moves the oldest resident #

The kick picks a resident at random, and the plates show what that does over time: every key drifts outward with age, and the keys a workload asks for most are the ones that have drifted least. A kick could instead choose which resident to move, and the choice that suits a recency-skewed workload is the oldest resident, the one least likely to be asked for, which a bucket can find from an age kept beside each entry or approximated by its position in the bucket.

The measurement that follows gives the blind kick that choice under every cap, and the first-found look a preference for the oldest resident among those with room, and charges the same lookups. The prediction is that under recency the mean lookup falls 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 changes, since an even workload does not care which keys move. It could fail on the chains: moving the oldest resident sends it to its other bucket, where it displaces another, and if the oldest keys’ other buckets are themselves full of old keys, chains may lengthen and insertions cost more than the lookups save. The question is whether a table can choose which of its keys pay for the room, or only how much room it pays for.