Room the chains could not reach

The block already open churned a cuckoo table at 95% load, with the kick chain capped at two and the keys it stopped filed in an overflow block a region, and found that the overflow does not climb for ever. It settles. With keys left where they stopped it settles at 9.2% of the table; moving a key home at every deletion holds it at 4.0%, and moving keys home only while their block is open for another reason holds it at 4.9%. The homing policies did not do better because of one plain fact: a slot freed by a deletion can hold one key, and every key moved home took the slot the next insertion needed. Homing at every deletion sent a quarter of the insertions that followed it to the overflow.

That page’s closing section proposed giving the stopped keys room of their own. Keep a few entries in each region aside, at the same total memory, so that a key the cap stops goes to its region’s reserve before the overflow block. The buckets would then hold the same keys in fewer entries, which is the price, and the proposal predicted it small: a tenth of a kick more for each insertion. Against that it predicted a large gain. A region at 95% load with keys staying holds about eleven stopped keys, and with homing about five, so a reserve of two entries a region should remove most of the overflow. And it named how it could fail. Buckets fuller than 95% might stop insertions faster than any reserve could catch them, so that the reserve fills within the first table’s worth of churn and the overflow climbs back. The question was whether a few entries kept back for the cap’s victims do more than every policy for moving them, or whether in a table this full there is no room to keep.

Where a reserve sits in a region #

The table is the earlier page’s exactly, and the line of pages behind it: the bucket that fits a line put eight entries in a bucket so a lookup reads at most two lines, and the keys a capped chain leaves behind capped the kick chain to stop an insertion’s bytes from running away. So: 16,384 entries in buckets of eight, 2,048 buckets in regions of sixteen, two hash functions choosing each key’s buckets, a cap of two kicks, a stopped key filed under the region of its first bucket. A region’s 128 entries are packed in tag order, as in entries found by the rank of their tag, so a bucket is not a fixed run of eight slots but a count in the region’s metadata, and a reserve is simply a number of the region’s entries its buckets may not use. It is the same device as the spare entries the slack an insertion can reach kept at the end of a region, pointed at a different customer: that spare was for insertions that would otherwise shift a whole region’s entries, and this one is for the keys the cap turns away. A reserve of $r$ entries means the region’s sixteen buckets together hold at most $128 - r$ keys, each bucket at most eight. The stored keys stay at 95% of 16,384. So the buckets’ room shrinks and they are asked to hold the same keys in it: the keys are 95.7% of the buckets’ room at $r = 1$, 96.5% at $r = 2$, 98.1% at $r = 4$, and at $r = 8$ there are more keys than bucket room, 101.3%.

A bucket has room for a key when it holds fewer than eight and its region’s buckets hold fewer than $128 - r$. An insertion that meets a bucket without room kicks a random resident to that resident’s other bucket, as before, at most twice. A key still displaced goes to its first bucket’s region’s reserve if an entry there is free, and to the region’s overflow block if not.

With a reserve of nought this is the earlier page’s simulation step for step, drawing the same random numbers, and it reproduces that page’s settled shares, block reads and kicks to the last key. Every difference measured below is the reserve’s.

The reserve does not keep a single key in #

A reserve of two entries a region leaves 7.7% of the keys in overflow blocks where none left 9.2%, and the share of keys outside their buckets does not move: it is 9.2% with no reserve, 9.2% with two, 9.0% with four and 9.3% with eight. The proposal predicted that two entries would remove most of the overflow. They remove a sixth of it, and they do so by holding keys that would otherwise have gone to the block. Not one key that the cap would have stopped is kept in a bucket instead.

The arithmetic of a sixth is the proposal’s own, read the other way. A region holds about eleven stopped keys at 95% with keys staying, and two of them fit in two reserve entries. Eleven minus two is nine: the block keeps most of what it held. The prediction read “about eleven stopped keys” as the problem and “two entries” as the answer, when two entries were never going to hold eleven keys. What the proposal was really reaching for was that a reserve might reduce the number of keys stopped in the first place. It does not, and the reason is the most useful thing the measurement found.

Stopped by a pair of buckets, never by a region #

After the churn has settled, 13.8% of the table’s entries are empty and 9.2% of its keys live outside their buckets. There is more empty room in the buckets than there are keys outside them. The cap stops a key because the two buckets its chain visits are full, and the room is elsewhere. A key’s first bucket is full; it kicks a resident to that resident’s other bucket; that one is full; it kicks again; that one is full too, and after two kicks the chain gives up. The chain has looked at three buckets, of 2,048, and it gives up while hundreds of buckets have a free slot.

That is the fact the earlier page met when it found the stop rate under churn higher than a count of full buckets would suggest. It is a property of the pairs of buckets that keys tie together, not of how much room the table has. And it is why the reserve is nearly free. A reserve takes room from the buckets, but the buckets have room to spare that the chains do not reach, and a region’s limit of $128 - r$ binds only when the region’s buckets are nearly full together. With keys staying they hold about 110 keys a region on average, against a limit of 124 at a reserve of four, so the limit is almost never what stops a key. At $r = 4$ fewer than one stop in a thousand happens at a region’s limit rather than at a full bucket.

So a reserve is room taken from the empty slots the chains could not reach, and handed to the keys the chains could not place. Spare where a bucket can use it found the mirror image of this in the packed table’s spare: divided evenly among buckets, most of it went to buckets that were already full and never grew. Room is only room for a key that can get to it. Up to eight entries a region, keys staying, that is all it does. The bar at eight is the strange one: the stored keys are 101.3% of the buckets’ room, more keys than the buckets could hold if every bucket were full, and still only 9.3% of keys live outside them. The 5.6% in reserves and the 3.7% in blocks were going to be outside anyway.

At sixteen entries the room runs out. The buckets would have to hold 108.6% of their room for the old share to stand, and the share outside rises to 11.0%. A sixth of the stops now happen at a region’s limit. The proposal’s failure, buckets too full for any reserve to help, is real, and at 95% with keys staying it sits at sixteen entries a region, an eighth of the table.

The price, in kicks #

At four entries a region an insertion kicks 0.632 times with keys staying, against 0.627 with no reserve, and 0.992 times when every deletion homes a key, against 0.988. The proposal priced the reserve at a tenth of a kick an insertion. It costs a two-hundredth, which is inside the noise of one seed. The reason is the one above: the stop is decided by the chain’s three buckets, and a reserve of four rarely makes one of them fuller than it would have been.

The price does arrive, and where it arrives depends on the policy. With keys staying it waits until sixteen entries, at 0.688 kicks and 11.3% of insertions stopped. With homing at every deletion it arrives at eight, 1.046 kicks and 28.3% stopped against 25.4%. Homing fills the buckets: a key moved home is a key the buckets hold, so under homing the buckets run fuller than under staying, and their room runs out at a smaller reserve. At sixteen entries, homing at every deletion stops nearly half of all insertions.

Homing when the block is open pays earlier than either, and the reason is a part of the policy the reserve added. A deletion from a bucket moves home a reserve key whose first bucket it is, which the region’s metadata shows without reading anything. That is a key moved home into the slot the next insertion wanted, exactly the trade that cost the earlier page’s homing a quarter of its insertions. At four entries this policy kicks 0.940 times against 0.888 with no reserve, and stops 22.5% of insertions against 20.0%. It is the one policy for which a reserve of four is not free, and the cost is the familiar one rather than the reserve’s room.

In front of each policy #

A reserve in front of a homing policy does what it does in front of keys that stay — it moves stopped keys from block to reserve — and the two gains add. At four entries a region the blocks hold 6.1% of keys when they stay, 1.8% homing at every deletion and 2.3% homing when the block is open. Each is the policy’s own overflow less the keys the reserve holds, which is between two and three per cent of the table in every case.

The shares outside the buckets tell the same story as before. Homing at every deletion keeps 4.0% of keys outside with no reserve and 4.0% with four entries; homing when open keeps 4.9% and 4.5%. The reserve does not stop keys being stopped under any policy. It decides which of them live where.

Two things about the homing policies change, though, and both are about reads. Homing at every deletion with no reserve read a block on 98% of deletions, because a region with an empty overflow was rare. With four entries a region it reads a block on 59% of them. A region’s first few stopped keys live in its reserve, the reserve’s keys are found in the metadata, and the block is read only when the reserve has nothing for the freed bucket and the block is not empty. Homing when the block is open reads a block on 2.3% of deletions with four entries a region, against 4.9% with none, because fewer deletions fall on a key that lives in one.

And a reserve that a policy keeps full is worth more than one it leaves alone. With keys staying, a reserve entry freed by a deletion stays empty until the next stop in that region, while the region’s block may still hold keys; at four entries a region the reserves are full in only two regions of three and hold 3.6 keys on average. Homing when the block is open refills them whenever the block is open anyway, moving keys from block to reserve as well as from block to bucket. That is about two hundredths of a key a deletion, and it is in the 2.3%.

Three loads #

At 85% load eight entries a region hold all but 0.2% of the keys the cap stops, and sixteen hold all of them, while the share outside the buckets climbs only from 4.2% to 4.5%. A lighter table stops fewer keys, so the same reserve covers more of them, and it has more empty room for the reserve to take. The point at which the reserve starts costing kicks moves out with it: at 85% with keys staying, sixteen entries a region cost an insertion 0.017 kicks more, at 90% 0.035 and at 95% 0.061.

Read across, the three loads say the same thing in three sizes. A reserve as large as a region’s typical overflow, about four and a half keys at 85%, seven and a half at 90% and eleven at 95% with keys staying, empties most of the blocks. A reserve as large as the empty room the chains cannot reach costs nothing until it approaches that room. At 85% the two are far apart, four and a half stopped keys a region against about twenty-four empty entries, so a reserve can be made as large as the overflow for nothing. At 95% they are close together, eleven stopped keys against about eighteen empty entries, and a reserve big enough to hold the overflow is already taking room the chains use.

What a reserve is worth to a lookup #

Homing when the block is open behind a reserve of four entries a region touches 1.57 overflow blocks a deletion at sixty-four successful lookups each, against 3.39 without the reserve and 6.07 for keys left where they stopped, and it is the cheapest of the four at every ratio of lookups to deletions, including none. The earlier page found that homing when open paid for itself against staying only once there were one and a half successful lookups a deletion; with a reserve in front of it there is no crossing to find.

This plate depends on where the reserve lives, and that is a choice of layout rather than a measurement. Every successful lookup reads at most its two buckets, the bound two probes are two misses priced in cache lines, plus whatever lies outside them. A lookup already reads its region’s header, which holds the bucket counts and the overflow’s filter, as the lookups a filter turns away arranged. With eight-byte entries, as in a lookup that stops caring how wide an entry is, four reserve entries and their tags fit in the part of that line the counts and filter leave. Then a lookup whose key lives in the reserve finds it in a line it has already read, and pays nothing; a key in a block costs a block, as before. With 32-byte records one entry fits, and a reserve of four would be a line of its own, read by every lookup whose tag it holds, which is the same price as a block. The plate draws the first layout. Under the second, a reserve saves the block’s allocation, its filter’s bits and the homing policies’ reads, and saves the successful lookups nothing. The filter’s bits are not nothing: a filter is sized by the keys it holds, as a filter that is allowed to be wrong priced it, and at four entries a region with keys staying the blocks hold two thirds as many keys, so the same false-yes rate costs two thirds of the bits.

The same reasoning sets the largest reserve worth keeping in the header line, and it is smaller than the largest reserve that is free in kicks. Eight entries cost an insertion nothing with keys staying, and they hold 60% of the stopped keys, but eight eight-byte entries are a whole line. Four is where the free line ends, and at 95% load four entries hold about a third of a region’s stopped keys. Lighter tables are better served: at 85% load the same four entries hold nearly two thirds of them.

What the counts depend on #

One seed, one stream of keys. Every number here comes from one sequence of hashes and one churn. The earlier page’s numbers were reproduced exactly, which says the two simulations are one simulation; it says nothing about how far another seed would move a 6.1% or a 0.632. Differences of a few thousandths of a kick, like the two-hundredth the reserve costs at four entries, are below what one seed can rank.

A reserve kept in the header is a layout assumed, not one built. No line was laid out and no bytes were counted; the claim that four eight-byte entries fit beside the counts and the filter is arithmetic about sizes the earlier pages chose. The reads a lookup makes are counted in blocks, not cache misses.

Uniform deletions. As on the earlier page, every stored key is equally likely to be deleted. A workload that deletes old keys first would empty the reserves and blocks faster, because stopped keys are older than average.

Still open: a kick that looks before it moves #

The measurement turned on one number the earlier pages never drew: after churn at 95% load, 13.8% of the table’s entries are empty while 9.2% of its keys are stopped. The cap stops a key because its chain visits three full buckets, and the chain visits them blind: each kick picks a random resident and moves it, without asking whether that resident’s other bucket has room. A bucket of eight holds eight residents, each with an other bucket, and the chance that all eight of those are full is much smaller than the chance that one chosen at random is.

A kick could look before it moves. Before displacing anyone, an insertion could read the other buckets of its first bucket’s residents and move the one whose other bucket has room. That is the first level of the breadth-first search that cuckoo tables with many choices use, and it costs reads: up to eight buckets, one of which is in the same region about once in sixteen and whose count is then free. The measurement that follows gives the insertion that look, at one level and at two, counts the buckets read, the kicks, the stops and the settled overflow, and compares them at the same reads with simply raising the cap. The prediction is that one level of looking removes most of the stops at 95% load, since a stop needs every resident’s other bucket full, and that it costs about three bucket reads an insertion that meets a full first bucket. It could fail on the reads. If a look costs more lines than the kicks it saves, and the overflow it removes is the overflow a header reserve already holds for nothing, then the empty room is reachable and still not worth reaching. The question is whether the 13.8% the chains cannot reach is a property of blind kicks, or a property of a table this full that any search pays as much to cross.