Two probes are two misses

Every hash table is analysed in probes. Linear probing’s cost is the expected length of the run of occupied slots a lookup walks; chaining’s is the expected length of a chain; cuckoo hashing’s is at most two, which is its whole appeal. An insertion that can fail and more hashes or wider buckets measured what cuckoo hashing pays for that bound — a construction that fails past a threshold — and took the bound itself as the prize.

A probe is an entry read. On a real machine an entry read costs almost nothing when the entry is already in cache and a great deal when it is not, so the quantity a lookup’s time actually tracks is the number of cache misses it causes, and a probe count predicts that only if every probe is equally likely to miss. This page measures both counts for three tables holding the same keys, to find out whether they are.

Three tables and two counts #

The three tables are the standard ones, each holding keys at a stated load in a table of 8,192 slots.

• Linear probing. One array of slots. A key goes to its hash’s slot or, if that is taken, the next free slot after it. A lookup starts at the hash’s slot and walks forward until it finds the key.
• Chaining. An array of bucket heads, each pointing to a list of entries allocated separately. A lookup reads the head and follows pointers through the list.
• Cuckoo hashing. Two arrays, each key in one of two slots — one per array, chosen by two hashes. A lookup reads the first slot and, if the key is not there, the second.

Every key in each table is looked up once, and every entry read is recorded as an address, then replayed through a cache model: fully associative, 64 lines of 8 slots, least-recently-used. For a chained table the bucket heads occupy the table’s addresses and the list nodes occupy addresses after it, in allocation order. Two numbers are reported per lookup: entries read, which is the probe count, and misses, which is the count of reads that had to fetch a line.

Entries read: cuckoo wins, as advertised #

In the analysis’s currency the ranking is clear. Cuckoo hashing reads the fewest entries at every load where it exists — 1.27 at 0.45, against linear probing’s 1.39 — because at low loads most of its keys are found in the first slot and the rest in the second, and nothing ever makes it read a third. Linear probing is close at low loads and runs away as the table fills. Chaining pays a nearly constant two, since every lookup reads a head and at least one node.

This is the plate that justifies cuckoo hashing, and it is correct.

It is also worth noticing how small the differences on it are at the loads where all three tables run. Between loads of 0.1 and 0.45, linear probing and cuckoo hashing are within ten per cent of each other throughout. An analysis in probes would say that below half full the choice between them is a matter of taste. The next plate says otherwise, and the way it says so is the argument of the page.

Misses: cuckoo loses #

In the machine’s currency the first two places swap. At a load of 0.45 — the highest this cuckoo table reaches — cuckoo hashing misses 1.18 times per lookup and linear probing 0.98. At every load both can run, cuckoo misses more, and the gap grows with load: 4% more at 0.1, 20% more at 0.45.

The mechanism is the one in the title. A cuckoo lookup that has to read its second slot reads a slot chosen by an independent hash in a different array, and that slot is on a different cache line from the first with near certainty. So every second probe is a second miss. As the load rises, more keys live in their second slot, more lookups make the second probe, and the misses climb towards two probes’ worth.

A linear-probing lookup that walks past its first slot reads the next slot. With eight slots to a cache line, the next slot is on the same line seven times in eight, so a run of two or three probes is usually one miss. Linear probing’s extra probes are nearly free; cuckoo hashing’s are full price.

The arithmetic can be done without the simulation, and doing it confirms the plate rather than replacing it. Suppose a lookup starts at a random slot and the slot’s line is not in cache — the typical case for a table much larger than its cache, since each lookup lands somewhere unrelated to the last. Every lookup then pays one miss for its first probe. A linear-probing lookup that makes $p$ probes crosses into a new line with probability about $(p-1)/8$, since each step forward leaves the line one time in eight. At a load of 0.45 with 1.39 probes, that is about $1 + 0.39/8 \approx 1.05$ misses. A cuckoo lookup pays one miss for its first probe and, whenever it needs its second, another; at 0.45 with 1.27 probes that is about $1 + 0.27 = 1.27$ misses.

The simulation reports 0.98 and 1.18, somewhat lower than both estimates because some first probes land on a line an earlier lookup left in the cache. The difference the arithmetic predicts — about 0.22 — is the difference the simulation measures, 0.20. So the whole effect is the second term: linear probing divides its extra probes by the number of slots on a line, and cuckoo hashing does not.

Chaining is worst in both currencies and for the same reason in both: a list node is a separate allocation, reached by a pointer, and a pointer can point anywhere. Every node on a chain is a miss unless it happens to share a line with the head, and it almost never does.

Chaining’s numbers at low load make the point most sharply. At a load of 0.1 almost every chain holds one entry, so a successful lookup reads the head and one node — 2.05 entries — and misses 1.88 times. The head and the node are two separate places in memory whatever the chain’s length, so chaining starts at nearly two misses a lookup when its analysis says it is doing almost nothing, and its misses barely move as the load rises because the second miss was never about length. Its probe count looks like a structure that is nearly free at low load; its miss count looks like a structure with a fixed toll of one pointer chase per lookup, which is what it is.

The two counts side by side #

Side by side the two panels make the inversion obvious. The ordering on the left is the one in every textbook; the ordering on the right is the one a profiler reports. Two counts disagree is this collection’s theme for exactly this, and where an algorithm looks is its general form: an access pattern is priced by its locality, and a count of accesses assigns every pattern the same price.

It is worth noticing what the right-hand panel does to linear probing’s reputation as well. Its probe count at a load of 0.9 is 5.20, the familiar runaway that makes the method sound fragile at high load. Its miss count at 0.9 is 1.43. The runaway is a runaway in entries read, most of which are on lines the lookup has already fetched, and in misses it is mild. The probe formula nobody checks measured how closely the formula tracks a real table; this plate measures how little the formula’s quantity tracks what the table costs on a machine with a cache.

Smaller lines #

The account predicts that linear probing’s advantage depends on how many slots share a line, and halving the line size tests that. With four slots to a line, a run of probes crosses into a new line twice as often, so linear probing’s misses rise — most visibly at high load, where the runs are long, 1.43 becoming 1.99 at 0.9. Cuckoo hashing’s misses barely move, because its two probes were already on different lines and making lines smaller cannot separate them further.

At a load of 0.45 the gap between the two narrows from 0.20 misses to 0.17. It does not close: even with four slots to a line, most short runs stay within one. Real cache lines hold more entries than four for any table of pointers or small integers, so the eight-slot plate is closer to the ordinary case.

A cache that holds the whole table #

With a cache large enough to hold the whole table, the picture changes character. For linear probing and cuckoo hashing every miss is now a first touch of a line, and every line is fetched at most once in the whole run of lookups. A fuller table means more lookups sharing the same lines, so the misses per lookup fall as the load rises — linear probing to 0.14 at 0.9. The two tables are nearly equal at 0.45, 0.27 each, since each touches every line of the table once and the number of lookups is the same.

Chaining alone gets worse, and the reason is the one the design of chaining cannot escape. Its nodes are allocated outside the table, one per key, so the number of lines they occupy grows with the number of keys, and the cache that holds the table does not hold them. At a load of 0.9 chaining misses 1.64 times per lookup where linear probing misses 0.14 — more than eleven times as often, in a regime where the cache is supposedly large enough. A bucket that becomes a tree measured a library that converts long chains to trees to bound their length; that bounds the probes and leaves every node a pointer away.

This last plate is also a reminder about where a measurement’s regime comes from. On a cache of 64 lines, every table misses about once per lookup at least, because lookups land on lines the cache does not hold. On a cache that holds the table, most lookups miss not at all, and the question becomes whether a table’s entries live inside the region the cache holds. The cliff where the data stops fitting measures the step between those two regimes for arrays; a hash table has the same step, and the ranking of tables on one side of it is not the ranking on the other. The count is not the time is the general form of the warning, and a probe count is a particularly clean instance of a count whose relation to time changes sign across a cache boundary.

What a table’s designer is choosing #

Put together, the plates say what each table is good at in a machine’s terms rather than an analysis’s.

Linear probing has the best locality of the three by a wide margin, because its probes are adjacent. Its weakness in probes at high load is mostly hidden by that locality, and it becomes a real weakness only when lines are small or the load is very high. It gives no worst-case bound: a long run is possible, and an adversary who can choose keys can make one.

Cuckoo hashing has a worst-case bound of two probes, which is a genuine guarantee against adversarial and unlucky keys, and it pays for the guarantee in misses on the common case as well as in a construction threshold. The bound matters most where a tail matters — the probe nobody waits for is this collection’s account of why a table’s worst lookup can matter more than its average — and least in a table serving many lookups whose average sets throughput.

Chaining has the worst locality in every regime, and its advantage — it never fills, and deletion is simple — is paid for in a pointer chase per lookup that no load factor removes.

That summary also says which variant of cuckoo hashing recovers the locality. If each of a key’s two candidate places is a bucket of several slots laid out on one cache line, a lookup reads up to eight slots in two lines — two misses, as before — but the table holds far more keys before its threshold. More hashes or wider buckets measured that shape’s threshold beyond 0.95; its misses per lookup should be about the plain cuckoo table’s two probes’ worth at every load, which is higher than linear probing’s but no longer rises with load, and the construction no longer fails at a half.

What the measurement leaves out #

One level of cache and no prefetching. A hardware prefetcher recognises a lookup that walks forward through adjacent slots and fetches ahead, which helps linear probing further; it cannot predict an independent hash, which helps cuckoo hashing not at all. So the gap on these plates is if anything conservative.

Successful lookups only. An unsuccessful lookup in linear probing walks to the end of a run, which is longer than the walk to a present key, and in cuckoo hashing always reads both slots. Both change the counts in cuckoo hashing’s favour by a little and change the misses in linear probing’s favour by less, since the extra probes are adjacent.

Allocation order for chains. The chained table’s nodes are allocated in insertion order, which scatters a bucket’s nodes as widely as any allocator would. An allocator that places nodes near their bucket, or a chained table that stores its first entry in the bucket itself, would move chaining’s misses towards linear probing’s — which is what open-addressing tables already are.

The keys are random. A table’s probes are a property of its keys and its hash, and the relative ordering here is for keys a good hash has made look random.

Lookups in arbitrary order. Every key is looked up once, in insertion order, which for a hashed table is a random order over the slots. A workload that looks up the same few keys repeatedly keeps their lines in cache and makes every table cheap; a workload that looks up keys in an order correlated with their slots — a scan, or a join over sorted keys — rewards linear probing’s locality even more. The plates are for the case with no correlation, which is the case where the tables differ least in their favour and most in their structure.

Where this ladder goes next: a bucket the size of a cache line #

The last section predicted a table from two measurements and did not build it. A cuckoo table whose candidates are buckets of four or eight slots, each bucket aligned to one cache line, should read at most two lines per lookup at any load up to its threshold — which for buckets of four is above 0.95 — and should therefore miss at most twice, with no runaway at high load and no failure at a half.

The measurement is the one on this page with a fourth table added, at line sizes of four and eight, across the same loads. The prediction is that it misses more than linear probing at low loads, where linear probing’s runs are one line, and fewer at high loads, where linear probing’s runs cross lines — and that the crossing falls somewhere between 0.8 and 0.9. If it does, the table with the worst locality on this page becomes, with one change to what a slot is, the table with the best worst case and competitive locality, and the choice between the two families stops being a choice between a guarantee and a cache.