The bucket that fits a line

Two probes are two misses replayed three hash tables through a cache and found that the count the analysis uses and the count the machine charges rank them differently. Cuckoo hashing reads at most two slots per lookup, fewer entries than linear probing at every load it can reach, and misses the cache more often at every one of those loads — 1.18 times a lookup at a load of 0.45 against linear probing’s 0.98 — because its two slots are two unrelated addresses, while a run of adjacent slots in linear probing usually stays on one line.

That essay ended with a design it did not build. Keep cuckoo hashing’s two candidates, but make each candidate a bucket of several slots, and lay the buckets out so that each one occupies exactly one cache line. A lookup still goes to at most two places, and each place is now a whole line rather than a single slot. The prediction was specific: the table should miss about twice a lookup at every load, more than linear probing while linear probing’s runs are short and fewer once they cross lines, with the two curves crossing somewhere between loads of 0.8 and 0.9.

This page builds that table and measures it in the same cache. The first half of the prediction fails, and the reason it fails says something about the difference between the keys a table holds and the keys it is asked about.

A bucket instead of a slot #

The table on this page has the same 8,192 slots as the others, divided into buckets of $b$ slots: bucket $i$ is slots $i \cdot b$ to $i \cdot b + b - 1$. With $b = 8$ and cache lines of eight slots, every bucket is exactly one line; with $b = 4$, every line holds two buckets and no bucket crosses a line boundary. Each key has two candidate buckets, chosen by two independent hashes.

Lookup scans the first candidate bucket from its first slot and, if the key is not there, scans the second. Insertion puts the key in the first empty slot of either candidate; if both are full, it evicts a randomly chosen occupant of one, places the new key in that slot, and sends the evicted key to its other bucket, repeating until something lands in an empty slot or the attempt is abandoned. That is ordinary cuckoo insertion with a bucket where a slot used to be.

More hashes or wider buckets measured what this shape does to the construction threshold, which was the reason to consider it in the first place: plain cuckoo hashing with two single-slot candidates fails to build a little past half full, and buckets of four take the threshold beyond 0.95. The table on this page confirms that at this size. Buckets of two build up to a load of 0.85 and fail at 0.9; buckets of four and eight build at every load measured, up to 0.95.

The lookups are counted exactly as before. Every key the table holds is looked up once in a random order, every slot read is recorded as an address, and the addresses are replayed through a cache of 64 lines of 8 slots, least recently used. A probe is a slot read. A miss is a read that had to fetch its line.

Entries read go up #

In the analysis’s currency the bucketed tables are the worst on the plate at low loads, and the wider the bucket the worse. At a load of 0.3, buckets of eight read 2.19 entries per lookup, nearly twice linear probing’s 1.22 and nearly twice plain cuckoo hashing’s 1.17.

The reason is how a bucket fills. A key goes into the first empty slot of its bucket, so a bucket holding four keys holds them in its first four slots, and finding the fourth means reading all four. At a load of 0.3 a bucket of eight holds about 2.4 keys on average, and a successful lookup for a random one of them reads about half of them plus one — which is where the 2.19 comes from. The scan is linear probing inside a fixed box, and it pays linear probing’s count without linear probing’s runaway: however full the table, a lookup reads at most two boxes.

At the top of the range the ordering changes. At a load of 0.95 linear probing reads 8.32 entries and buckets of eight read 6.76, because linear probing’s runs have grown long enough to cross many buckets’ worth of slots while the bucketed scan never extends beyond sixteen. An analysis in probes would call buckets of eight a poor choice below about 0.9 and a modest improvement above it, with buckets of four somewhere in between.

Misses go down, at every load #

In the machine’s currency the bucketed tables are the best on the plate at every load measured. Buckets of eight miss 0.94 times per lookup at a load of 0.3 against linear probing’s 0.96, 1.01 at 0.75 against 1.12, and 1.21 at 0.95 against 1.79. Buckets of four sit between the two all the way up. The predicted low-load loss does not happen, and there is no crossing to find: the gap is small at low loads and grows steadily, but it never changes sign.

At the loads where plain cuckoo hashing can be built at all, the bucketed tables recover everything it gave up. At 0.45, plain cuckoo hashing misses 1.18 times per lookup, linear probing 0.98, and buckets of eight 0.93. The two-candidate idea was not what cost cuckoo hashing its locality; putting each candidate in a single slot was.

Why the prediction was wrong #

The prediction came from an honest piece of arithmetic that answered a different question. It reasoned that a bucketed lookup reads two lines, each line is a miss, so the table should miss about twice a lookup. That is exactly true of a lookup that reads both buckets. It is not true of a lookup that finds its key in the first.

How often a successful lookup reaches its second bucket can be counted directly. With buckets of eight, the share is 0.0% at a load of 0.3, 0.2% at 0.45, 2.4% at 0.6, 7.4% at 0.75, 14.2% at 0.85, 19.6% at 0.9 and 29.9% at 0.95. Insertion puts every key in its first candidate if there is room, and a bucket of eight is full only when the table is nearly full around it, so almost every key the table holds is in the first place a lookup goes. For plain cuckoo hashing, where a candidate is full as soon as it holds one key, the same share is already 17.4% at 0.3 and 26.6% at 0.45.

That gives a two-term account of every successful lookup’s misses. The first term is the chance that the first line is not already cached, which is the same for every table on the plate because every lookup starts at an unrelated address. The second is the chance of fetching a further line. For a bucketed table that is the second-bucket share. For linear probing it is the chance that the run crosses a line boundary before reaching the key, which for a lookup of $p$ probes is about $(p-1)/8$ — small, but never zero, because a run that starts on the last slot of a line crosses on its first step whatever the load.

At a load of 0.3, linear probing’s 1.22 probes give a crossing chance of about $0.22/8 \approx 0.03$, while buckets of eight reach their second bucket essentially never, and the plate’s difference is 0.02. At 0.95, buckets of eight miss about $0.92 + 0.30 = 1.22$ times per lookup, which is the 1.21 on the plate, while linear probing’s 8.32 probes cross about one line on average and its longer runs cross several. Both terms were available when the prediction was made. The error was taking the bucket’s worst lookup as its typical one.

The worst lookup #

Averages hide the property that made cuckoo hashing worth considering in the first place, so this plate draws the worst case instead. The quantity is the most distinct lines any one lookup touched, among all 7,782 lookups at a load of 0.95, and it bounds how many misses that lookup can take whatever the cache holds.

For linear probing it is the length of the longest run in lines. It is 4 at a load of 0.6, 11 at 0.75 and 54 at 0.95 — one key in that table sits more than four hundred slots from its home. For every cuckoo shape on the plate it is 2 at every load, and for the aligned buckets it cannot be anything else: a lookup reads within two buckets, each bucket lies within one line, and no key can make it read a third. The plate is drawn only if that holds for every bucket size that divides the line.

The probe nobody waits for is this collection’s account of why the worst lookup matters: a service answering many requests is judged by its slowest ones, and a request that touches fifty-four lines is a request that waits on fifty-four fetches. Plain cuckoo hashing offered a bound of two probes and paid for it in average misses and in a table that could not pass half full. The aligned bucket offers a bound of two lines, pays nothing in average misses, and builds to 0.95. It is the rare change that moves both the average and the tail in the same direction.

Keys the table does not hold #

Everything above is about keys the table holds, and the prediction’s arithmetic belongs to the other kind. A lookup for a key that is not there must rule out both candidates, so a bucketed table reads both buckets in full: sixteen entries for buckets of eight, two lines, and 1.87 misses at every load from 0.3 to 0.95. Plain cuckoo hashing reads two entries and misses the same 1.87 times, because the misses come from the two lines and not from how much of each is read. This is the “about twice a lookup” the prediction described, and it is flat, as predicted.

Linear probing on an absent key walks to the first empty slot, which is further than the walk to a present key and grows much faster with load. It misses 1.00 times at 0.3 and 1.26 at 0.6, fewer than the buckets’ 1.87; 1.77 at 0.75, still fewer; and 2.96 at 0.85, far more. The crossing the prediction expected between 0.8 and 0.9 is real, and it lies between 0.75 and 0.85 — for lookups that fail. At 0.95 a failed lookup in linear probing reads 108.5 entries and misses 13.1 times.

Which curve matters depends on what a table is asked. A cache in front of a slower store, a symbol table during compilation, or an index probed by a join whose keys mostly match all ask mainly about keys that are present. A table used to remove duplicates, to check membership before an expensive operation, or to probe with the larger side of a join where most keys have no partner asks mainly about keys that are absent, and below a load of about 0.8 linear probing serves those better. Chaining is the cheapest of all for absent keys at low loads, 1.24 misses at 0.3, because a short chain rules a key out after reading its head and at most one node.

A bucket wider than its line #

The bound of two lines is a statement about alignment, and halving the line size is the test that separates it from a statement about buckets. With lines of four slots, a bucket of four is still one line and keeps its bound: at most two lines per lookup, and 1.39 misses at a load of 0.95. A bucket of eight now spans two lines. Its scan crosses from one line to the next halfway through, so a lookup can touch four lines, and at 0.95 buckets of eight miss 2.00 times per lookup — worse than buckets of four, where on eight-slot lines they had been better.

The site’s check for this table includes the case as a claim that must fail: that buckets of eight on lines of four keep the two-line bound. It fails, on a lookup that touches four lines. A bucket that is merely small is not enough. It has to be no wider than the line it sits on, and it has to start where the line starts.

On a real machine that is a constraint on the entry as much as on the bucket. A cache line is typically 64 bytes, so eight slots of 8 bytes fit it exactly — a table of 64-bit keys, or of pointers. A table storing a 64-bit key beside a 64-bit value has slots of 16 bytes, fits four to a line, and should use buckets of four. The right bucket size is read off the entry size and the line size rather than chosen for its threshold.

What a table’s designer is choosing now #

Two probes are two misses closed with a choice between two families: linear probing, with the best locality and no bound, and cuckoo hashing, with a bound and poor locality. The aligned bucket removes most of that choice for keys the table holds. It has the better average, the bounded worst case, and the higher load, and what it gives up is visible on two plates only.

It reads more entries. At low loads a successful lookup in buckets of eight reads nearly twice as many slots as linear probing, and a failed one always reads sixteen. On these plates those reads are free, because they are all on lines already fetched. On a real machine they are not quite free — each is a comparison — but the comparisons are of adjacent entries in one line, which is precisely the shape a column computed in machine words exploited: several comparisons done at once as one operation on a word. A bucket of eight small tags can be checked in one step.

It pays full price for absent keys. A workload dominated by failed lookups at moderate loads is served better by linear probing, and one at high loads by neither — which is where a filter in front of the table earns its place.

And it inherits cuckoo hashing’s insertion. Evictions are rarer with buckets, since a key is displaced only when both of its candidates are full, but insertion is still a random walk that can fail near the threshold, and an insertion that can fail is the account of what that costs. Nothing on this page measures insertion.

What the measurement leaves out #

One level of cache and no prefetching. A prefetcher recognises a forward walk through adjacent memory and fetches ahead, which helps linear probing’s long runs and does nothing for a jump to an unrelated bucket. The high-load gap on these plates is therefore wider than a machine with a good prefetcher would show. A lookup that knows its two buckets in advance can also ask for both lines at once, which cuts the time a failed lookup waits without changing its misses.

Lookups in random order, and a cache far smaller than the table. With a cache of 1,024 lines, enough to hold the whole table, every table misses exactly as often as every other: 0.378, 0.377 and 0.377 per lookup at a load of 0.3 for linear probing and buckets of four and eight, and 0.132 each at 0.95. Each touches every line once, and the difference between the tables is a difference in how often a lookup lands on a line that is not cached. The cliff where the data stops fitting is the general form: rankings measured on one side of that boundary do not carry to the other.

Reads counted as equal. A slot read here costs one unit whether it is a key compared or a line fetched. The count is not the time is the reminder that the conversion from misses to time has its own constants, and on a machine where a miss costs a hundred comparisons, the plates’ entries-read panel is nearly irrelevant and the misses panel is nearly everything.

Keys that look random. Both hashes are multiplications keeping the high bits of the product, which spread these keys well. Choices that are not independent measured what happens to a two-choice scheme when its choices are correlated, and a bucketed table whose two hashes agree on a bucket more often than chance would reach its second candidate more often and lose some of its margin.

Still open: a line of tags in front of the entries #

The aligned bucket works because eight entries fit a line, and it stops working as entries grow. A table of 32-byte records fits two to a line, and a bucket of two builds only to about 0.85 on this table.

There is a standard way around that, and it is a second layout decision on top of the first. Store a line of small tags — one byte from each key’s hash — separately from the entries, eight or more to a line, and keep the full entries in a parallel array. A lookup reads the tag line for its bucket, compares all the tags at once, and reads a full entry only where a tag matches. A successful lookup then touches the tag line and one entry line: two misses, but independent of how wide an entry is. A failed lookup touches the tag lines and, unless a tag matches by chance, nothing else.

The measurement that follows puts that layout beside the inline buckets on this page as entries widen from one slot to four, and asks at what entry width the tag line pays for its extra fetch — and how often a one-byte tag matches by accident, since every false match is a wasted line.