The slack an insertion can reach

Entries found by the rank of their tag took a bucketed cuckoo table whose tags are kept sorted and noticed that the position a tag is found at is an address. It dropped the table’s fixed slots and packed each bucket’s entries in tag order, found by rank. The table has 16,384 slots in buckets of eight, with 32-byte entries. A slotted table at half load spends half its entry array on nothing and holds 66.1 bytes a key; the packed one held 36.1. The price was data movement. An insertion into a packed bucket shifts every entry after its rank, and with entries of several buckets packed into one region, every entry of the later buckets too. With a region for every bucket, an insertion at half load moved 99 bytes where a slotted one moved 36.

That page charged no reallocation: a region was assumed to have room. Its closing section proposed a layout between the two. Pack each group’s entries, but leave a few spare entries at the end of the group’s region, so that an insertion “shifts only the entries after its rank in its own bucket and borrows a slot from the shared slack”. A region that runs out is copied into a larger one, and that copy is charged. The prediction was that a few spare entries a group, for groups of four to sixteen buckets, would keep most of the packed layout’s saving while bringing the bytes an insertion moves back within a small factor of the slotted layout’s.

The measurement builds that layout and charges its copies. It keeps the saving and does not bring the bytes down. The proposal’s own sentence contains the reason: a slot at the end of the region is not one an insertion into an earlier bucket can borrow without moving everything in between.

Slack at the end saves only the copies #

Three packed layouts are built beside the slotted one, on exactly the earlier page’s table: the same keys, hashes, cuckoo kicks and sorted tags. Each group of buckets owns one region of entries, and a region with no free entry left is copied into one larger by a stated number of spare entries, the copy charged at 32 bytes an entry. The layouts differ in where the free entries sit.

• Slack at the end. Entries are packed in bucket order and the free ones follow the last. An insertion shifts every entry after its position in the region.
• Slack spread, region rewritten. Each bucket owns a run of entries with free space at its end, and an insertion shifts only the entries after its rank in its own run. A bucket whose run is full makes the whole region rewrite itself with the free entries spread evenly again.
• Slack spread, nearest gap borrowed. The same runs, but a bucket whose run is full takes a free entry from the nearest bucket that has one, shifting the entries in between by one place. Only a group with no free entry anywhere is copied into a larger region.

At the end of the region, sixteen spare entries bring an insertion from 2,832 bytes moved to 1,109, and thirty-two to 1,073. They never bring it below a thousand. Past a handful of spare entries the curve is flat. The slack is doing one thing: making copies rarer. A region with one free entry is copied at almost every insertion into its group: reaching half load, 8,192 keys, the table copies a region 8,064 times, and each copy moves the group’s whole contents. With thirty-two free entries a region is copied once for every thirty-two insertions into it — 191 copies to half load — and copying falls from 65% of the bytes moved to 5%. The flat part of the curve is what is left when copying has been paid down to nothing, and it is not small.

What remains is shifting, and slack at the end cannot touch it. An insertion into the first bucket of a group of sixteen, at half load, shifts the entries of the fifteen buckets after it: about sixty entries, 1,900 bytes. Averaged over where insertions land, that is the thousand bytes the curve levels at. Counted without reallocation, as the earlier page counted, the same shifting comes to 996 bytes an insertion for groups of sixteen, and the slack’s whole effect is to bring the copies down to nearly nothing on top of it.

The proposal’s sentence assumed that an insertion would shift only its own bucket and “borrow a slot from the shared slack”. The two halves are incompatible when the slack is at the end. The free slot is after the last bucket, and the only way to bring it to an earlier bucket is to move every entry between.

Where the bytes go #

The three layouts spend their bytes on different things, and the plate says which fix each one needs. Slack at the end spends almost nothing on copies once it has a few spare entries, and almost everything on shifts. Rewriting the region whenever a bucket’s run fills spends 84% of its bytes on copies even with thirty-two spare entries. Its shifts are small, but its runs fill often, each bucket’s share of the spare being two entries, and every fill rewrites sixteen buckets’ worth of entries.

The nearest-gap layout sits between. Its shifts are short because the nearest free entry is usually a bucket or two away, and its copies are rare because a whole group has to fill before one happens. With sixteen spare entries a group, one a bucket, a fifth to a third of its bytes are copies and the rest are short shifts, and the total is a third of the slack-at-the-end layout’s.

The rewrite layout fails for a reason worth stating, because it looks like the obvious repair. Spreading the slack evenly gives each bucket one free entry when the group keeps sixteen, and a cuckoo insertion lands in one of two buckets chosen by hash. So the first bucket in a group to receive two insertions since the last rebalance fills its run, and a group of sixteen buckets reaches that point after a handful of insertions — the birthday problem at the scale of a group. Each time, all sixteen buckets’ entries are rewritten to hand the full bucket one more slot. The nearest-gap layout hands it the slot from a neighbour instead, and the neighbour’s entries are the only ones that move.

This is the arrangement the packed memory array uses for keeping a sorted array with fast insertion: gaps spread through the array, an insertion moving elements only as far as the nearest gap, and a rebalance only when a region runs out. The difference here is the scale. The regions are a group of buckets, a few hundred entries, rather than a whole array.

Bytes an insertion moves as the table fills #

As the table fills, every layout moves more, and the gap between them widens. At half load the nearest-gap layout moves 347 bytes an insertion against the slack-at-the-end layout’s 1,109, a third. At 0.9 it moves 1,005 against 6,786, a seventh. Near the top the regions are full and the cuckoo kicks multiply the insertions, so the slack-at-the-end layout pays its long shifts several times over. The nearest-gap layout’s shifts are bounded by the distance to a free entry, and that distance grows only as the group’s free entries run out.

The slotted layout’s own growth separates the two causes. It shifts nothing but tag bytes, so its rise from 36 bytes an insertion at half load to 89 at 0.9 is almost entirely the cuckoo kicks: each kick is another insertion into another bucket, and near full load an arriving key displaces others more often. That factor of 2.5 is the part of the growth every layout inherits. The nearest-gap layout grows by 2.9 times over the same range, little more than the kicks alone. The slack-at-the-end layout grows by 6.1 times, because each of the extra insertions the kicks cause also pays the long shift, and the shifts grow with the load too.

The prediction’s first half holds: the saving survives. At half load the nearest-gap layout with one spare entry a bucket holds 38.3 bytes a key, against the slotted layout’s 66.1 and the earlier page’s unreallocated packing’s 36.1. The spare entries cost two bytes a key and the per-bucket run lengths about a byte a bucket. The second half does not: 347 bytes moved against the slotted layout’s 36 is nearly ten times, not “a small factor”. At 0.9 it is eleven times, 1,005 against 89, while the packed layout’s space advantage has almost vanished: 35.6 bytes a key against 36.7.

Every layout on one plate #

The group size and the amount of slack are two dials, and each point they set is a pair: bytes held a key and bytes an insertion moves.

The plate has two findings. The first is that reallocation doubles the cheapest packed layout’s cost. The earlier page’s best, a region a bucket, moved 99 bytes an insertion at half load with no reallocation charged. Given one spare entry and charged its copies, the same layout moves 211, and with two spare entries, 153. For a region of one bucket, the copy on overflow is the dominant cost, and the slack the proposal wanted is worth having there — as a reallocation policy, not as a shift policy. The exchange rate is visible between the two points: a second spare entry in every bucket’s region costs 3.9 bytes a key held and saves 58 bytes an insertion moved.

The second is that with the nearest gap borrowed, grouping costs little. At one spare entry a bucket, groups of 4, 16 and 64 buckets move 269, 347 and 495 bytes an insertion against a region a bucket’s 211 — at most 2.3 times — where slack at the end for the same groups moves up to 19 times as much. Grouping saves pointers, eight bytes a group instead of a bucket, which at half load is up to two bytes a key. At 32-byte entries that is a small share of what a key holds; for smaller entries it would be the larger part of the packed layout’s overhead, and there the ability to group without paying for it in shifts matters.

What grouping costs, by where the slack is #

With the slack at the end, bytes moved grow in proportion to the group: 39 times as many for groups of 64 as for a region a bucket at 0.9. Every insertion shifts the rest of its group, and the rest of the group grows with it. With the nearest gap borrowed, a group of 64 moves 2.4 times what a region a bucket does at 0.9 and 2.3 times at half load. The distance to the nearest free entry grows much more slowly than the group, because one spare entry a bucket leaves a free entry within a bucket or two almost everywhere.

A tag that answers more than yes sorted a bucket’s tags so that a lookup could stop early, and the earlier page turned that order into an address. What this page adds is that the order has a cost, and that the cost is set by the distance from an insertion to the nearest free place, not by how much free space there is. The bucket that fits a line sized a bucket to a cache line so that a lookup costs one line. A packed layout that keeps its free entries spread gives an insertion a comparable guarantee: it touches the bucket it lands in and, usually, one neighbour.

That guarantee is what makes the shifts cheap in the sense a machine charges. Where insertion sort actually wins found that the shifting insertion sort does costs almost nothing on small arrays, because the elements it moves are adjacent and already in cache. A shift within one bucket’s run and into its neighbour’s is the same kind of move: a few hundred contiguous bytes, one or two cache lines. The slack-at-the-end layout’s shifts are the other kind. A group of sixty-four buckets at 0.9 holds about 460 entries, fifteen kilobytes, and an insertion near its start moves most of them — a cost that the cliff where the data stops fitting would price by whether the region still fits in the cache at all.

What was measured and what was not #

The lookup’s layout is the earlier pages’. A lookup that stops caring how wide an entry is separated the tags from the entries so that a lookup reads the tag array’s line and then one entry, and every layout here keeps that separation. A spread layout adds a byte a bucket of run length beside the tags. Two probes are two misses is the reminder that a cuckoo lookup’s second bucket is a second line, and nothing here changes that.

Bytes, not time. Every cost is bytes moved, as on the earlier page. A shift of a few hundred bytes is a memmove within a cache line or two; a copy of a region is an allocation and a larger memmove. They are counted in the same unit here and priced differently by a machine. The count is not the time is the standing warning.

One table, one seed, one entry size. The table has 16,384 slots and 32-byte entries throughout, built once from one seed. Near full load the number of cuckoo kicks an insertion causes varies most between seeds, so the figures at 0.9 and above are the least certain on these plates, and the ratios between layouts are more trustworthy there than the bytes themselves. Smaller entries make the pointers a larger share of the space, which favours grouping, and make every shift cheaper in bytes, which favours packing.

Regions grow and never shrink. Deletions leave free entries behind and no region is ever made smaller. A table that shrinks and grows would pay copies in both directions, and a workload of mixed inserts and deletes was not measured.

Lookups were not charged. A packed bucket’s entry is found from its group’s pointer, the counts of earlier buckets, and its rank; with runs, from the run lengths instead of the counts. Both are a few bytes of arithmetic in the same line as the tags, and neither was measured as time.

Still open: runs sized by where the insertions land #

Every spread layout here divides the group’s spare evenly among its buckets. But a cuckoo table’s buckets do not fill evenly. A bucket that is some keys’ first choice and others’ second fills faster, and after a kick the displaced key lands in its other bucket, which may be anywhere. The nearest-gap layout pays when a full bucket’s neighbours are full too, and those are the stretches an even division serves worst.

A run could instead be sized by its bucket’s recent history. A bucket that has overflowed its run gets a larger share at the next rebalance, and one that has lost entries a smaller one. That is the adaptive packed memory array’s refinement of the even one, applied at the scale of a group of buckets. The measurement that follows gives each bucket’s run a share of the group’s spare in proportion to its insertions since the last rebalance and compares that with the even division at the same spare. The prediction is that it helps most near full load, where the even division’s shifts grow fastest, and helps little at half load, where almost every bucket has a free entry within reach anyway. The number to watch is whether it brings the moves at 0.9 back towards the half-load figure. That would say how much of the growth with load is the cuckoo kicks’ own cost and how much is slack in the wrong place.