Spare where a bucket can use it

Entries found by the rank of their tag packed a cuckoo table’s 32-byte entries by the rank of their sorted tags. The fixed slots went, and the table held half the bytes of a slotted one at half load, paying for it in bytes shifted on every insertion. The slack an insertion can reach charged the reallocation that layout had assumed away. The best arrangement it found divided each region’s spare entries among the buckets, so each bucket’s entries sit in a run with room at its end. When a bucket’s run was full it borrowed the nearest free slot in the region, shifting the entries between, and it grew the region only when no slot was free. At 16 spare entries a region of sixteen buckets that moved 1,005 bytes an insertion at 90% load, against 6,786 for spare kept at the region’s end, and 347 at half load.

Its closing section questioned the even division. A cuckoo table’s buckets do not fill evenly. A bucket that is some keys’ first choice and others’ second fills faster, and a kick sends a displaced key to its other bucket, wherever that is. So a run could be sized by its bucket’s recent history: when a region redistributes, each bucket gets a share of the spare in proportion to its insertions since the last redistribution. That is the adaptive packed memory array’s refinement of the even one, applied to a region of buckets. The section predicted it would help most near full load, where the even division’s shifts grow fastest. It named the number to watch: whether it brings the bytes moved at 90% load back towards the half-load figure. That would say how much of the growth with load is the kicks’ own cost and how much is slack in the wrong place.

The table, and three ways to divide its spare #

The table is the earlier pages’: 2^16 slots in buckets of eight, two hashes, tags of one byte kept sorted in each bucket, entries of 32 bytes packed in tag order in a region for each sixteen buckets. Keys are inserted up to 95% load with the same hashes and seed, and every byte moved is charged — tags and entries shifted, entries borrowed across a gap, regions copied when they grow. Sixteen spare entries a region is the main setting. The rules differ only in how a region divides its spare when it redistributes. Evenly is the earlier page’s rule. By recent insertions is the proposal: each bucket’s share is proportional to its insertions since the region last redistributed, plus half an insertion so an idle bucket is not left with nothing. By room left weights each bucket by the entries it can still take — eight less what it holds.

Dividing the spare by recent insertions moves more bytes at every load: 1,159 an insertion at 90% load against 1,005 with an even division, and 1,795 against 1,670 at 95%. The prediction was that it would help most near full load, and near full load it hurts. Dividing by room left does what the proposal meant to do. It moves 974 bytes at 90%, 3% under the even division, and 1,502 at 95%, 10% less. At half load both weighted rules move more than the even one, 395 and 409 against 347, because nearly every bucket then has room and a weighting only concentrates spare that an even division would have spread where the next insertions land. Every per-insertion figure is charged since the previous tenth of load, on the earlier page’s grid, so these numbers and that page’s are the same measurement.

Why a bucket’s past is the wrong guide #

A packed memory array divides spare by recent insertions because the elements it stores keep arriving in the same regions: a sorted stream of keys lands where it landed before. A cuckoo bucket is different in one decisive way. It holds at most eight entries, and a key that arrives at a full bucket does not make it grow. It kicks a resident out to that resident’s other bucket.

At 90% load, 65% of the buckets are full, and at 95%, 80%. A full bucket’s run can never use a spare entry. Its count of entries is capped, and every further key that names it is sent elsewhere. A bucket that has taken many insertions since the last redistribution is, more often than not, one of those full buckets. The insertions it took are what filled it. The count the proposal weights by therefore points at the buckets least able to use what it gives them.

The spare’s location confirms it. At 90% load, 71% of an evenly divided spare sits in the runs of full buckets, and 82% of a spare divided by recent insertions; divided by room left, 3%. The even division strands most of the spare simply because most buckets are full and it gives each an equal share. The insertion-weighted division strands more, because it gives more to the buckets that were filling. Room left strands almost none, since a full bucket’s weight is zero. The ordering holds at every load, not just near the top. At half load the insertion-weighted rule already strands 12% of its spare against the even rule’s 6%, and at 70% it strands 39% against 24%. The buckets it favours are always fuller than average, because being filled is what earned them the weight.

Stranded spare is not lost. A bucket whose run is full borrows the nearest free slot in its region, and a free slot in a full bucket’s run can be borrowed by a neighbour, at the price of shifting every entry between. That is why the even division still does tolerably at 90% load. Its stranded spare is used, and it costs a shift each time. It is also why dividing by room saves little at 90% and more at 95%. At 90% the neighbours of a bucket that needs room are still close enough that borrowing is cheap. At 95% they are further apart, and each borrow shifts more. Two probes are two misses found that a cuckoo lookup’s two buckets cost two cache lines. A borrow is the insertion’s version of the same cost: the room a bucket needs is somewhere else in its region, and reaching it moves everything in between.

How much of the growth the spare can reach #

The number the section asked for was whether any division brings 90% load back towards half load. None does. The best, by room left, moves 974 bytes at 90% against 395 at half load, two and a half times as much. The reason is in the kicks.

At 90% load, 635 of the 974 bytes an insertion moves are the kick chain; at 95%, 1,273 of 1,502. A kick removes an entry from a full bucket and places it in its other bucket, shifting the entries after it in both runs. At half load a new key almost always finds room in its first bucket, and kicks cost 20 bytes an insertion. At 95% a new key’s chain of kicks is long, each link a removal and a placement, and the chain is five sixths of the bill. The division of spare changes where a placed entry’s room comes from. It does not change how many placements a key makes before it settles, which is set by the cuckoo table’s two choices and its load. The bucket that fits a line found that buckets of eight let the table build past 95% load at all. The chains that make that possible are the cost this layout cannot shed.

So the answer to the section’s question is not a split at all. From half load to 90%, with the best division, bytes moved an insertion grow by 579, from 395 to 974. The kick chain’s share grows by 615, from 20 to 635. Everything else — placing the new key, borrowing a gap, redistributing a region — falls slightly, from 375 bytes to 339. All of the growth with load is the cuckoo kicks’ own cost. Slack in the wrong place costs something at every load, which is what dividing by room recovers, but it is not what grows.

What the division can change, and when it pays #

The three rules differ in less than it might seem. A region grows when it has no free slot at all, and how many free slots it has does not depend on where they sit. So every rule makes exactly the same redistributions at exactly the same insertions: 444 by half load, 858 by 90%, 896 by 95%, each copying the region into a larger one. Every byte that separates the rules is in the borrowing — the entries shifted when a bucket takes the nearest free slot in its region. By 90% load borrowing is 41% of all bytes moved with an even division, 46% with room left and 50% with recent insertions. A rule for dividing spare is a rule for how far a full run has to reach for a free slot. The question is only which rule leaves free slots nearest to where the next insertions will need them.

In a cuckoo table the next insertions land in buckets with room. A new key goes to its first bucket if that bucket has a free entry, and otherwise a kick moves some resident out to a bucket with room further along the chain. At half load nearly every bucket has room, the next insertions land nearly uniformly, and an even division is the right guess. That is why room left and recent insertions both lose to it there, 395 and 409 bytes against 347. Near full load most buckets have none, the next insertions land in the few that do, and room left is the right guess.

Over the whole fill that makes dividing by room nearly break-even. Summed over every insertion from empty to 95% load, it moves 483 bytes a key against the even division’s 475. It pays more at low loads than it saves at the top. It is the better rule for a table that lives near full load — one that inserts and deletes around 90% for most of its life. For a table filled once and then read, the even division is as good. The layout that is told nothing found a structure that needs no parameter to be near the best at every block size. No division here is best at every load, and the rule that is best near full load needs to know the one thing the even rule does not: how full each bucket is.

When the spare is scarce #

The proposal does help in one regime, and the reason is the same. With four spare entries a region, dividing by recent insertions moves 2,842 bytes an insertion at 95% load against 3,355 for an even division; from sixteen spare up it moves more. Four spare among sixteen buckets means most buckets get none under any rule. An even division hands its four to the first buckets in the region, whatever their state. Recent insertions at least point at buckets in use, and some of those still have room. Dividing by room left does better again at four, 2,605, and at every amount of spare: 1,266 against 1,524 at thirty-two, 17% less.

The even division improves only slowly as spare is added, 1,670 at sixteen and 1,524 at thirty-two, because the extra spare lands mostly in full buckets. Dividing by room gets more from each extra entry: from 1,502 to 1,266 over the same step. When most buckets are full, a spare entry is worth something only in a bucket that can take one, and the rule that knows that turns memory into fewer bytes moved.

What was measured and what was not #

One table, one seed. Every number is one build of 2^16 slots to 95% load, the earlier pages’ hashes and seed. The rules share every insertion and every kick, since the division of spare changes only where entries sit in memory, not which bucket holds them. So the differences between rules are not sampling noise. How they vary over seeds was not measured.

Bytes, not time. The cost charged is bytes moved. The shifts a borrow makes are contiguous, and a real machine moves contiguous bytes far faster than scattered ones. Where an algorithm looks drew that difference, and a byte count treats a long contiguous shift and many short ones alike.

Sixteen buckets a region. Every rule divides the spare of a region of sixteen buckets. A larger region pools more spare and has more buckets with room to give it to, and the earlier page found grouping cheap when the nearest gap is borrowed. A larger region also makes a borrow reach further. How the three rules compare at other region sizes was not measured, and the room rule’s advantage near full load should grow with the region, since it has more non-full buckets to choose among.

A region that fits in cache. A region of sixteen buckets holds about 128 entries of 32 bytes, 4 KB, which fits easily in a first-level cache. The cliff where the data stops fitting found how sharply that stops being true, and a region large enough to fall off it would make every borrowed byte dearer than the byte counts here say.

Room is known exactly. Dividing by room left needs each bucket’s count, which the table keeps anyway — it is how a lookup knows where a bucket’s run ends. The rule costs nothing to compute at redistribution. It would cost more on a structure whose capacity per bucket was not fixed, and a packed memory array’s segments are such a structure. That is why the proposal came from there.

Insertions only. Keys are never deleted. Deletions would empty full buckets, and a bucket that has lost entries is exactly one that can take more, so a rule weighting by room would follow deletions without being told about them. An insertion count would not.

Still open: a region that lends its spare before it runs out #

Every rule here redistributes only when a region has no free slot at all, and the kick chain is what grows with the load. Both suggest the same repair: spend spare on the kicks. When a kick chain is about to place a displaced key into a full bucket, it could look first for a slot in that bucket’s own region and let the key stay, as an overflow entry held in the region’s spare, rather than kicking again.

The measurement that follows gives each region a small overflow for displaced keys, taken from its spare, and caps a key’s kick chain at a stated length, after which the key goes to its region’s overflow. A lookup then checks two buckets and, where they have overflow entries, the overflow of their regions. The prediction is that at 95% load a cap of two kicks halves the bytes moved, since most of the chain’s cost is in its tail, and that the saving is small below 90%, where chains are short and the plate above shows kicks costing a few per cent of the bill. What it costs is lookups: a lookup that misses both buckets must scan an overflow. The question is how many overflow entries a region can hold before that scan costs more than the kicks it saved — which is the trade a tag that answers more than yes made between a bucket’s order and a lookup’s work, now made between a kick and a probe.