More hashes or wider buckets

An insertion that can fail measured cuckoo hashing in its plainest form. Every key has two candidate slots, one in each of two tables. An arriving key takes whichever is free; if neither is, it evicts the occupant of one, which moves to its own other slot, possibly evicting another, and so on. A lookup examines exactly two slots whatever the keys are, which is a worst case rather than an expectation — and the price is that the construction can fail, with an eviction chain that never settles.

That essay found the failure had a threshold: below about half a key per slot it essentially never happened, and above it essentially always did. A table that is guaranteed to be at most half full is a table that wastes half its memory, and that is a real price for a worst-case lookup.

There are two obvious ways to lower it. Give each key more candidate buckets — a third hash function, or a fourth. Or keep two candidate buckets and let each bucket hold more than one key. Both have been analysed, both have published thresholds, and both are used. This page measures them side by side, because they buy the same thing in different currencies.

The shapes, stated #

A shape here is two numbers: the number of candidate buckets a key has, $d$, and the number of slots in each bucket, $b$. A key may live in any free slot of any of its $d$ buckets. The plain cuckoo table is $d = 2$, $b = 1$.

Every shape is filled the same way. A key goes into a free slot among its candidates if there is one; otherwise it evicts a randomly chosen occupant from a randomly chosen candidate bucket and the evicted key is reinserted by the same rule. If five hundred evictions pass without the chain settling, the construction is declared failed. The load is the number of keys divided by the total number of slots, $d$ is realised by that many independent hash functions over one table of 256 buckets, and every point on the plates is twenty independent constructions with fresh keys and fresh hash functions.

A lookup in a shape examines every slot of every candidate bucket: $d \times b$ slots in the worst case, and never more. That product is the price side of each shape, and it is a constant, which is the point — every shape on this page keeps the worst-case guarantee that justified cuckoo hashing in the first place.

Why there is a threshold at all #

The construction’s success is a question about a random graph, and seeing it that way explains why every plate below has a cliff rather than a slope.

Draw the buckets as vertices. For the plain table, each key is an edge between its two candidate buckets, drawn at random by the hash functions. Placing every key in a slot is choosing, for every edge, one of its two endpoints, with no vertex chosen more than once — and that is possible exactly when no connected piece of the graph has more edges than vertices. A tree has one fewer edge than vertices and fits easily; a piece with one cycle has exactly as many, and fits exactly; a piece with two cycles has too many, and fails.

A random graph with $n$ vertices and $cn$ edges changes character at a single value of $c$. Below one half, its pieces are almost all trees with an occasional single cycle; above one half, a giant piece forms, full of cycles, and it has far more edges than vertices. With two tables of $n$ slots each and $2n$ slots in all, a load of one half is exactly $c = 1/2$ — which is why the plain cuckoo table’s threshold is a half, and why it is sharp: it is the emergence of the giant component of a random graph, one of the most studied phase transitions in mathematics.

Every other shape changes the graph. Three hash functions make each key a hyperedge joining three buckets, and the question becomes whether a random hypergraph admits an orientation, whose threshold is about 0.918. Buckets of two slots make each vertex able to absorb two edges, and the question becomes whether every piece has at most twice as many edges as vertices. The thresholds differ because the graphs differ, and each is a cliff for the same reason the first one is.

A third hash function #

One more hash function moves the threshold from a little over a half to over nine tenths. That is not a small constant improvement on the same curve; the failure curve for three hashes is flat at zero all the way through the region where the two-hash table has already failed every time.

The published threshold for two hash functions is exactly one half, and the measured 0.57 is above it because these tables are small. A limit is not a prediction is this collection’s measurement of the same effect for linear probing: the threshold is a statement about tables whose size goes to infinity, and a table of 256 buckets sees the transition smeared over a range and shifted. The published threshold for three hash functions is about 0.918, and the measured 0.92 sits on it.

Why a third choice matters so much more here than it did for balancing loads is worth a sentence, because the second choice found that a third choice bought almost nothing. There the quantity was the maximum load, which a second choice had already reduced to a doubly logarithmic function, so a third had little left to improve. Here the quantity is whether every key can be given a slot at all — a matching problem — and a graph in which every key has three candidates is far more likely to have a matching than one in which every key has two. The same extra hash buys a different thing in a different problem.

Wider buckets instead #

Keeping two hash functions and widening the buckets moves the threshold almost as far. Two slots per bucket reach 0.89, against a published threshold of about 0.897; four slots reach past 0.95, against a published threshold of about 0.98, and the measurement stops before the transition.

On this plate the worst-case read grows faster than it did for more hash functions. Four slots in each of two buckets is eight slots examined, where three hash functions examined three. Counted in slots, wider buckets are the more expensive way to buy a high threshold.

Counted in anything a machine charges for, they are the cheaper way, and that is the argument the rest of the page is about.

All four shapes on one plate #

Side by side the shapes show one thing clearly and hide another. What they show is that the threshold behaviour survives every change: no shape turns the cliff into a slope, and in each the construction goes from never failing to always failing over a few hundredths of load. The threshold is the algorithm is the theme for results of this form, and here the threshold is not a tuning choice but a property of the random graph the hash functions draw — each key an edge or hyperedge between its candidate buckets, and the construction succeeding exactly when that graph admits an assignment of keys to slots.

What the plate hides is the cost of a lookup in anything other than slots. Three hash functions spread a key’s three candidates over three unrelated places in memory. Two buckets of four slots put its eight candidates in two places, and if a bucket is laid out as four adjacent entries, each place is one read of contiguous memory. Where an algorithm looks measures exactly this difference on cache lines: a read of adjacent entries costs one cache miss however many entries it covers, while reads in unrelated places cost one miss each.

So in the currency the analysis uses, slots examined, three hashes with one slot is cheapest at 0.92. In the currency a machine uses, places visited, two hashes with buckets of four is cheapest at 0.95 and above, with two places against three. Two probes are two misses measures that currency directly against linear probing, and finds that even the plain two-slot cuckoo lookup pays its two probes as two cache misses where linear probing’s longer runs pay about one.

Past nine tenths #

The returns from more hash functions diminish quickly. Two to three moved the threshold by more than a third of the table; three to four moves it by six hundredths; the published threshold for five is higher again by less than two hundredths. Each additional hash function costs one more place visited on every lookup, forever, to buy memory that was already more than nine tenths used.

That makes the choice among shapes a choice about where the last few per cent of memory are worth buying, and the answer depends on the size of an entry. If the table stores eight-byte keys, a table at 0.92 wastes eight per cent of its memory and moving to 0.98 saves six per cent at the cost of a fourth place per lookup. If the table stores fingerprints of a few bits — which is what a cuckoo filter does, and what the evidence a filter cannot remove measured — the same six per cent is a much larger share of the bits per key the filter exists to minimise, and the widely used design for such filters is two hashes and buckets of four.

Larger tables sharpen the cliff #

The larger tables check that the thresholds measured are the thresholds of the structure rather than artefacts of a small table. Quadrupling the table moved the plain two-hash table’s midpoint from 0.57 to 0.54 — towards the limit of one half — and left the other two shapes where they were, because their measured thresholds were already close to their limits.

The asymmetry has a reason. The plain table’s failure near its threshold is dominated by small, dense clusters of keys whose candidate slots overlap — a handful of keys with fewer slots between them than keys — and on a small table such clusters are relatively more likely to be absent by luck, which lets the construction survive a little past the limit. Shapes with more candidates per key make those clusters much rarer at the loads where they fail, so their thresholds are set by the global structure rather than by local accidents, and a small table measures them nearly as well as a large one.

That is also a warning about quoting a threshold from a small experiment: the shape whose threshold is lowest is the one whose small-table measurement is most flattering.

The memory each shape actually uses #

The thresholds are loads, and a load is a share of slots, so turning them into memory needs one more step that the plates leave implicit.

A table that must stay below its threshold with some margin reserves the rest of its slots empty. Taking the measured midpoints and leaving, say, five hundredths of margin, the plain two-hash table can be used to about a half, three hashes to about 0.87, buckets of two to about 0.84 and buckets of four to above 0.9. The plain table therefore needs about one and three quarters as many slots per key as the three-hash table, and about one and four fifths as many as the table with buckets of four.

That factor is the whole of the case for the richer shapes, and it scales with what a slot holds. A table of pointers pays eight bytes per wasted slot; a table of small fingerprints pays a few bits. So the same threshold difference is a large absolute saving for a table of large entries and a large relative saving for a table of small ones, and the second case is where the evidence a filter cannot remove found the fingerprint filter competing with a Bloom filter on bits per key — a competition a load of one half would lose outright.

The probe formula nobody checks is a reminder that this kind of arithmetic is where published numbers and running systems part company: a formula for a load is a formula for one table at one size, and the margin a system actually leaves is set by how often it is willing to rebuild.

What a threshold buys, restated #

Every shape on this page offers the same contract with a different number in it. A lookup reads a constant number of places, for every key, always. Construction succeeds with overwhelming probability below a load that depends on the shape, and fails with overwhelming probability above it. Between those two statements there is almost no room: a fraction of a per cent of load.

That makes the load a design constraint in a way it is not for linear probing, whose cost rises smoothly and never fails. A cuckoo table must be resized before it reaches its threshold, and the resize rule must leave margin for the finite-size smear this page measured, so the practical load of a plain two-hash table is some way below a half and that of a two-by-four table some way below 0.98.

What happens when a construction does fail is worth a sentence too, because it is the other half of the cost. A failed construction is repaired by choosing new hash functions and inserting every key again. Below the threshold that happens rarely enough that its expected cost, spread over the insertions, is a constant per key; near the threshold it happens so often that the rebuilds themselves dominate the cost of filling the table. What amortised means sets out when a rare expensive operation can honestly be charged to the cheap ones around it, and a cuckoo rebuild qualifies only so long as the load leaves room — which is one more reason the usable load of every shape is set by its threshold minus a margin rather than by the threshold itself. The probe nobody waits for measured a scheme whose cost is an average that degrades gracefully; the shapes here are schemes whose cost is a guarantee that holds until it does not.

What the measurement leaves out #

The eviction rule is a random walk with a fixed limit. A breadth-first search for a free slot finds shorter eviction chains and succeeds on some instances a random walk gives up on, so the measured thresholds are slightly conservative for small tables. The limiting thresholds are properties of the random graph and do not depend on the rule.

The keys are random and the hash functions independent. A hash is a family, not a function is the reminder that the thresholds are statements about hash families with enough independence, and that cuckoo hashing is known to need more independence than the weakest universal families provide.

No stash. A small overflow area holding a few keys whose insertion failed lets a construction succeed past the point where one or two keys cannot be placed, and it changes the failure probability below the threshold dramatically at a constant cost per lookup.

Where this ladder goes next: the stash that absorbs the last few keys #

The failure probability below the threshold is small but not zero, and for the plain table it is not as small as a practitioner would want: it falls only polynomially with the size of the table, so a large table rebuilt often will eventually fail at a load where the theory says it should not.

The published repair is a stash — a constant-size list, checked on every lookup, where a key goes when its eviction chain does not settle. A stash of a handful of slots turns that polynomial failure probability into a much faster-falling one, at the cost of a few extra comparisons on every lookup, which are sequential and cheap. The next rung measures it: failure rate against load for stash sizes zero to four, on tables large enough to see failures below the threshold at all, and the extra reads it costs. The prediction is that a stash of one or two changes the plain table from a structure that occasionally fails at a load of 0.45 into one that practically never does — and that it moves the threshold itself not at all.