The keys a capped chain leaves behind

Spare where a bucket can use it measured a packed cuckoo table, one whose 32-byte entries sit in tag order in a shared region for every sixteen buckets rather than in fixed slots. It traced every byte of the growth in an insertion’s cost, from half load to 90%, to the kick chain. With the region’s spare divided by the room each bucket had left, an insertion moved 395 bytes at half load, 974 at 90% and 1,502 at 95%, and at 95% the kicks were 1,273 of those bytes. No division of the spare could reach them. A kick removes an entry from a full bucket and places it in its other bucket, and a long chain of those is what makes a nearly full table expensive to fill.

Its closing section proposed to spend spare on the kicks instead. Cap a key’s chain at a stated length, and when the cap is reached put the key still displaced into an overflow held in its region’s spare, rather than kicking again. A lookup would then check its two buckets and the overflows of their regions. The section predicted that at 95% load a cap of two would halve the bytes moved, because most of a chain’s cost is in its tail, and that below 90% the saving would be small because chains are short there. It set the cost against lookups, and asked how many overflow entries a region could hold before scanning them cost more than the kicks they saved.

The table, the cap and two places for the overflow #

The table is the earlier pages’ in every respect: $2^{16}$ slots in buckets of eight, two hash functions, one-byte tags kept sorted in each bucket, 32-byte entries packed in tag order in a region for each sixteen buckets, sixteen spare entries a region divided by room left, and the nearest free slot borrowed when a bucket’s run is full. Keys arrive in the same order from the same seed, and a key whose first bucket is full kicks a resident chosen at random to that resident’s other bucket, which may kick again. Every byte moved is charged, and every figure is charged since the previous tenth of load, so the uncapped numbers here are the earlier page’s to the byte.

The cap stops a chain after a stated number of kicks, from none to eight. The key still displaced when the cap is reached goes to the overflow of the region of the bucket it was bound for and stays there. Two places for that overflow are measured. In the spare, the proposal: the entry takes the free slot nearest its region’s end, so every entry after that slot moves up one place, and a region with no free slot grows as it would for any insertion. In a block: each region keeps a separate block for its overflow, allocated four entries at a time, which an insertion writes without moving anything, at the price of the block’s bytes and a pointer. The table’s content — which key sits in which bucket — is the same in both, so the two differ only in bytes moved and bytes held.

The tail is most of the chain #

Between 90% and 95% load an uncapped insertion makes 4.16 kicks on average, and a cap of two leaves 1.14 — it removes 72% of the kicks. That is the premise of the prediction and it holds. The chain’s length has a long tail. Most keys at 95% load settle within two kicks, and a minority make long walks, bouncing a resident from one full bucket to another until one of them lands in a bucket with room. Capping at eight already removes 30% of the kicks and at four more than half.

The cap has a price in keys as well as in bytes. With a cap of two, 34.3% of the insertions between 90% and 95% load end in the overflow, and by 95% load the overflow holds 3.9% of all the keys in the table. At a cap of eight, 11.5% of the late insertions and 0.8% of all keys. Those numbers are large beside the stash of a handful of slots that an insertion that can fail described, which catches only the rare key whose chain never settles. A cap of two is not a stash for failures. It turns a third of the insertions near full load into overflow entries on purpose, trading the tail of every chain for a list that has to be kept and searched.

Thirteen per cent, where half was predicted #

With the overflow in the region’s spare, a cap of two moves 1,311 bytes an insertion at 95% load against 1,502 uncapped — 13% less, where the prediction said half. At 90% the saving is 6%, 915 bytes against 974. The prediction’s other half holds: below 90% the cap changes nearly nothing, 554 bytes at 70% against 552, because chains there are short and rarely reach two kicks.

With the overflow in a separate block, the same cap moves 734 bytes at 95% load — 51% less — and 731 at 90%, 25% less. That is the prediction, made by a design the section did not propose. The kicks removed are the same kicks in both, since the table’s content is the same. The difference is entirely in what it costs to put a key into the overflow.

A key in the spare costs six kicks #

A key put into the region’s spare costs 1,819 bytes to insert, on average between 90% and 95% load; an uncapped kick costs 306. The cap of two does cut the kick chain’s bytes from 1,273 an insertion to 396. It then spends 624 bytes an insertion putting the stopped keys into the spare, which is 1,819 bytes for each of the 0.34 overflow insertions an insertion makes. Most of what the cap took from the kicks, the overflow gives back.

The overflow insertion is expensive for the same reason a borrow is. The overflow sits at the region’s end, so its entry needs a free slot there. Near full load, with the spare divided by room left, the free slots are in the few buckets that still have room, scattered through the region. The nearest one to the end is often several buckets back, and every entry between it and the end moves up one place to open the slot. At 95% load a region of sixteen full-ish buckets holds more than a hundred entries, and the shift moves a large part of them. The slack an insertion can reach found spare at a region’s end costing 6,786 bytes an insertion at 90% load, against 1,005 for spare spread among the buckets. The overflow reintroduces that layout for one key in three near full load.

The kick, by contrast, is cheap per step because both its halves are local. Removing a resident shifts only the entries after it in its own bucket’s run, and placing it shifts only those after its rank in the other bucket’s. A chain of four kicks is four pairs of local shifts. An overflow insertion into the spare is one shift across much of a region. Six local shifts cost what one long one does.

Every cap, both places #

With the overflow in the spare, no cap saves more than 16% at 95% load, and the best is a cap of one, at 1,265 bytes. The curve is nearly flat because the two costs trade against each other. A lower cap removes more kicks and sends more keys to the expensive overflow, and between one and eight the sum barely moves. At a cap of zero, where no key ever kicks and every key whose first bucket is full goes to the overflow, the table moves 1,361 bytes an insertion, 9% less than uncapped, while holding 12% of its keys in overflow by 95% load.

In a block, every cap saves, and the lower the cap the more: from 1,188 bytes at eight kicks to 734 at two and 316 at none. The block’s overflow insertion writes one entry and a tag, 33 bytes, so every kick removed is a saving. The block costs memory: the table holds 36.0 bytes a key at 95% load with a cap of two against 35.0 uncapped, and between 35.6 and 36.0 across the caps. The blocks themselves hold 1.7 bytes a key at a cap of two — their entries, allocated four at a time, and a pointer for each region that has one — and the regions, holding fewer entries, need a little less spare, so the table’s total rises by one byte a key. It is small beside the 768 bytes an insertion the cap of two saves near full load, and it is held for the table’s life, where the saving is paid only while it fills.

What a lookup pays #

At 95% load with a cap of two, a lookup for a key that is not there must compare 9.4 overflow entries, and every such lookup meets a region with an overflow. It cannot answer no after reading its two buckets, since the key might have been stopped by a cap and put aside. At a cap of eight it compares 1.9 entries, and 82% of such lookups meet an overflow at all; at 90% load, 0.4 entries and 31%. A lookup for a key that is present stops as soon as it finds it, so only the 3.9% of keys that live in the overflow pay a scan when they are found.

How much a scan costs depends on how the overflow is stored, and that is where the two places differ again. An overflow in the spare sits at the end of the region, beyond the buckets’ runs, and reaching it means reading past them. An overflow in a block is somewhere else in memory, and reaching it is a pointer followed to another cache line. Either way the lookup that used to read two buckets, which two probes are two misses priced at two cache lines, now reads a third. If the overflow’s tags are packed together, 9.4 of them fit in that one line, so the extra cost is one line rather than 9.4 entries. So the cap of two, with the overflow in a block, costs every failed lookup at 95% load one extra line, about half as much again as the lookup cost before.

That gives the exchange rate the section asked for. At 95% load the cap of two in a block saves 768 bytes an insertion, about twelve 64-byte lines, and costs one line a failed lookup. It pays for a table that sees fewer than about twelve failed lookups for every insertion near full load, and loses for one that sees more. A table that is filled once and then queried is the second kind. A table that inserts and deletes around 95% load for its whole life, with a write for every few reads, is the first. A tag that answers more than yes made the same kind of trade between a bucket’s order and a lookup’s work, and it came out the same way: the right answer depends on the ratio of writes to reads, which the table cannot see from its own structure.

Where the prediction went wrong #

The prediction had the right premise and the wrong accounting. The tail of the chain is most of the chain, and removing it removes most of the kicks’ bytes. What the prediction did not price was the destination. A key that stops kicking still has to be stored somewhere, and in a packed table storage costs moves. The spare at a region’s end was chosen because it was already there, and the earlier pages had already measured what storing at a region’s end costs: the most expensive layout of the three they tried.

A cap is a way of choosing where the last few keys go. With the overflow in the spare, they go to the least convenient place in the region. With it in a block, they go somewhere that costs a pointer and a line on lookup and nothing on insertion. The block is not free. It is a second structure, its bytes are held for the table’s life, and every failed lookup reads it near full load. But the cost it moves is the one the section asked about, from insertions to lookups, where the spare moved it from kicks to shifts and saved very little.

The bucket that fits a line found that buckets of eight let a cuckoo table build past 95% load at all. What it bought with the eighth slot was room for chains to settle. A cap spends that room differently: it lets chains stop before they settle and keeps the unsettled keys to one side, which is the stash of a handful of slots, generalised to a third of the insertions near full load.

The limits of the measurement #

One table, one seed. Every number is one fill of a table of $2^{16}$ slots with one sequence of keys and one sequence of random victims. The uncapped figures reproduce the earlier page’s to the byte, which checks the accounting but not the variance across seeds.

Overflow keys stay in the overflow. A key put aside is never moved back into a bucket, even when a later kick frees room in one of its buckets. A table that reinserted overflow keys opportunistically would hold fewer of them and pay for the reinsertions in moves; that is not measured.

The overflow in the spare takes the free slot nearest the region’s end. A design that let an overflow entry take the free slot nearest the bucket it was bound for, with a small index of where each overflow entry sits, would pay a borrow’s cost rather than a shift across the region. It would also need that index on every lookup. It is the obvious middle design and it was not built.

Lookups are counted in entries and in regions reached, not timed. The extra line a failed lookup reads is an argument from the layout, with the overflow’s tags assumed packed in one line; it was not measured in cache misses. The cliff where the data stops fitting measured what a line costs once a table stops fitting in cache.

Still open: a lookup that knows when it can skip the overflow #

Every failed lookup at 95% load with a cap of two reads an overflow, because it cannot know whether the key it seeks was stopped by the cap. A region could say so. If each overflow entry’s key were also recorded in a small filter per region — a few bits a key, like the Bloom filters that a floor on the bits weighed — a failed lookup would read the filter, which sits beside the region’s header in the line it reads anyway, and follow the pointer to the block only on a yes.

The measurement that follows gives each region’s overflow a filter at a stated number of bits a key and counts, for absent keys, how often the lookup still has to reach the block, at every cap and at 90% and 95% load. The prediction is that at eight bits a key the share of failed lookups that reach the block falls from 100% to about 2% at a cap of two. That would take the cost of the cap from one line on every failed lookup to one line on one lookup in fifty, and move the exchange rate from twelve lookups an insertion to several hundred. What it costs is the filter’s bits, a few per overflow key, and the filter’s updates on every overflow insertion. The question is whether a structure that exists to spare the table its kicks can be made invisible to the lookups too, or whether any overflow near full load is a cost every read has to share.