A look that spreads the room

A kick that looks before it moves changed how a cuckoo table makes room. The table holds 16,384 entries in buckets of eight laid out on one cache line, and each key may live in either of two buckets chosen by two hashes. An insertion that finds its first bucket full used to kick a random resident to that resident’s other bucket, and kick again from there, up to a cap of two kicks, after which the key was filed in an overflow block. The look reads the other bucket of each of the full bucket’s residents in turn and moves the first one whose other bucket has room, so the new key takes its slot without a chain. At 95% load, under the same cap of two, the look left 0.20% of keys in overflow after churn, where blind kicks had left 9.2%.

Its closing section noticed that the look’s choice was arbitrary. Stopping at the first resident with room fills that resident’s other bucket, which might have had one free slot or three. A look that read all eight residents’ other buckets before choosing could move the resident to the emptiest, and would leave the table’s free slots spread over more buckets instead of consuming them where they happened to be found. It predicted that this look would read about one and a half more buckets an insertion than the first-found look, since the first with room is usually the third or fourth resident, and that it would hold overflow at nought where the first-found look leaves 0.20% at 95% load and 0.89% at 97%, because buckets with exactly one free slot would become rarer. It named the way it could fail: a table at 95% load has one free slot for every twenty entries, and moving keys toward empty buckets might only shuffle where the full buckets are without making any fewer of them.

The look spreads the room, and the failure it named is close to what happens. It also turns out to be the wrong place to spend the reads.

Reading all eight and choosing #

Everything except the choice is the earlier essay’s: the table, the hashes, the cap of two, eight rounds of churn after the fill (a random deletion and a fresh insertion each), keys the cap stops filed in the overflow block of their first bucket’s region of sixteen buckets, and the count of bucket reads, in which a bucket inside the region already read is free. The emptiest-bucket look reads the other bucket of every resident of the full bucket, notes how many free slots each has, and moves the resident whose other bucket has the most, the first such in reading order when several tie. If none has room, the insertion falls back to the blind kick under the cap, as before. The first-found look is unchanged, and so are blind kicks at caps from two to sixty-four and the two-level look, which, when no resident’s other bucket has room, looks at the other buckets of those buckets’ residents.

The table is run at 90%, 95%, 97% and 98% load. Every design’s churn checks that the keys in buckets and in overflow add up to the keys stored and that every key sits in one of its two buckets.

Less overflow, at the price of more reads #

At 95% load, under the cap of two, the emptiest-bucket look leaves 0.08% of keys in overflow, against 0.20% for the look that stops at the first with room, and reads 7.12 buckets an insertion against 4.34. The prediction said nought, for about one and a half more reads. The overflow falls by three fifths and the reads rise by 2.8.

On the plate the two looks are two curves of the same shape, the emptiest one shifted right by nearly three reads. At every cap the emptiest look has less overflow; at every level of overflow the first-found look reaches it with fewer reads. Under a cap of four both leave nothing, 4.41 reads against 7.15. The cap of two that the earlier essay compared at is the only place where the choice of resident matters, because it is the only place where the look’s misses still reach overflow often enough to count.

The design that wins the plate is neither. The two-level look, which searches the residents of the residents’ other buckets when the first level finds nothing, leaves no key in overflow at 95% load for 4.31 reads an insertion, fewer than the first-found look and 2.8 fewer than the emptiest.

Where the extra reads come from #

The look that stops at the first resident with room stops, on average, at the 3.3rd resident of eight at 95% load, so the emptiest-bucket look, which always reads all eight, reads about four more buckets each time it looks. The prediction’s arithmetic had the right position and the wrong subtraction. It took the first with room to be the third or fourth, which it is, and counted one and a half extra reads. But a look that stops early reads fewer than four buckets on average, counting the looks that find nothing and read all eight, so reading all eight every time costs about four more; and looking runs at every full bucket a chain meets, which at this load is seven insertions in ten. An insertion that finds its first bucket full reads 9.96 buckets under the emptiest-bucket look against 5.69 under the first-found look.

What the extra reads buy is visible in the same plate. The emptiest-bucket look finds room in 90% of its looks at 95% load, against 86% for the first-found look, because the buckets it leaves behind are less often completely full. Four looks in a hundred that would have gone on to a blind kick, and sometimes to overflow, now succeed. That is a real effect of spreading the room, and it is small.

Spread room is still scarce room #

After churn at 95% load, the emptiest-bucket rule leaves 24% of buckets with exactly one free slot, against 21% under the first-found look, and 7% with two or more against 8%; full buckets fall only from 71% to 69%. The prediction said that buckets with one free slot would become rarer. They become commoner, which is what spreading room means at this load. A table at 95% load has 819 free slots among 2,048 buckets, two fifths of a slot a bucket. Moving keys toward the buckets with the most room takes slots from the buckets that had three and gives them to buckets that had none, so the distribution narrows: fewer buckets with several free slots, a few more with one, and slightly fewer with none.

The closing section named this risk precisely: at a given load the room is a fixed quantity, and a placement rule can only rearrange it. The packed table met the same arithmetic when it divided a region’s spare among its buckets: room put where it can be used helps, and no division makes more of it. The rearrangement helps because a look succeeds when any one of eight other buckets has a slot, and having the slots on more buckets raises that chance a little: from 86% to 90%. It does not help much, because 69% of the buckets a look reads are still full. At 95% load the room is scarce whatever shape it takes.

The other two designs on the plate leave the room in nearly the same shape as the first-found look. Neither of them chooses where to put a key, and both reach far less overflow than the rule that does. The difference between designs is not in the shape of the room they leave but in how far they search for it.

A base and an exponent #

The two ways of spending reads act on different parts of one number. A one-level look fails when all eight of the residents’ other buckets are full. If buckets were full independently, with a chance $p$ each, that would happen with chance $p^8$. Spreading the room acts on $p$: the emptiest-bucket rule lowers the share of full buckets from 71% to 69%, which takes $p^8$ from 6.5% to 5.1%, a fall of a fifth. Looking a level deeper acts on the exponent: the second level reads the other buckets of up to fifty-six more residents, and $p^{64}$ is under one in ten million at either value of $p$.

The measured failure rates are higher than the independent ones, 14% for the first-found look and 10% for the emptiest, because full buckets are not independent; the likeliest reason, not separately measured, is that a full bucket’s residents tend to have full other buckets too, so a look that starts in a crowded part of the table stays there. But the direction is the arithmetic’s. A rule that changes the base by two points cannot compete with one that multiplies the exponent by eight, and the plates show the second leaving nothing in overflow at 95% load for fewer reads than the first spends to leave 0.08%.

Where room is scarcest, spreading helps least #

At 97% load the emptiest-bucket look leaves 0.72% of keys in overflow under the cap of two, against the first-found look’s 0.89%, for 8.72 reads an insertion against 5.65. The prediction’s nought is two orders of magnitude away. With three free slots for every hundred entries, a look’s eight other buckets are all full more than a fifth of the time, and spreading the slots over more buckets cannot change that much when there are so few slots to spread. Under a cap of four the two looks are level, 0.16% and 0.17% of keys in overflow, and the emptiest pays three more reads for it.

The two-level look leaves 0.010% at 7.03 reads, and blind kicks under a cap of sixty-four leave 0.02% at 7.17. Both search further for less than the emptiest-bucket look spends searching wider.

From 95% load to 98% the emptiest-bucket look’s advantage over the first-found look shrinks from a factor of two and a half to a factor of 1.14: 0.08% against 0.20%, then 1.32% against 1.50%. At 98% the two-level look leaves 0.10% and blind kicks under a cap of 32 leave 0.92%. Every design’s overflow rises with load, and the ordering of the four does not change at any load above 90%, where all of them leave nothing. A placement rule acts on how room is arranged, and the closer a table comes to full the less arrangement there is to act on.

What an insertion pays #

An insertion that meets a full first bucket reads 9.96 buckets under the emptiest-bucket look at 95% load, against 5.62 under the two-level look, which leaves nothing in overflow, and 5.69 under the first-found look. The emptiest-bucket look’s price is nearly fixed, nine to twelve reads at every load, and every one of those reads is a cache line, the unit the machine actually charges, because it reads all eight residents’ buckets at every full bucket it meets whatever their state. The two-level look’s price rises steeply with load, from 3.60 to 11.61, because it reads the second level only when the first finds nothing, and at 98% that is most of the time. Below 98% the two-level look is the cheaper of the two at every load, and at 98% they cost nearly the same while the two-level look leaves a thirteenth as much in overflow.

That makes the comparison the earlier essay drew sharper. The first-found look reads a bucket and stops if it has room, which is the cheapest possible use of a read. The two-level look continues that, one level further, only when the first level has failed. The emptiest-bucket look spends its extra reads on buckets that are no use for this insertion, reading all eight to choose among the ones with room, in order to make the next insertion slightly likelier to find room. Room the chains could not reach found that a table at 95% load stands 13.8% empty after churn while keys sit in overflow; the room is there, and what a design buys with its reads is reach to it, not a better arrangement of it.

What the prediction got right #

The closing section predicted that the emptiest-bucket look would read about one and a half more buckets an insertion than the first-found look, and hold overflow at nought where the first-found look leaves 0.20% at 95% load and 0.89% at 97%. It reads 2.8 more, because it reads all eight residents’ buckets at every full bucket a chain meets, and leaves 0.08% and 0.72%. It predicted that buckets with exactly one free slot would become rarer, and they become commoner, from 21% to 24%, because spreading a fixed amount of room over more buckets is exactly that.

It named the failure as the shape of the free room being fixed by the load, so that every placement rule meets the same full buckets in a different order. The shape is not quite fixed: the rule moves about 2% of buckets from no free slot to one and 1% from several to one, and its looks succeed four times more in a hundred. But the load fixes how much room there is, and at 95% that is two fifths of a slot a bucket. A look can make the table a little easier for the insertions after it. The cheaper way to help them is to look further for this one.

What the table assumes #

One way to choose. The emptiest bucket, ties to the first read. A look could weigh the room it finds against the reads already spent, or prefer an emptier bucket only when it is in the region already read and free; neither was run.

Reads as the only price. A bucket read is one unit whether it is a cache line the insertion was going to touch or one it was not. The emptiest-bucket look writes slightly less than the first-found look, 1.76 entries an insertion against 1.82 at 95%, since its moves land where they are less often undone, but writes are not what any of these designs is short of.

One seed of churn a design. Every number is one table churned for eight rounds, and the overflow shares at 95% load are a few dozen keys. The orderings between designs are the same at every load from 95% to 98%, which is the evidence that they are not noise.

Still open: the price of a key left in overflow #

Every design here was judged on two numbers, the overflow it leaves and the reads an insertion pays, and the plates leave the exchange rate between them open. A key in overflow is not free to keep: every lookup of it reads its two buckets, finds nothing, and reads the overflow block as well, so its cost is paid every time it is asked for. A table that is read ten times for every write should pay many reads at insertion to keep a key out of overflow; one that is written as often as it is read should not.

The measurement that follows charges each design for both: the reads its insertions pay, plus, for every lookup, the extra read a key in overflow costs, at mixes from one lookup for every insertion to a hundred, with lookups drawn uniformly over the stored keys and again in proportion to a skewed popularity. It then finds, at each load and mix, the design and cap that cost least in total. The prediction is that at one lookup an insertion the plain first-found look under a cap of two is cheapest at 95% load, since its 0.20% of overflow costs a fifth of a read for every hundred lookups, and that by ten lookups an insertion the two-level look is cheapest at every load from 95% up. It could fail on skew. If the keys that end up in overflow are the ones inserted most recently, and recent keys are the ones looked up most, overflow costs far more than its share suggests, and the deep search pays at mixes where a uniform count says it does not. The question is whether a table’s search depth should be set by its load alone or by how often what it stores is asked for.