Entries found by the rank of their tag

A tag that answers more than yes kept a cuckoo table’s one-byte tags sorted within each bucket, so a lookup could stop at the first tag above its own. That saved comparisons and no cache lines, and the page said so. Its closing section noticed a second consequence it had not used. A sorted array of tags is not only stoppable; it is an index. The position a tag is found at is a rank, and a rank is exactly what a compact structure uses to address an entry without a slot of its own.

The design it proposed gives entries no fixed slots at all. A bucket of eight slots holding five keys stores five entries, packed in the order of their tags, and the tag array becomes the only thing that knows where anything is. The section asked what that saves at each load, what it costs an insertion that must now shift entries as well as tags, and whether the saving survives the entry’s width, since shifting a 32-byte record is a different price from shifting a byte. It predicted that packing would pay below about 70% load, where a slotted table’s slack is most of its space, and lose above it.

That prediction is wrong in an instructive way. The space saving and the insertion cost do not cross at a load. They are two different currencies that both grow with the load, and which one dominates is set by the entry’s width and by how often the table is written.

One bucket, two layouts #

The slotted layout is the one a lookup that stops caring how wide an entry is measured. A separate array of tag bytes, eight to a bucket, sits in front of a parallel array of entries, eight to a bucket, and slot $i$’s tag describes slot $i$’s entry. Every slot has an entry’s worth of bytes whether or not a key lives there.

The packed layout keeps the same tags in the same order and throws the empty slots away. A bucket’s entries are stored contiguously in tag order, so the entry for the tag at rank $r$ is the $r$-th entry of the bucket. What is lost is the fixed address. A bucket’s first entry is no longer at bucket index times eight; it is wherever the entries of the buckets before it end. So the packed layout needs one more piece of state: a pointer to the start of each group of buckets, eight bytes a group. A bucket’s start is then its group’s pointer plus the counts of the buckets before it in the group. Both layouts keep a four-bit count per bucket already, so the pointers are the whole of the packed layout’s extra state.

That is a small rank directory, the structure rank is the only thing it does measured at the scale of bits: a stored position for every block, and a count within the block. Here the “bits” are buckets’ counts and the block is a group of buckets, and the same trade arrives: a pointer per small group is fast to use and costs space, a pointer per large group is cheap and costs work.

The measurement builds one cuckoo table of 16,384 slots in buckets of eight, with the ordered tag of the earlier page, inserting keys until the load reaches 0.95 and recording at each load along the way. The slotted and packed layouts hold the same keys in the same buckets in the same order, so every difference between them is the layout. Bytes held count tags, counts, pointers and entries. Bytes moved count every byte an insertion shifts or writes: the tag bytes after its position, the entries after its rank in the group’s region, the entry itself, and the same again for every cuckoo kick, which removes a key from one bucket and inserts it in another.

What the empty slots were costing #

At half load the slotted table holds 66.1 bytes a key and the packed one 36.1, with a pointer for every bucket. The slotted table spends half its entry array on slots with nothing in them. At a load of 0.2 the gap is fourfold, 165.3 against 42.3. The packed line is nearly flat and sits just above the entry’s own 32 bytes, because apart from the entries it holds only a tag byte a slot, half a byte of count a bucket, and its pointers. The slotted line is a hyperbola, the entry array’s fixed size divided by the keys.

The gap closes as the table fills, because the empty slots are what the packed layout saves and they run out. At 0.9 the slotted table holds 36.7 bytes a key and the packed 34.3; at 0.95, 34.8 and 34.2. Larger groups save a little more at every load, because a pointer shared by sixteen buckets is half a byte a bucket rather than eight: 33.2 bytes a key at 0.9 with groups of sixteen, against 34.3 with one a bucket.

So on the space axis the prediction is wrong in its direction. Packing does not stop paying above 70% load; at 32-byte entries it pays at every load measured, and pays least where the table is fullest. That is the opposite of a trade that turns over. It is a saving that shrinks towards nothing, and whether it ever turns into a loss depends on the entry’s width.

The width at which a pointer costs more than it saves #

A pointer a bucket is eight bytes shared by eight slots: one byte a slot. An empty slot’s entry is $w$ bytes. The packed layout saves $w$ bytes on every empty slot and pays one on every slot, so it holds fewer bytes exactly when the share of empty slots exceeds $1/w$, which is a load below $1 - 1/w$. For 8-byte entries that is a load of 0.875, and the plate crosses one between 0.85 and 0.9. For 16-byte entries it is 0.9375, crossed between 0.9 and 0.95. For 32 and 64 bytes it is 0.97 and 0.98, beyond anything measured.

So there is a load above which packing loses on space, as the prediction said, but it is set by the width and it is high: seven eighths for the narrowest entries measured, and nearly full for the widest. A table of 8-byte keys run at 0.9 should keep its slots; a table of 64-byte records should pack at any load it can reach. Larger groups push the crossing further, since a pointer shared by more buckets costs less a slot. At groups of sixteen it is eight bytes per 128 slots, a sixteenth of a byte a slot, and the crossing is almost at a full table for any width.

What an insertion pays #

The space saving is only half of the design. The other half is what happens when a key arrives.

A slotted insertion writes its entry and shifts the tag bytes after it in the bucket, a few bytes. At half load it moves 36 bytes, which is barely more than the 32-byte entry itself. A packed insertion with a pointer a bucket must also shift every entry after its rank within the bucket, 99 bytes at half load and 586 at 0.9. With a pointer per group, it shifts every entry after its rank in the whole group’s region, and that is where the price runs away: at 0.9, 8,010 bytes an insertion with groups of sixteen buckets, and 31,914 with groups of sixty-four.

The costs rise with the load for two reasons that compound. A fuller bucket and a fuller group have more entries after any given rank, so each placement shifts more. And a fuller cuckoo table kicks more: by the time it reaches 0.9 it has made a quarter of a kick for every key inserted, and by 0.95 nearly half, and each kick is a removal and an insertion, each paying its own shift. Between them the slotted layout’s cost triples from half load to 0.9, and the packed layout’s with a pointer a bucket rises sixfold.

This is the quantity the prediction was reaching for. The trade does get worse with load, but not because the saving turns into a loss. The saving shrinks while the price of each insertion grows, so the ratio between them worsens steeply. At half load a packed insertion costs 2.7 times a slotted one’s bytes moved and saves 30 bytes a key held. At 0.9 it costs 5.6 times and saves 2.4.

Two currencies, and the rate between them #

Bytes held and bytes moved are not the same kind of cost. A byte held is paid for as long as the key is in the table. A byte moved is paid once, on the insertion that moves it, as a memory copy. The writes nobody counted is the page on why a byte moved is a cost a store pays and an operation count ignores. Here both kinds are counted and neither can be converted into the other without knowing how long a key stays.

The group size is the dial between them, and it barely turns the space axis while it spins the other. From a pointer a bucket to a pointer per sixty-four buckets, the saving at 0.7 goes from 12.3 bytes a key to 13.7 — 11% more — while the extra bytes an insertion moves go from 124 to 7,889, sixty-four times more. Almost all of the saving comes from dropping the empty slots, and almost none from economising on pointers. A pointer a bucket is the only group size worth having at this width, and at narrower widths the case is stronger, because there the pointers were the only thing packing could lose on.

With a pointer a bucket, the rate is 12.3 bytes held against 124 bytes moved: each byte a key no longer holds costs about ten bytes of copying, paid once, when the key arrives. That makes the rule simple in the two cases that matter. A table that is loaded once and read many times — a static index, the construction of a lookup structure from a known key set — should pack, and pack at whatever load it can reach, because every byte moved is paid once and every byte saved is paid back on every read of the memory it no longer occupies. A table that is written constantly, whose keys arrive and leave as fast as they are read, should keep its slots, because there the moves are paid on every operation and the slots are held for the same short time the keys are.

The load a packed table can afford #

There is a reading of the two plates together that neither shows alone, and it changes what a designer should do with a packed table.

A slotted table is run full because its empty slots are expensive. The bucket that fits a line built its cuckoo tables past a load of 0.95 for exactly that reason, and a table at 0.9 holds 36.7 bytes a key with 32-byte entries and moves 105 bytes an insertion. A packed table’s empty slots cost one tag byte each and nothing more, so it has no reason to run full. Run at half load, it holds 36.1 bytes a key and moves 99 bytes an insertion.

A packed table at half load and a slotted table at 0.9 are the same on both axes, to within 2%. The packed table is then the better table on every axis the plates do not draw. At half load a cuckoo table with buckets of eight almost never kicks — a hundredth of a kick per key inserted, against a quarter at 0.9. Its buckets hold four keys on average rather than seven, so a lookup compares fewer tags, and the sorted tag’s early stop from the earlier page has shorter buckets to stop in. Two more advantages follow from the same arithmetic and were not measured: a lookup for a stored key should find it in its first bucket far more often, because the first bucket was rarely full when the key arrived, and a burst of insertions that would push a slotted table past its building limit has room to land.

So the rank-addressed layout is less a way of shrinking a table than a way of moving its operating point. The slack a hash table needs in order to be fast stops costing an entry per slot, and the table can keep that slack at the price of a tag byte. That is the same move the count that was already there made with a bit vector’s ranks: information the structure was already keeping, read as an address, turns a cost that was paid in space into one paid in a little arithmetic.

What a lookup reads #

Nothing above changes a lookup’s count of tag comparisons, since the tags are the same tags in the same order. What changes is how the entry is found: a slotted lookup computes the entry’s address from the bucket and the slot, and a packed one adds the group pointer and the counts of the earlier buckets in the group. With a pointer a bucket there are no earlier buckets, so the entry is at the bucket’s pointer plus the tag’s rank.

In cache lines the difference is one small read. A bucket’s eight tags are eight bytes and its pointer is eight more, so interleaving pointers with tags puts four buckets’ tags and pointers in one 64-byte line where the slotted layout puts eight buckets’ tags. A lookup still reads one line to find its tag and one to fetch its entry, and the tag array is twice as large as before, 2 bytes a slot rather than 1. None of that was simulated here; it is the arithmetic of where the pointer is stored, and the space the model does not see is the reminder that the allocator’s own bookkeeping for sixteen thousand small regions would add to it.

What was measured and what was not #

One table, one seed, one bucket size. 16,384 slots in buckets of eight, built by one sequence of random keys to a load of 0.95. The cuckoo kicks are the random-walk kicks of the earlier pages. A different bucket size changes how many entries sit after a rank, and so every packed cost, roughly in proportion.

Regions are assumed to have room. A packed group’s region grows by one entry an insertion and shrinks by one a removal. The model charges the entries shifted inside the region and not the reallocation that a region with no spare room would need; a real design either over-allocates each region, giving back part of the saving, or reallocates, adding a copy of the whole region now and then. Measuring what an algorithm keeps is the page on why a structure’s footprint and its allocations are separate measurements.

Bytes moved are not time. A memory copy of 586 bytes is ten cache lines, done by an instruction that moves them at the machine’s copy bandwidth, and it is not comparable to 586 separate one-byte writes. The plates count bytes because bytes are what the layout decides; how long a copy takes is the count is not the time in another form.

No deletion measured on its own. Every removal here is a cuckoo kick, immediately followed by an insertion elsewhere. A workload with deletions would pay the shift on the way out as well, and would leave the packed layout’s space accounting unchanged — which is the packed layout’s advantage over a slotted table with tombstones, and not measured.

Still open: a region that keeps its slack at the end #

The packed layout pays for its compactness in shifts because entries after an insertion’s rank have nowhere to go but along. The slotted layout pays for its cheap insertions in slack, spread evenly through every bucket whether or not that bucket will ever need it. There is an arrangement between them: pack each group’s entries, but leave a few empty entries at the end of the group’s region, so an insertion shifts only the entries after its rank in its own bucket and borrows a slot from the shared slack at the end.

The measurement that follows gives every group of $G$ buckets a region with $s$ spare entries shared among them, and charges a region that runs out of spare the copy of the whole region into a larger one. It sweeps $s$ and $G$ at loads from half to 0.95. The prediction is that a few spare entries per group of four to sixteen buckets holds most of the packed layout’s saving — the empty slots are gone except the $s$ per group — while bringing an insertion’s bytes moved back to within a small factor of the slotted layout’s. That would make packing a question of how much slack to keep and where, rather than a choice between a compact table and a writable one.