A kick that looks before it moves

Room the chains could not reach ended on a number the earlier pages had not drawn. A cuckoo table of 16,384 entries in buckets of eight, filled to 95% and churned — a random key deleted and a fresh one inserted, 131,072 times — keeps 9.2% of its keys in overflow blocks, because its kick chain is capped at two kicks and a key still homeless after two kicks is filed in its region’s block. And after the churn, 13.8% of the table’s entries stand empty. The keys outside their buckets and the room inside them coexist. That page tried keeping some of each region’s entries aside for the stopped keys and found it only moved them: a key is stopped by the buckets its chain visits, never by a region short of room.

Its closing section traced the stops to how the chain visits buckets. A kick picks a random resident of a full bucket, moves it to its other bucket, and if that bucket is full too, kicks again. It moves blind, without asking whether the resident’s other bucket has room. A full bucket holds eight residents, each with another bucket, and the chance that all eight of those are full is much smaller than the chance that one chosen at random is. So the proposal was a kick that looks first: before displacing anyone, read the other buckets of the full bucket’s residents and move one whose other bucket has room. That is the first level of the breadth-first search that cuckoo tables with many choices use, and a table of buckets has many choices in effect: the bucket that fits a line gave each of a key’s two candidates eight slots, which is what let it build past a load of 0.95 at all. It predicted that one level of looking removes most of the stops at 95% load for about three bucket reads an insertion that meets a full first bucket, and set the test that matters: compare it, at the same reads, with simply raising the cap.

The table, and what an insertion is charged #

Everything but the insertion is the earlier pages’. The table has 16,384 entries in 2,048 buckets of eight and two hash choices a key, and each region of sixteen buckets has one overflow block. A stopped key is filed in the block of its first bucket’s region and stays there until it is deleted, the policy those pages called keys that stay. The churn is eight rounds of deletion and insertion after the fill, and what is reported is the share of keys in overflow settled over the second half of the churn.

Three insertions are compared. The blind kick is the earlier pages’: under a cap of c kicks, a full bucket’s random resident is displaced to its other bucket, up to c times, and the key still displaced after that is filed in overflow. Here the cap runs from two, the earlier pages’ setting, to 64. The one-level look reads, at every full bucket the insertion meets, the other bucket of each of its residents in turn and stops at the first with room; that resident moves there and the arriving key takes its slot. If none has room it falls back to a blind kick, under a cap of nought to four. The two-level look, finding no room at the first level, reads the other buckets of the residents of each of those full buckets in turn, and the first with room moves a resident two steps along the path. It never kicks blind.

Two costs are counted. A bucket read is one bucket’s contents brought in to be examined: the first bucket, each bucket a kick moves to, each bucket a look examines. A look that examines a bucket in the region it is already reading, one in sixteen, is not charged, the proposal’s own rule. An entry written is a key placed in a slot, a key displaced into another bucket, or a key filed in overflow. The second was not in the proposal. It is here because the keys a capped chain leaves behind, the page that introduced the cap, introduced it to stop the chain’s writes: at 95% load five sixths of the bytes a packed table moved on an insertion were its kicks, and a cap of two removed 72% of the kicks.

The room is reachable #

One level of looking under the same cap of two holds the overflow at 0.20% of the keys, against 9.20% for blind kicks; two levels hold it at nought. The proposal’s first prediction is right, and by more than it said. One level finds a resident whose other bucket has room at 86% of the full buckets it looks at, and the 14% where it finds none fall back to blind kicks, of which there are now 0.11 an insertion rather than 0.63. Two levels find room every time.

The trace says how the blind table reaches its 9.2%. After the fill the overflow is 3.7%, and the churn ratchets it up. A deletion frees a slot in a bucket, and the next insertion’s first bucket is almost never that one, so the freed room sits there while stopped keys accumulate. The looks drain the ratchet: a key deleted from a bucket leaves room that a later look can find from any bucket that shares a resident with it, and with eight residents a bucket and two choices a key, a bucket is a neighbour of up to eight others.

The 13.8% of empty entries, then, was not unreachable. With one level of looking the empty share at the end of the churn is 5.2%, and with two it is 5.0% — the floor at 95% load, every key in a bucket and nothing in overflow. The proposal asked whether the empty room is a property of blind kicks or of a table this full. It is a property of something narrower, and the next plate shows what.

The same room for the same reads, blind #

Blind kicks under a cap of 32 leave 0.02% of keys in overflow for 4.23 bucket reads an insertion, and under a cap of 64 none for the same 4.23; the two-level look leaves none for 4.31, and the one-level look under a cap of two leaves 0.20% for 4.34. At equal reads, raising the cap does as well as looking, and at the reads where both reach the floor, blind is a twelfth of a bucket cheaper. The empty room was never out of a blind chain’s reach. The cap of two kept it empty.

The curves explain why. The one-level look is no better than blind kicks at any number of reads: under a cap of nought it holds 2.87% at 2.88 reads, where blind kicks under a cap of eight hold 2.62% at 2.80, and under a cap of one it holds 0.76% at 3.86, against blind’s 0.68% at 3.72 under a cap of sixteen. Each of those is a close pair, and at every one the blind chain is a little ahead. The reads per insertion end, for every design that empties the overflow, at about four and a quarter, which looks like a property of the table at this load: the average distance, in buckets, from a full bucket to room. A look reaches that room by reading sideways and a blind chain by walking, and the walk is not longer on average.

The prediction’s other number was wrong in the other direction. An insertion that meets a full first bucket reads 5.7 buckets with one level of looking, not about three, because the look reads residents’ other buckets in turn until one has room and at 95% load the first few are usually full. The look examines 3.2 buckets for every insertion, about four and a half on each insertion that meets a full bucket — over half of that bucket’s eight residents.

Where the reads and the writes go #

Every design that empties the overflow reads about four and a quarter buckets an insertion; the blind chain under a cap of 64 writes 4.23 entries an insertion doing it, and either look writes 1.82. The reads are nearly the same and the writes differ by a factor of 2.3. That is the difference between the two ways of reaching room, and it is exactly the cost the cap was set to control.

A blind chain writes at every step. An insertion that can fail described cuckoo hashing as a structure that buys a worst case on lookups and pays for it in construction, and the chain is where that payment is made. Each kick displaces a resident to make room for the key arriving, so a chain of k kicks writes k + 1 entries, and its reads and its writes are the same number. A look writes only once it has found room: one resident moved to its other bucket and the arriving key placed, two writes, or three along a two-step path. Everything it read on the way it leaves where it was. The 1.82 is the 1.0 of every insertion that finds room at its first bucket and the two or three writes of the 71% that do not.

The keys a capped chain leaves behind introduced the cap of two because, on a table whose entries are packed, a kick moves bytes and the chain’s tail was most of them. Raising the cap buys the empty room back with exactly the writes the cap was saving. The cap of 64 that reaches the room blind writes 2.6 times as many entries as the cap of two, which was the whole of the earlier page’s saving and more. The look reaches the same room for 0.19 writes an insertion more than the cap of two, and its extra cost is in reads.

So the right comparison is not the one the proposal named, look against cap at the same reads, where the two tie. It is look against cap at the same writes, and there the look holds the overflow at nought for 1.82 writes an insertion where blind kicks under a cap of three write 1.87 and hold 6.94%.

The worst insertions #

The worst insertions cost about the same however the room is reached: more than sixteen buckets are read by 1.71% of insertions blind under a cap of 64, 2.19% with one level of looking and 1.91% with two. The longest single insertions read 52, 27 and 49 buckets. A look bounds its reads by its depth — eight at one level, up to 72 at two — and a blind chain bounds them by its cap, so each has a worst case its parameters set, and at 95% load none of them comes near it often.

The one-level look under a cap of two has the shortest worst case, 27 reads, because it can look at most three times — at the first bucket and at each of the two buckets its blind kicks reach — and each look reads at most eight. It also leaves 0.20% in overflow, which is the price of the bound. The two-level look and the long blind chain spend their worst cases on the same rare insertions: the ones whose neighbourhood of buckets is full to some depth. Both pay about fifty reads for those, and the look writes three entries at the end of them where the blind chain writes fifty.

The tail matters more than the mean in a table that must answer lookups while it inserts. An insertion that holds a lock across its reads holds it for as long as the worst insertion reads; one that writes along a chain leaves the table inconsistent for as long as the chain is in flight, unless the chain is first found and then executed. A look is the second shape by construction — it finds the path, then moves — which is why the published cuckoo tables that serve readers concurrently search before they kick. Nothing here measures concurrency; the plate measures the reads, and the reads are the same.

At higher loads #

At 97% load the two-level look still leaves only 0.01% in overflow, for 2.06 entries written an insertion; blind kicks under a cap of 64 leave 0.02% and write 7.17. The reads are 7.03 and 7.17 — still within a fifth of a bucket — and the writes differ by a factor of three and a half. At 98% the two-level look reads 10.14 buckets and writes 2.24, and the blind chain reads 10.10 and writes 10.10, and both leave a little in overflow, 0.10% and 0.17%.

The one-level look loses ground as the load rises, 0.89% at 97% and 1.50% at 98%, because at those loads a full bucket’s residents’ other buckets are full more often than not and the fallback to two blind kicks runs out. At 90% every design but the blind cap of two empties the overflow and nobody reads much: 2.29 to 2.43 buckets. The cost of reaching room rises steeply with the load and it is the same for a look and a walk, read for read. What the load does not change is that the walk writes everything it reads.

What the cap was for #

The earlier pages read the cap of two as a bound on the chain, and the overflow as what the bound cost. This page reads them the other way. The cap is a choice of which resource to spend on placing a key: under a cap of two the table spends overflow — 9.2% of its keys a block away from their lookups — and saves writes; under a cap of 64 it spends writes and saves overflow. A look offers a third resource to spend, reads, and it is the only one of the three a table can spend without moving anything. At 95% load it buys the empty room with 2.7 extra bucket reads an insertion over the cap of two, and 0.2 extra writes.

Whether that is a good trade depends on what a write costs against a read, and that is a property of the memory the table lives in, not of the table. In the packed table where the cap was introduced, a write moved bytes along a region, and the earlier page found the chain’s writes were five sixths of everything an insertion moved, so there the look wins outright. In a slotted table in ordinary memory a write is one store to a line already read, and there the blind chain under a high cap is as good and simpler. The table’s arithmetic is the same in both. The block already open priced the overflow by the lookups that have to read a block, and the cap turns out to be a choice between that price and the writes, with the look as a way to pay neither in exchange for reads.

What one table cannot say #

One geometry. Every number is a table of 16,384 entries in buckets of eight with two choices. Buckets of four have half as many residents to look at and the look’s advantage in finding room would be smaller; more choices a key would give a blind chain more places to go, the trade more hashes or wider buckets measured for building a table rather than churning one. Neither was run.

The order of a look. The look examines residents in the order they sit in the bucket and stops at the first with room. A look that chose the resident whose other bucket has the most room, or that preferred a bucket in the region already read, would read the same and might leave the table better arranged for the next insertion. Only first-found was measured.

Writes counted, not priced. An entry written is one unit whatever it costs. In a table packed by tag rank, as in entries found by the rank of their tag, a write shifts every entry after it in its region; in a slotted table it is one store. The packed table’s writes moved bytes in proportion to how far a region’s entries shifted, and the earlier pages priced that in bytes; this page counts writes and makes no claim about bytes beyond the earlier page’s ratio.

Still open: a look that leaves the most room behind #

The look stops at the first resident whose other bucket has room, and that choice decides where the next insertion will find room. Moving a resident into a bucket with one free slot fills that bucket; moving it into one with three free leaves two. A look that read all eight residents’ other buckets before choosing — which it often does anyway, since at 95% load the first with room is on average the third or fourth — could move the resident to the emptiest, and spread the table’s free slots rather than consume them where they are found.

The measurement that follows gives the one-level look that rule under a cap of two, counts the reads it adds, and tracks the overflow, the reads per insertion and the distribution of free slots per bucket through the churn at 95% and 97% load. The prediction is that it reads about 1.5 more buckets an insertion than the first-found look, since it always reads all eight, and in exchange holds the overflow at nought where the first-found look holds 0.20% at 95% and 0.89% at 97%, because buckets with exactly one free slot become rarer and a look’s chance of finding room rises. It could fail on the spread itself: a table at 95% has one free slot for every twenty entries, and moving keys toward empty buckets may only shuffle where the full buckets are without making any fewer of them. The question is whether a look can make the table easier for the insertions after it, or whether at a given load the shape of the free room is fixed by the load and every placement rule meets the same full buckets in a different order.