A tag that answers more than yes

A lookup that stops caring how wide an entry is put one byte of each key’s hash in an array of its own, in front of the entries. A lookup reads its bucket’s eight tag bytes, compares them all, and reads a full entry only where a tag matches — so a hit touches the tag line and one entry line whatever an entry weighs, and a miss usually touches no entry at all.

It ended on an observation about the comparison rather than the layout. Every tag on that page is a byte compared for equality, and the comparison has one bit of output per slot: this tag matches, or it does not. The bytes could carry more. A tag whose bits are ordered — a field of the hash read as a number rather than a scattering of it — would let a bucket’s tags be kept sorted, so a lookup could stop at the first tag above its own and an insertion could find its place.

That page also named the hazard in the same breath, and it turns out to be the whole of the subject.

Three ways to cut a tag out of a hash #

A key’s 32-bit hash is a field, and a bucket index and a tag are two cuts out of it. There are three that a designer would reach for.

A second hash. The tag is the top bits of a different multiplication. This is what the unordered design uses, and it is independent of the bucket index by construction.

The bits below the bucket index. The bucket index takes the top ten bits of a hash; the tag takes the next eight. Read as a number the tag is ordered, so a bucket’s tags can be sorted — and the two fields are disjoint, so the tag is still independent of which bucket a key landed in.

The top bits of the same hash. Also ordered, also sortable, and the bits are the bucket index’s own.

The third is the obvious one, and it is a trap.

Sorting the bits below the bucket index answers an absent key in 8.97 tag comparisons instead of 14.43 — a saving of 38% — and reads the same 0.057 entries. That is the design working exactly as intended.

Taking the tag from the bucket’s own bits reads 5.743 entries on an absent key against 0.054, a hundred and seven times more, while saving nothing worth having on the comparisons. The tag has stopped being a tag.

Why the third cut destroys the tag #

The failure is not subtle once it is measured directly. A tag exists to distinguish the keys inside a bucket. So count how many distinct tags a bucket actually holds, per key in it.

A key is in bucket $b$ because the top ten bits of its hash are $b$. Every key in the bucket therefore has the same top ten bits, and a tag cut from them is the same for all of them. It is not a poor discriminator; it is a constant.

The curve says so precisely: the overlapping tag separates about a third of a bucket at 4, 6, 8 and 10 bits alike — a third being what the bucket’s own duplicate-free structure gives for nothing — and starts to move only at 12, where two bits of it stick out past the index. At 16 bits, six bits stick out and it separates 0.973.

The useful width of that tag is its width minus the index’s, and at eight bits that is a negative number.

The independent tag halves its entry reads for every bit added, which is what a fingerprint does: one more bit is one more halving of the chance of an accident. The overlapping tag is flat for ten bits and then joins the same slope, two decades behind and never catching up.

This is the same defect, one level down, as the hash bug recorded in the record that forgets on purpose: a structure indexed by the low bits of a product, where the low bits of a product depend only on the low bits of the operands. There the accident made a cache look better than it was; here it makes a tag look worse. Both are about which bits of a hash are already spoken for, and neither is visible in anything but a measurement of what the bits actually separate.

What a fingerprint is, stated once #

It is worth naming the quantity the last two plates are about, because it is the same quantity three structures here depend on and each calls it something else.

A tag is a fingerprint: a short hash of a key, stored so that a lookup can reject most non-matches without reading the key itself. Its whole specification is one number — the chance that a key which is not the one asked for has the same fingerprint — and that chance is $2^{-t}$ for $t$ bits if the fingerprint is independent of everything else used to find the key. A filter allowed to be wrong prices the same object as a filter’s false-positive rate; the bits given to the wrong keys prices what happens when a fingerprint table runs out of room.

The independence clause is the part that is never stated with it, and it is the part that fails here. The overlapping tag’s chance of a spurious match is not $2^{-8}$. Conditional on the two keys being in the same bucket it is 1, because being in the same bucket means having those bits equal. The measured 0.350 distinct tags a key is that conditioning, seen from the other side.

So a fingerprint’s width is not a property of the fingerprint. It is a property of the fingerprint given everything else the structure already knows about the key. That is a sentence about conditional entropy and it can be written as one, but the plate says it better: ten bits of the overlapping tag buy nothing, and every bit past ten buys the usual halving.

What the ordering costs, and where it pays #

An absent key’s tag falls uniformly among the bucket’s, so on average half of them are above it and a sorted scan should stop half way. The measurement approaches that from below — 28% at four entries, 38% at eight, 43% at sixteen — and the shortfall is granularity: in a bucket of four there are only five places to stop.

The insertion pays in shifts. Keeping eight bytes in order costs 3.55 byte moves per key inserted, and sixteen costs 5.17. That is paid once a key, against a saving paid once a lookup, so the exchange rate is the read-to-write ratio of the workload. A table built once and queried a million times takes the trade without thinking about it; a table churning at the rate it is read does not.

The stored-key side barely moves: 5.21 comparisons against 5.79, a saving of 10%. That asymmetry is the right way round for a hash table used as a membership test, where the absent keys are the common case and the whole point of the tag array is to answer them without touching an entry — and it is the wrong way round for a table used as a dictionary, where nearly every lookup hits. Two probes are two misses is the page that separated those two workloads for the probing rules, and the separation applies here unchanged. That is expected. A stored key’s tag matches, and a scan that matches stops on the match whether or not the bucket is sorted; the only saving is on the second bucket, which a stored key reaches one time in five.

What this does not buy #

Every number on this page is a comparison or an entry read, and the design was introduced to save cache lines. It saves none.

A bucket’s eight tag bytes are eight contiguous bytes. They are one line, or occasionally two, and the lookup reads the line whether it compares three tags in it or eight. Stopping early removes comparisons from inside a line that has already arrived, and a comparison inside an arrived line is one of the cheapest things a processor does — and on a machine with a vector instruction, all eight of them are one instruction and stopping early is not available at all.

So the honest claim is narrow. Ordering the tag is a saving in comparisons and not in misses, and the count is not the time is the page that says what the gap between those two is worth. Where it would pay is a bucket wide enough to span several lines — sixteen entries and two-byte tags, or thirty-two entries — because there a lookup that stops early stops before reading the second tag line. At that width the saving is 43% of the comparisons and the question becomes whether it is 43% of the lines, which needs the line accounting rather than the comparison counter.

There is a second reading of the same fact, and it is the more interesting one. The tag array was introduced because a lookup’s cost had stopped being about comparisons and become about which lines it touches — that was the whole argument of the page before this one, and it is why the tags live in an array of their own rather than beside the entries. Having moved the cost onto lines, a refinement that improves comparisons is a refinement aimed at the quantity that was deliberately abandoned.

That is not a criticism of the idea; it is a statement about where a design’s next improvement has to come from. Once a structure has been optimised onto one axis, further work on the axis it left behind is free of consequence. The ordered tag’s 38% is real, exact and, on the machine the previous page was arguing about, worth nothing. The way to make it worth something is to make the tags span more than one line, which means a wider bucket — and a wider bucket is what the bucket that fits a line had to abandon in the first place.

What the ordering does buy unconditionally is the insertion. An unordered bucket finds a free slot by scanning; a sorted one finds the insertion point by the same early stop, and the bucket that fits a line measured how much of a cuckoo table’s build cost is that scan. Nothing here separates that saving from the shift cost it pays for, and it is the one place where the trade might be positive on both sides.

Where the second bucket goes #

One number on the first plate has not been used and it decides how much any of this is worth. A lookup for an absent key reads both buckets, always — there is nowhere else the key could be — so it makes twice a bucket’s worth of comparisons. A lookup for a stored key reads the second bucket only 20% of the time, because the first one usually holds it.

That is why the absent case has twice the comparisons to save from and gets nearly four times the saving. It is also why the early stop is worth more than the arithmetic suggests: the stop happens independently in each bucket, so an absent lookup stops early twice.

A cuckoo table’s two buckets are the same structure that positions confined to one line found for a blocked filter, arriving from the other end of the collection, and the design tension is identical — a second place to look is a second chance to be balanced and a second thing to read. The difference is that a hash table’s second read is conditional on a definite answer and a filter’s is not, which is why a table can afford two buckets and the filter in that essay could not.

What is settled and what is not #

Settled, on a cuckoo table of 8,192 slots at 90% load with buckets of eight and 8-bit tags, counted exactly: keeping a bucket’s tags sorted lets an absent key’s lookup stop after 8.97 tag comparisons instead of 14.43, and a stored key’s after 5.21 instead of 5.79. It costs 3.55 tag-byte shifts per key inserted. The entries read are unchanged at 0.057 against 0.054.

Settled: the saving grows with the bucket — 28.4% at four entries, 37.8% at eight, 43.1% at sixteen — towards the half a sorted scan promises, and the insertion cost grows with it, 2.52 to 5.17 shifts.

Settled, and it is the finding: a tag cut from the bucket index’s own bits separates 0.350 of a bucket’s keys against a disjoint field’s 0.990, and causes 5.743 entry reads on an absent key against 0.057. Its useful width is its width minus the bucket index’s, which the plate shows directly — flat to ten bits, then falling on the same slope as the good cut.

Not settled:

Lines rather than comparisons. Nothing here re-counts the design in cache lines, and the saving is inside a line that has already been read. The case for the ordering rests on buckets wide enough for the tags to span more than one line, which is a width nothing here measures.

Vector comparison. Eight tag bytes against one broadcast byte is a single instruction on any machine that ships today, and an early stop cannot be expressed in it. Under that cost model the ordered tag’s saving is zero and its insertion cost is not, which would reverse the conclusion entirely.

Building the table. The insertion’s shifts are counted and the scan they replace is not, so the insertion side of the trade is measured on its cost and not on its saving.

Deletion and churn. A sorted bucket’s deletion must close the gap, which is another shift. Every table here is built once and queried; the read-to-write ratio at which the trade turns negative is therefore not measured, only named.

Still open: the tag as the bucket’s own index #

The ordering was introduced to let a lookup stop early, and it has a second consequence this page has not used. A sorted array of eight tags is not only stoppable — it is searchable, and a search in eight sorted bytes is three comparisons rather than four and a half.

That is a small saving and it points at a larger one. Once a bucket’s tags are sorted they are a small index over its entries, and an index answers questions a set cannot. A range of tags is a contiguous run, so “is any key in this bucket whose hash begins with these bits present” is one lookup rather than eight; and the position a tag is found at is a rank, which is the thing a compact structure needs to address an entry array without pointers.

The measurement that follows gives the entries no fixed slots at all. Instead of a parallel array indexed by slot, the entries of a bucket are packed contiguously and addressed by the rank of their tag — so a bucket of eight slots holding five keys stores five entries rather than eight, and the tag array becomes the only thing that knows where anything is. It asks what that saves at each load factor, what it costs on an insertion that must now shift entries as well as tags, and whether the saving survives the entry width, since shifting a 32-byte record is a different price from shifting a byte. The prediction is that it pays below about 70% load, where the slack a slotted table holds is most of its space, and loses above it — which would make it the opposite trade from every other one here, most of which pay only when the table is tight.