Optimizing Open Addressing – Max Slater – Laptop Graphics, Programming, and Math

Your default hash desk needs to be open-addressed, utilizing Robin Hood linear probing with backward-shift deletion.
When prioritizing deterministic efficiency over reminiscence effectivity, two-way chaining can be a sensible choice.

Code for this text could also be discovered on GitHub.

Most individuals first encounter hash tables applied utilizing separate chaining, a mannequin easy to grasp and analyze mathematically.
In separate chaining, a hash operate is used to map every key to considered one of (Okay) buckets.
Every bucket holds a linked record, so to retrieve a key, one merely traverses its corresponding bucket.

Given a hash operate drawn from a universal family, inserting (N) keys right into a desk with (Okay) buckets ends in an anticipated bucket measurement of (frac{N}{Okay}), a amount also called the desk’s load issue.
Assuming (fairly) that (frac{N}{Okay}) is bounded by a relentless, all operations on such a desk will be carried out in anticipated fixed time.

Sadly, this primary evaluation doesn’t think about the myriad components that go into implementing an environment friendly hash desk on an actual pc.
In follow, hash tables primarily based on open addressing can present superior efficiency, and their limitations will be labored round in almost all instances.

Open Addressing

In an open-addressed desk, every bucket solely incorporates a single key.
Collisions are dealt with by inserting extra keys elsewhere within the desk.
For instance, in linear probing, a secret is positioned within the first open bucket ranging from the index it hashes to.

Not like in separate chaining, open-addressed tables could also be represented in reminiscence as a single flat array.
A priori, we should always count on operations on flat arrays to supply larger efficiency than these on linked buildings on account of extra coherent reminiscence accesses.

Nonetheless, if the person needs to insert greater than (Okay) keys into an open-addressed desk with (Okay) buckets, the whole desk have to be resized.
Sometimes, a bigger array is allotted and all present keys are moved to the brand new desk.
The scale is grown by a relentless issue (e.g. 2x), so insertions happen in amortized fixed time.

Why Not Separate Chaining?

In follow, the usual libraries of many languages present individually chained hash tables, similar to C++’s std::unordered_map.
No less than in C++, this alternative is now thought-about to have been a mistake—it violates C++’s precept of not paying for options you didn’t ask for.

Separate chaining nonetheless has some purported advantages, however they appear unconvincing:

• Individually chained tables don’t require any linear-time operations.

  First, this isn’t true.
  To keep up a relentless load issue, separate chaining hash tables additionally must resize as soon as a adequate variety of keys are inserted, although the restrict will be larger than (Okay).
  Most individually chained tables, together with std::unordered_map, solely present amortized fixed time insertion.

  Second, open-addressed tables will be incrementally resized.
  When the desk grows, there’s no cause we’ve to maneuver all current keys immediately.
  As an alternative, each subsequent operation can transfer a set variety of outdated keys into the brand new desk.
  Finally, all keys could have been moved and the outdated desk could also be deallocated.
  This method incurs overhead on each operation throughout a resize, however none would require linear time.

• When every (key + worth) entry is allotted individually, entries can have steady addresses. Exterior code can safely retailer tips that could them, and enormous entries by no means must be copied.

  This property is straightforward to help by including a single degree of indirection. That’s, allocate every entry individually, however use an open-addressed desk to map
  keys to pointers-to-entries. On this case, resizing the desk solely requires copying pointers, reasonably than total entries.

• Decrease reminiscence overhead.

  It’s potential for a individually chained desk to retailer the identical knowledge in much less house than an open-addressed equal, since flat tables essentially waste house storing empty buckets.
  Nonetheless, matching high-quality open addressing schemes (particularly when storing entries not directly) requires a load issue larger than one, degrading question efficiency.
  Additional, individually allocating nodes wastes reminiscence on account of heap allocator overhead and fragmentation.

The truth is, the one state of affairs the place open addressing really doesn’t work is when the desk can not allocate and entries can’t be moved.
These necessities can come up when utilizing intrusive linked lists, a typical sample in kernel knowledge buildings and embedded techniques with no heap.

For simplicity, allow us to solely think about tables mapping 64-bit integer keys to 64-bit integer values.
Outcomes won’t take into consideration the results of bigger values or non-trivial key comparability, however ought to nonetheless be consultant, as keys can typically be represented in 64 bits and values are sometimes pointers.

We’ll consider tables utilizing the next metrics:

• Time to insert (N) keys into an empty desk.
• Time to erase (N) current keys.
• Time to lookup (N) current keys.
• Time to lookup (N) lacking keys^.
• Common probe size for current & lacking keys.
• Most probe size for current & lacking keys.
• Reminiscence amplification in a full desk (complete measurement / measurement of knowledge).

Every open-addressed desk was benchmarked at 50%, 75%, and 90% load components.
Each take a look at focused a desk capability of 8M entries, setting (N = lfloor 8388608 * textual content{Load Issue} rfloor – 1).
Fixing the desk capability permits us to benchmark conduct at precisely the desired load issue, avoiding deceptive outcomes from tables which have not too long ago grown.
The big variety of keys causes every take a look at to unpredictably traverse an information set a lot bigger than L3 cache (128MB+), so the CPU ^{can not successfully cache or prefetch reminiscence accesses.}

Desk Sizes

All benchmarked tables use completely power-of-two sizes.
This invariant permits us to translate hashes to array indices with a quick bitwise AND operation, since:

h % 2**n == h & (2**n - 1)

Energy-of-two sizes additionally admit a neat digital reminiscence trick^{, however that optimization isn’t included right here.}

Nonetheless, power-of-two sizes could cause pathological conduct when paired with some hash features, since indexing merely throws away the hash’s excessive bits.
Another technique is to make use of prime sized tables, that are considerably extra sturdy to the selection of hash operate.
For the needs of this publish, we’ve a set hash operate, so prime sizes weren’t used^.

Hash Operate

All benchmarked tables use the squirrel3 hash operate, a quick integer hash that (so far as I can inform) solely exists in this GDC talk on noise-based RNG.

Right here, it’s tailored to 64-bit integers by selecting three massive 64-bit primes:

uint64_t squirrel3(uint64_t at) {
    constexpr uint64_t BIT_NOISE1 = 0x9E3779B185EBCA87ULL;
    constexpr uint64_t BIT_NOISE2 = 0xC2B2AE3D27D4EB4FULL;
    constexpr uint64_t BIT_NOISE3 = 0x27D4EB2F165667C5ULL;
    at *= BIT_NOISE1;
    at ^= (at >> 8);
    at += BIT_NOISE2;
    at ^= (at << 8);
    at *= BIT_NOISE3;
    at ^= (at >> 8);
    return at;
}

I make no claims concerning the standard or robustness of this hash operate, however observe that it’s low-cost, it produces the anticipated variety of collisions in power-of-two tables, and it passes smhasher when utilized bytewise.

Different Benchmarks

A number of much less fascinating benchmarks have been additionally run, all of which exhibited similar efficiency throughout equal-memory open-addressed tables and a lot worse efficiency for separate chaining.

• Time to lookup every aspect by following a Sattolo cycle ^(2-4x).
• Time to clear the desk (100-200x).
• Time to iterate all values (3-10x).

Separate Chaining

To get our bearings, let’s first implement a easy separate chaining desk and benchmark it at varied load components.

These are respectable outcomes, particularly lookups at 100%: the CPU is ready to disguise a lot of the reminiscence latency.
Insertions and erasures, however, are fairly sluggish—they contain allocation.

Technically, the reported reminiscence amplification in an underestimate, because it doesn’t embrace heap allocator overhead.
Nonetheless, we should always not instantly examine reminiscence amplification towards the approaching open-addressed tables, as storing bigger values would enhance separate chaining’s ratio.

std::unordered_map

Operating these benchmarks on std::unordered_map<uint64_t,uint64_t> produces outcomes roughly equal to the 100% column, simply with marginally slower insertions and quicker clears.
Utilizing squirrel3 with std::unordered_map moreover makes insertions barely slower and lookups barely quicker.
Additional comparisons shall be relative to those outcomes, since actual efficiency numbers for std::unordered_map rely on one’s customary library distribution (right here, Microsoft’s).

Linear Probing

Subsequent, let’s implement the only sort of open addressing—linear probing.

Within the following diagrams, assume that every letter hashes to its alphabetical index. The cranium denotes a tombstone.

• Insert: ranging from the important thing’s index, place the important thing within the first empty or tombstone bucket.

  

• Lookup: ranging from the important thing’s index, probe buckets so as till discovering the important thing, reaching an empty non-tombstone bucket, or exhausting the desk.

  

• Erase: lookup the important thing and exchange it with a tombstone.

  

The outcomes are surprisingly good, contemplating the simplicity:

For current keys, we’re already beating the individually chained tables, and with decrease reminiscence overhead!
In fact, there are additionally some apparent issues—searching for lacking keys takes for much longer, and the worst-case probe lengths are fairly scary, even at 50% load issue.
However, we will do significantly better.

Erase: Rehashing

One easy optimization is mechanically recreating the desk as soon as it accumulates too many tombstones.
Erase now happens in amortized fixed time, however we already tolerate that for insertion, so it shouldn’t be an enormous deal.
Let’s implement a desk that re-creates itself after erase has been referred to as (frac{N}{2}) occasions.

In comparison with naive linear probing:

Clearing the tombstones dramatically improves lacking key queries, however they’re nonetheless fairly sluggish.
It additionally makes erase slower at 50% load—there aren’t sufficient tombstones to make up for having to recreate the desk.
Rehashing additionally does nothing to mitigate lengthy probe sequences for current keys.

Erase: Backward Shift

Truly, who says we’d like tombstones? There’s a little-taught, however quite simple algorithm for erasing keys that doesn’t degrade efficiency or must recreate the desk.

Once we erase a key, we don’t know whether or not the lookup algorithm is counting on our bucket being stuffed to search out keys later within the desk.
Tombstones are one method to keep away from this downside.
As an alternative, nonetheless, we will assure that traversal is rarely disrupted by merely eradicating and reinserting all following keys, as much as the following empty bucket.

Observe that regardless of the title, we aren’t merely shifting the next keys backward. Any keys which might be already at their optimum index won’t be moved.
For instance:

After implementing backward-shift deletion, we will examine it to linear probing with rehashing:

Naturally, erasures develop into considerably slower, however queries on lacking keys now have affordable conduct, particularly at 50% load.
The truth is, at 50% load, this desk already beats the efficiency of equal-memory separate chaining in all 4 metrics.
However, we will nonetheless do higher: a 50% load issue is unimpressive, and max probe lengths are nonetheless very excessive in comparison with separate chaining.

You might need seen that neither of those upgrades improved common probe size for current keys.
That’s as a result of it’s not potential for linear probing to have another common!
Take into consideration why that’s—it’ll be fascinating later.

Quadratic Probing

Quadratic probing is a typical improve to linear probing meant to lower common and most probe lengths.

Within the linear case, a probe of size (n) merely queries the bucket at index (h(okay) + n).
Quadratic probing as an alternative queries the bucket at index (h(okay) + n^2).
Every desk operation have to be up to date to make use of this new probe sequence, however the logic is in any other case nearly similar.

There are additionally a pair refined caveats to quadratic probing:

• A quadratic probe sequence won’t essentially contact each bucket within the desk, so insertions can fail regardless of there being an empty bucket. On this case, the desk should develop and the insertion is retried.
• There really is a true deletion algorithm for quadratic probing, nevertheless it’s a bit extra concerned than the linear case and therefore not reproduced right here. We’ll once more use tombstones and rehashing.

After implementing our quadratic desk, we will examine it to linear probing with rehashing:

As anticipated, quadratic probing dramatically reduces each the typical and worst case probe lengths, particularly at excessive load components.
These good points usually are not fairly as spectacular when in comparison with the linear desk with backshift deletion, however are nonetheless very important.

Lowering the typical probe size improves the typical efficiency of all queries.
Right here, nonetheless, question efficiency has regressed barely, as quadratic probing itself requires extra computation and accesses reminiscence much less predictably.
That’s not essentially a deal breaker—efficiency is decrease variance—nevertheless it’s not splendid.

Double Hashing

Double hashing purports to offer even higher conduct than quadratic probing.
As an alternative of utilizing the identical probe sequence for each key, double hashing determines the probe stride by hashing the important thing a second time.
That’s, a probe of size (n) queries the bucket at index (h_1(okay) + n*h_2(okay))

• If (h_2) is at all times co-prime to the desk measurement, insertions at all times succeed, because the probe sequence will contact each bucket. Which may sound tough to guarantee, however since our desk sizes are at all times an influence of two, we will merely make (h_2) at all times return an odd quantity.
• Sadly, there isn’t any true deletion algorithm for double hashing. We’ll once more use tombstones and rehashing.

Let’s implement a desk with a barely modified squirrel3 because the second hash.
The outcomes, in comparison with quadratic probing with rehashing:

Double hashing succeeds in additional lowering common probe lengths, however max lengths are extra of a blended bag.
Sadly, the extra overhead of hashing each key twice makes most queries considerably slower, so double hashing doesn’t appear value it.

Robin Hood Linear Probing

To this point, quadratic probing and double hashing have offered low probe lengths, however their uncooked question efficiency lags linear probing with backward shift deletion—a minimum of at low load components.
Enter Robin Hood linear probing.
This technique drastically reins in most probe lengths whereas sustaining excessive question efficiency.

The important thing distinction is that when inserting a key, we’re allowed to steal the place of an current key whether it is nearer to its splendid index (“richer”) than the brand new secret is.
When this happens, we merely swap the outdated and new keys and keep on inserting the outdated key in the identical method. This ends in a extra equitable distribution of probe lengths.

This insertion methodology seems to be so efficient that we will totally ignore rehashing so long as we preserve observe of the utmost probe size.
Lookups will merely probe till both discovering the important thing or exhausting the utmost probe size.

Implementing this desk, in comparison with linear probing with backshift deletion:

Most probe lengths enhance dramatically, undercutting even quadratic probing and double hashing.
This solves the primary downside with open addressing.

Nonetheless, efficiency good points are much less clear-cut:

• Insertion efficiency suffers throughout the board.
• Present lookups are barely quicker at low load, however a lot slower at 90%.
• Lacking lookups are maximally pessimistic.

Fortuitously, we’ve received yet another trick up our sleeves.

Erase: Backward Shift

When erasing a key, we will run a really comparable backshift deletion algorithm.
There are simply two variations:

• We are able to cease upon discovering a key that’s already in its optimum location. No additional keys might have been pushed previous it—they might have stolen this spot throughout insertion.
• We don’t must re-hash—since we cease on the first optimum key, all keys earlier than it may well merely be shifted backward.

See Also

NASA’s OSIRIS-REx asteroid pattern return to Earth: Dwell updates

With backshift deletion, we now not have to preserve observe of the utmost probe size.

Implementing this desk, in comparison with naive robin hood probing:

We once more regress the efficiency of erase, however we lastly obtain affordable missing-key conduct.
Given the superb most probe lengths and total question efficiency, Robin Hood probing with backshift deletion needs to be your default alternative of hash desk.

You may discover that at 90% load, lookups are considerably slower than primary linear probing.
This hole really isn’t regarding, and explaining why is an fascinating train^.

Two-Manner Chaining

So, you’re nonetheless not happy with a most noticed probe size of 12—you need to provably by no means iterate greater than a relentless variety of buckets.
One other class of hash tables primarily based on Cuckoo hashing can present this assure.
Right here, we are going to look at a very sensible formulation generally known as Two-Manner Chaining.

Our desk will nonetheless encompass a flat array of buckets, however every bucket will be capable to maintain a small handful of keys.
When inserting a component, we are going to hash the important thing with two totally different features, inserting it into whichever corresponding bucket has extra space.
If each buckets occur to be stuffed, the whole desk will develop and the insertion is retried.

You may suppose that is loopy—in separate chaining, the anticipated most probe size scales with (O(frac{lg N}{lg lg N})), so wouldn’t this waste copious quantities of reminiscence rising the desk?
It seems including a second hash operate reduces the anticipated most to (O(lglg N)), for causes explored elsewhere.
That makes it sensible to cap the utmost bucket measurement at a comparatively small quantity.

Let’s implement a flat two-way chained desk. We are able to measure the way it performs with varied bucket capacities:

Since each key will be present in considered one of two potential buckets, question occasions develop into primarily deterministic.
Lookup occasions are particularly spectacular, solely barely lagging the Robin Hood desk and having no penalty on lacking keys.
The common probe lengths point out that the majority buckets are roughly half full, and the max probe lengths are strictly bounded by two occasions the bucket measurement.
Reminiscence effectivity does undergo at small bucket capacities (and therefore insertion is slower on common on account of rising the desk), however remains to be affordable for reminiscence unconstrained use instances.

General, two-way chaining is one other good selection of hash desk, a minimum of when reminiscence effectivity isn’t the very best precedence.
Within the subsequent part, we’ll additionally see how lookups may even additional accelerated with prefetching and SIMD operations.

Keep in mind that deterministic queries won’t matter should you haven’t already applied incremental desk development.

Cuckoo Hashing

Cuckoo hashing includes storing keys in two separate tables, every of which holds one key per bucket.
This scheme will assure that each secret is saved in its splendid bucket in one of many two tables.

Every secret is hashed with two totally different features and inserted utilizing the next process:

1. If a minimum of one desk’s bucket is empty, the secret is inserted there.
2. In any other case, the secret is inserted anyway, evicting one of many current keys.
3. The evicted secret is transferred to the alternative desk at its different potential place.
4. If doing so evicts one other current key, go to three.

If the loop finally ends up evicting the important thing we’re making an attempt to insert, we all know it has discovered a cycle and therefore should develop the desk.

As a result of Cuckoo hashing doesn’t strictly certain the insertion sequence size, I didn’t benchmark it right here, nevertheless it’s nonetheless an fascinating choice.

To this point, the lookup benchmark has been applied roughly like this:

for(uint64_t i = 0; i < N; i++) {
  assert(desk.discover(keys[i]) == values[i]);
}

Naively, this loop runs one lookup at a time.
Nonetheless, you might need seen that we’ve been capable of finding keys quicker than the CPU can load knowledge from predominant reminiscence—so one thing extra advanced have to be occurring.

In actuality, fashionable out-of-order CPUs can execute a number of iterations in parallel.
Expressing the loop as a dataflow graph lets us construct a simplified psychological mannequin of the way it really runs: the CPU is ready to execute a computation at any time when its dependencies can be found.

Right here, inexperienced nodes are resolved, in-flight nodes are yellow, and white nodes haven’t begun:

On this instance, we will see that every iteration’s root node (i++) solely requires the worth of i from the earlier step—not the results of discover.
Subsequently, the CPU can run a number of discover nodes in parallel, hiding the truth that each takes ~100ns to fetch knowledge from predominant reminiscence.

Unrolling

There’s a typical optimization technique generally known as loop unrolling.
Unrolling includes explicitly writing out the code for a number of semantic iterations inside every precise iteration of a loop.
When every interior pseudo-iteration is impartial, unrolling explicitly severs them from the loop iterator dependency chain.

Most fashionable x86 CPUs can preserve observe of ~10 simultaneous pending masses, so let’s strive manually unrolling our benchmark 10 occasions.
The brand new code appears like the next, the place index_of hashes the important thing however doesn’t do the precise lookup.

uint64_t indices[10];
for(uint64_t i = 0; i < N; i += 10) {
  for(uint64_t j = 0; j < 10; j++) {
    indices[j] = desk.index_of(keys[i + j]);
  }
  for(uint64_t j = 0; j < 10; j++) {
    assert(desk.find_index(indices[j]) == values[i + j]);
  }
}

This isn’t true unrolling, because the interior loops introduce dependencies on j.
Nonetheless, it doesn’t matter in follow, as computing j is rarely a bottleneck.
The truth is, our compiler can mechanically unroll the interior loop for us (clang particularly does this).

Specific unrolling has principally no impact, because the CPU was already capable of saturate its pending load buffer.
Nonetheless, handbook unrolling now lets us introduce software program prefetching.

Software program Prefetching

When traversing reminiscence in a predictable sample, the CPU is ready to preemptively load knowledge for future accesses.
This functionality, generally known as {hardware} prefetching, is the rationale our flat tables are so quick to iterate.
Nonetheless, hash desk lookups are inherently unpredictable: the deal with to load is decided by a hash operate.
Which means {hardware} prefetching can not assist us.

As an alternative, we will explicitly ask the CPU to prefetch deal with(es) we are going to load from within the close to future.
Doing so can’t velocity up a person lookup—we’d instantly look ahead to the consequence—however software program prefetching can speed up batches of queries.
Given a number of keys, we will compute the place every question will entry the desk, inform the CPU to prefetch these places, and then begin really accessing the desk.

To take action, let’s make desk.index_of prefetch the situation(s) examined by desk.find_indexed:

• In open-addressed tables, we prefetch the slot the important thing hashes to.
• In two-way chaining, we prefetch each buckets the important thing hashes to.

Importantly, prefetching requests the whole cache line for the given deal with, i.e. the aligned 64-byte chunk of reminiscence containing that deal with.
Which means surrounding knowledge (e.g. the next keys) might also be loaded into cache.

Prefetching makes an enormous distinction!

• Separate chaining advantages from prefetching the unpredictable preliminary load^.
• Linear tables with a low common probe size drastically profit from prefetching.
• Quadratic and double-hashed probe sequences shortly depart the cache line (and require extra computation), making prefetching a bit much less efficient.
• In two-way chaining, keys can at all times be present in a prefetched cache line—however every lookup requires fetching two places, consuming additional load buffer slots.

SIMD

Trendy CPUs present SIMD (single instruction, a number of knowledge) directions that course of a number of values without delay.
These operations are helpful for probing: for instance, we will load a batch of (N) keys and examine them with our question in parallel.
In one of the best case, a SIMD probe sequence might run (N) occasions quicker than checking every key individually.

Let’s implement SIMD-accelerated lookups for linear probing and two-way chaining, with (N=4):

Sadly, SIMD lookups are slower for the linearly probed desk—a mean probe size of (1.5) meant the overhead of organising an (unaligned) SIMD comparability wasn’t value it.
Two-way chaining, however, will get fairly a bit quicker. Buckets are on common half full, and we will discover a key utilizing at most two (aligned) SIMD comparisons.

• The linear and Robin Hood tables use backshift deletion.
• The 2-way SIMD desk has capacity-4 buckets and makes use of AVX2 256-bit SIMD operations.
• Insert, erase, discover, discover unrolled, discover prefetched, and discover lacking report nanoseconds per operation.
• Common probe, max probe, common lacking probe, and max lacking probe report variety of iterations.
• Clear and iterate report milliseconds for the whole operation.
• Reminiscence studies the ratio of allotted reminiscence to measurement of saved knowledge.