A lookup that stops caring how wide an entry is

The bucket that fits a line measured a cuckoo table whose candidates are buckets of eight slots, each bucket aligned to one cache line. It reads at most two lines per lookup at any load it reaches, builds past 0.95, and misses less often than linear probing at every load — and it does all of that because eight eight-byte entries are sixty-four bytes, which is a cache line.

That is arithmetic about alignment, and the arithmetic has one term in it nobody chose. An entry is eight bytes because the table stores a 32-bit key and a 32-bit value. A table of records — a key, a pointer, a length, a timestamp — stores thirty-two bytes or more, and then a bucket of eight is four lines, the bound is gone, and the design that was the best worst case on that page is not.

The second line on that plate is what this page is about, and the shape of it is the whole finding: it does not move. Between four-byte entries and sixty-four-byte entries an inline bucket’s cost multiplies by eight and a tagged bucket’s changes by fifteen thousandths.

The layout #

Store, in a separate array, one byte taken from each key’s hash — a tag. The tag array is indexed exactly as the entry array is, so a bucket’s eight tags are eight contiguous bytes wherever the bucket is and however wide an entry is. Keep the entries themselves in a parallel array.

A lookup then reads its bucket’s eight tag bytes, compares all eight against the query key’s tag, and reads a full entry only at a position where the tag matched. A key the table holds is found by one tag match and one entry read: the tag line and one entry line, two lines, independent of the entry’s width. A key the table does not hold usually matches no tag at all, and then the entries are never touched.

The cost is the extra fetch. At four- and eight-byte entries an inline bucket is already one line, so the tag array adds a whole line to a lookup that did not need one — 2.21 against 1.20. That is the 84% penalty the plate shows at the left, and it is why the design is not simply better.

It is also why the tagged line sits at 2.22 rather than at 2.00. A lookup reads its first bucket’s tags and, on 20.3% of lookups at this load, has to read the second bucket’s too because the key was evicted there; and on 2.0% of lookups a tag matches by accident and a wasted entry line is read. Those two account for the 0.22 above two exactly, and both are measured separately below. Neither has anything to do with the entry’s width, which is why the line is flat.

And the rightmost point is the one place the tagged line moves at all. At 128-byte entries an entry no longer fits in one line, so an entry read costs two, and the tagged layout goes from 2.22 to 3.24. The design makes a lookup independent of the entry’s width only up to the width of a line, which is the same boundary the inline layout ran into, reached for a different reason and two doublings later.

Where it pays #

The crossing is at sixteen bytes an entry, and it is not a property of the design. It is a property of the bucket.

A bucket of $b$ entries of $w$ bytes spans $bw$ bytes and therefore about $bw/64$ lines; $b$ tags span $b$ bytes and are one line for any $b$ up to sixty-four. So the tag line pays whenever $bw > 128$ or so — the inline bucket’s two candidates costing more than the tagged layout’s two tag lines plus an entry — and the crossing moves with the bucket exactly as that says: at buckets of four it is at thirty-two bytes, at eight it is at sixteen, and at sixteen there is no width drawn at which the inline layout wins.

That is worth stating as a design rule because it composes with the earlier page’s rule and partly replaces it. The bucket’s width was chosen to be a cache line. The tag line makes the bucket’s width free, so the bucket can be chosen for what it is actually good at — the load it can be filled to. The bucket that fits a line found that buckets of eight fill past a load of 0.95 where buckets of two stop near 0.85; the table on this page cannot be filled at all to 0.9 with buckets of two. With tags in front, a bucket of sixteen is available at no cost in lines, and it fills higher still.

The lookup that finds nothing #

The plate above is for keys the table holds, which is the case a hash table is usually measured on and not the case that decides a system.

For an absent key the inline bucket has no early exit: it has to read both candidate buckets to the end to know the key is in neither, so it pays $2bw/64$ lines whatever else is true. The tagged layout pays two tag lines and nothing more, and the ratio at 128-byte entries is fifteen to one.

This is the case that matters because a lookup that finds nothing is most of the traffic in the systems these tables are built for. The filter that feeds the table is the arrangement that exists to avoid exactly this cost — a Bloom filter in front of a table, so that a key the table does not hold is rejected without touching it. A tag array is the same idea moved inside the table, and it is strictly better in one respect: it never says yes to a key the table does not hold without also finding out, in one further read, that it was wrong.

What an accident costs #

A tag is one byte of a 32-bit hash, so two different keys share a tag once in 256 times, and every shared tag is an entry read that finds the wrong key.

At eight bits an accident happens on 2.0% of lookups and costs one extra line when it does, so its contribution to the mean is two hundredths of a line against a total of 2.22 — under one per cent. At four bits it happens on 34% of lookups and the mean climbs to 2.50, which is a measurable loss for a saving of 1.5% of the table’s bytes. Eight bits is not a tuned optimum; it is the width at which the accidents stop mattering, and every wider tag buys almost nothing.

One point on that plate is out of order, and the reason is worth carrying. A twelve-bit tag reads 2.36 lines where an eight-bit tag reads 2.22 and a sixteen-bit tag 2.20, although it causes eighteen times fewer accidents than the eight-bit one. Twelve bits is one and a half bytes, so a bucket’s tags span twelve bytes at an offset that is not a multiple of anything, and they straddle a line boundary far more often than eight or sixteen bytes do. The accidents fell and the alignment got worse, and the second effect was larger. That is the same class of finding as the aligned bucket it began with — a bound that was arithmetic about alignment — arriving from the other direction.

Load, and what does not change with it #

Both layouts get slightly dearer as the table fills, and both for the same reason: a fuller table sends more lookups to their second candidate bucket. Neither shows anything like linear probing’s collapse — two probes are two misses measured a linear-probing table reading forty entries and missing 5.23 times per absent-key lookup at a load of 0.9, against a bucketed cuckoo table’s 1.87 — and the flatness is the property the cuckoo family was chosen for.

The tag array does not change that flatness; it makes it hold for entries of any width. The bucketed table’s guarantee was “at most two lines”, proved by an alignment argument that a wider entry breaks. The tagged table’s guarantee is “two tag lines plus one entry line per tag match”, which has no width in it at all, and the widths on the first plate are what that sentence looks like measured.

The bound, restated without a width in it #

It is worth writing the two guarantees side by side, because the difference between them is the point of the design and it is easy to lose in the plates.

The inline bucket’s guarantee. A lookup reads at most two buckets; a bucket of $b$ entries of $w$ bytes, aligned, spans $\lceil bw/64 \rceil$ lines; so a lookup reads at most $2\lceil bw/64 \rceil$ lines. With $b = 8$ and $w = 8$ that is two, which is the number the earlier page was about. The guarantee is true for every $b$ and $w$ and is only useful when $bw \le 64$.

The tagged bucket’s guarantee. A lookup reads at most two tag ranges of $b$ bytes each, which is at most two lines for $b \le 64$, plus one line for each tag that matched. Tags match once for the key itself and, for every other occupied slot examined, with probability $2^{-t}$ for a tag of $t$ bits. So the expected lines are at most $2 + 1 + 2b\lambda 2^{-t}$, where $\lambda$ is the load — and $w$ does not appear.

Putting the measured numbers into the second expression: $b = 8$, $\lambda = 0.9$, $t = 8$ gives $2b\lambda 2^{-t} = 0.056$ accidental entry reads a lookup, against a measured 0.020. The account overstates because it charges both candidate buckets on every lookup and most lookups stop at the first; halving it gives 0.028, which is the right order. The expression is a bound rather than a fit, and the plate is what it looks like when the bound is not tight.

The worst case is worth naming too, because it is unbounded and the mean is not. A lookup whose tag matches every occupied slot in both buckets reads sixteen entries, which at 128-byte entries is thirty-two lines — worse than the inline layout’s worst case. It happens with probability $2^{-8 \times 16}$ on random keys and with probability one against an opponent who can choose keys, which is the same hazard the adversary who knows the seed is about, in a structure where the seed is a hash the caller cannot see. Nothing here measures it.

What is being traded #

Three costs move together here and it is worth separating them.

Lines read. The quantity every plate above counts, and the one the design exists to hold flat.

Bytes held. A one-byte tag on an eight-byte entry is 12.5% more memory; on a 32-byte entry it is 3.1%. The design is therefore cheapest in space exactly where it is most useful in time, which is an unusually comfortable arrangement and is not a coincidence — both quantities are ratios against the entry’s width.

Instructions. Comparing eight tag bytes against one is a single vector comparison on any machine that has one, and comparing eight 32-byte entries is eight comparisons of thirty-two bytes. Nothing here counts instructions, and on a table that fits in cache the instruction count is what decides. The count is not the time is the standing caution, and it applies to this page more sharply than to most: a plate counting lines is a plate about a table that does not fit in cache, and the design being measured is a rearrangement whose other half — the vector comparison — this model cannot see.

The three do not trade against each other evenly, and the shape of the trade is the reason this design is common in practice and rare in textbooks. Bytes and instructions both improve as the entry widens: the tag’s share of memory falls, and comparing tags instead of entries saves more the wider an entry is. Lines improve too, and by the largest factor. A design whose three costs all move the same way with one parameter has no trade-off in that parameter at all — what it has is a threshold, and the threshold is where an entry stops fitting beside its neighbours in one line. The exchange rate nobody wrote down had to construct a conversion between comparisons and moved bytes before it could rank sorting algorithms by record size; here no conversion is needed, because past sixteen bytes every axis agrees.

What is not measured here #

One cache, one line size. Sixty-four bytes, and lines counted rather than misses simulated. A lookup’s two tag lines and one entry line are three distinct lines whether or not any of them was resident, and on a table whose tag array fits in cache entirely — 8,192 bytes here — the tag reads are nearly free and the plate overstates the tagged layout’s cost. That is the case a real implementation aims for, and it is the reason the tag array is kept small.

No deletions and no updates. A tag is derived from the key, so an entry’s tag never changes while the entry lives. A table that supports deletion has to invalidate a tag, and the usual arrangement — a reserved tag value meaning empty — removes one of the 256 tags and costs nothing measurable. Neither is implemented.

One key distribution. Keys are drawn from a shift-register generator and hashed by multiply-shift, so tags are as near uniform as the hash makes them. A tag taken from the same bits of the hash that chose the bucket would be no tag at all — every key in a bucket would share it — and nothing on this page would detect that, because the tag here is taken from a different multiplier.

Present and absent, not a mix. Each plate looks up either only keys the table holds or only keys it does not. A real workload is a mix, and the tagged layout’s advantage scales with the share of lookups that find nothing: at 32-byte entries the two cases read 2.22 and 2.05 tagged lines against 4.81 and 8.00 inline, so the advantage is 2.2× on a hit and 3.9× on a miss and any mix falls between.

The second bucket, not a schedule. A lookup reads its second candidate bucket on 20.3% of hits at a load of 0.9 and on every miss, and nothing here tries to lower that. A table that biased its insertions towards each key’s first bucket would lower it — which is the arrangement the second choice measured for load rather than for locality — and would make the tagged layout’s 2.22 closer to 2.02.

Buckets of two never build. At a load of 0.9 a bucket of two fails, which is the earlier page’s threshold seen from the far side, so the crossing for that bucket is not drawn.

Still open: a tag that answers more than yes or no #

Every tag on this page is a byte compared for equality, and the comparison has one bit of output per slot. The bytes could carry more. A tag whose bits are ordered — the top bits of the key’s hash rather than a scattering of them — would let a bucket’s tags be kept sorted, so that a lookup could stop at the first tag above its own and an insertion could find its place; and the same ordering makes a bucket’s tags a small index over the entries rather than a set of them.

The measurement that follows builds that variant and asks what the ordering costs and buys: how many tag comparisons a lookup makes when it can stop early against the eight it makes now, what the insertion pays to keep eight bytes in order, and whether an ordered tag is measurably worse at its first job — since the top bits of a hash are the bits the bucket index was taken from, and a tag correlated with the bucket is a tag that distinguishes fewer of the keys inside it.