Swiss Table SIMD Probing

In the previous lesson, we tore apart our open-addressed hash table and rebuilt its memory layout. Instead of bundling keys and state flags together inside an array of structures, we split our container into two parallel arrays: a Keys array and a contiguous 1-byte Metadata array.

By packing a 7-bit H2() hash fingerprint alongside negative kEmpty (-128) and kDeleted (-2) states inside each control byte, our container filtered out over 99% of hash collisions without ever touching the Keys array. Even with a scalar probing loop, shrinking our metadata footprint to 1 byte per slot cut our miss latencies nearly in half.

However, our SwissSet is still walking through that Metadata array one byte at a time. On a modern processor equipped with 128-bit, 256-bit, or 512-bit vector registers, inspecting a single byte per loop iteration leaves most of our silicon idle.

In this lesson, we will connect our contiguous Metadata array to the SIMD searching and bitmasking techniques we built earlier in the chapter. We will upgrade SwissSet to probe 16, 32, or 64 buckets in a single clock cycle, solve the physical wrap-around boundary problem using mirrored control bytes, and push our container's maximum load factor to 87.5%.

Let's examine how our current scalar Contains() method traverses the Metadata buffer when searching for a key:

1while (true) {
2  int8_t ctrl{Metadata[Index]};
3
4  if (ctrl == h2) {
5    if (Keys[Index] == key) return true;
6  }
7
8  if (ctrl == Ctrl::kEmpty) {
9    return false;
10  }
11
12  Index = (Index + 1) & Mask;
13}

Every iteration of this loop loads a single int8_t byte from Metadata[Index], executes two branches to test for h2 and kEmpty, and increments Index by 1. If a collision cluster forces us to step past 12 occupied slots, the CPU executes 12 loop iterations and 24 conditional jumps.

In a vectorized Swiss Table, we stop thinking in individual slots and start operating in groups. A group is simply a contiguous chunk of control bytes sized to match a single hardware vector register: xsimd::batch<int8_t>.

Depending on the CPU architecture our code is compiled for, the width of this group (xsimd::batch<int8_t>::size) automatically scales to fill the hardware's registers:

• 128-bit registers: A group is 16 bytes wide, inspecting 16 hash buckets per instruction.
• 256-bit registers: A group is 32 bytes wide, inspecting 32 hash buckets per instruction.
• 512-bit registers: A group is 64 bytes wide, inspecting an entire 64-byte cache line of 64 hash buckets in a single instruction.

Defining the Group Width and Initial Capacity

Introducing SIMD groups immediately creates a physical constraint on our table's minimum Capacity. In our scalar implementation, we initialized Capacity to 16 slots.

What happens if we compile that table on a processor where GroupWidth is 32 or even 64 bytes? If our table only has 16 slots, a single register load will attempt to read 32 or 64 bytes from a 16-byte buffer, immediately overflowing our heap allocation.

To guarantee that our table is always at least as wide as a hardware vector register, we'll initialize Capacity to either 16 or GroupWidth, using std::max to choose whichever is larger. Because GroupWidth is always a power of two (16, 32, or 64), our bitwise Mask continues to work without modification:

1#pragma once
2#include <vector>
3#include <cstdint>
4#include <cstddef>
5#include <limits>
6#include <bit> 
7#include <algorithm> 
8#include <xsimd/xsimd.hpp> 
9
10class SwissSet {
11  struct Ctrl {
12    static constexpr int8_t kEmpty = -128;  // 0b10000000
13    static constexpr int8_t kDeleted = -2;  // 0b11111110
14  };
15
16  using GroupBatch = xsimd::batch<int8_t>; 
17  static constexpr size_t GroupWidth{GroupBatch::size}; 
18
19private:
20  size_t Capacity{std::max<size_t>(16, GroupWidth)}; 
21  size_t Mask{Capacity - 1}; 
22  size_t Size{0};
23  size_t Tombstones{0};
24
25  std::vector<int8_t> Metadata;
26  std::vector<int> Keys;
27
28  // ...
29};

Before we write load_unaligned(&Metadata[Index]) inside our probe loop, we have to confront a physical memory hazard that did not exist when we wrote SimdFind() earlier in the chapter.

When we wrote SimdFind(), we always started our scan at index 0. In a hash table, our probe does not start at index 0. It starts at Index = H1(hash) & Mask, which can be any slot between 0 and Capacity - 1.

Imagine a SwissSet where Capacity is 32 and GroupWidth is 16. Suppose an incoming query hashes to starting slot Index = 28.

When we execute load_unaligned(&Metadata[28]), the CPU does not know that our Metadata array is supposed to behave like a circular ring buffer. The hardware instruction blindly loads 16 contiguous bytes from memory starting at &Metadata[28], which spans indices 28 through 43.

If Metadata is only 32 bytes long, two related bugs occur simultaneously:

1. Out-of-Bounds Heap Over-Read: Reading indices 32 through 43 reaches 12 bytes past the end of our std::vector<int8_t> allocation. This is undefined behavior and will trigger a segmentation fault if the end of the vector aligns with an unmapped OS page boundary.
2. Broken Ring Wrapping: Logically, in a 32-slot circular table, the 16-slot probe sequence starting at slot 28 consists of slots 28, 29, 30, 31 followed by wrapped-around slots 0, 1, 2, ..., 11. Reading garbage memory past index 31 completely misses the elements sitting at the front of the array.

Why Branching Kills Performance

Our first instinct might be to add an if statement inside the probe loop to check if Index + GroupWidth exceeds Capacity. If it does, we could perform two partial loads - one at the end of the array and one at index 0 - and stitch them together.

That would work, but it degrades our performance. Adding a boundary check and a split-load path inside the innermost probe loop reintroduces branch mispredictions and extra register shuffles on every query that lands near the end of the array.

We'd prefer to let the CPU execute a single, unconditional load_unaligned(&Metadata[Index]) instruction regardless of whether Index is 0, 15, or Capacity - 1.

Cloning the Leading Control Bytes

The Swiss Table architecture solves this by cloning the leading control bytes onto the tail of the Metadata buffer.

Instead of allocating Capacity bytes for Metadata, we allocate Capacity + GroupWidth bytes. The extra GroupWidth bytes sitting at the end of the array (at indices Capacity through Capacity + GroupWidth - 1) are maintained as an exact physical mirror of the first GroupWidth bytes (at indices 0 through GroupWidth - 1).

The following diagram shows how this would look with a Capacity of 16 and a GroupWidth of 8:

Whilst this mirroring adds a lot of overhead in our simple example where Capacity is only 16, in real-world use cases, we'll have capacity for thousands, millions, or billions of elements.

By mirroring a relatively tiny number (GroupWidth) of slots, we trade a few extra bytes of RAM to make every unaligned SIMD load near the end of the buffer automatically wrap around the ring in a single hardware instruction with zero branches.

Note that we only mirror the 1-byte Metadata array. We don't use any SIMD logic on the Keys array, so it can safely remain Capacity elements long.

Implementing SetCtrl()

To keep those trailing mirror bytes synchronized with the front of the Metadata array, we'll route all control byte updates through a small private helper method called SetCtrl():

1void SetCtrl(size_t index, int8_t ctrl) {
2  Metadata[index] = ctrl;
3  if (index < GroupWidth) {
4    Metadata[Capacity + index] = ctrl;
5  }
6}

Whenever index falls within the first GroupWidth slots (index is less than GroupWidth), SetCtrl() duplicates the write to Metadata[Capacity + index].

Let's add SetCtrl() to SwissSet.h and update our constructor and Grow() method so that Metadata always allocates Capacity + GroupWidth bytes:

1// ...
2class SwissSet {
3// ...
4private:
5  // ...
6  // Write a control byte and update its tail mirror
7  // if it sits within the first GroupWidth slots
8  void SetCtrl(size_t index, int8_t ctrl) { 
9    Metadata[index] = ctrl; 
10    if (index < GroupWidth) { 
11      Metadata[Capacity + index] = ctrl; 
12    } 
13  } 
14
15  void Grow() {
16    size_t OldCapacity{Capacity};
17    std::vector<int8_t> OldMetadata{std::move(Metadata)};
18    std::vector<int> OldKeys{std::move(Keys)};
19
20    Capacity *= 2;
21    Mask = Capacity - 1;
22
23    // Allocate Capacity + GroupWidth for mirrored tail
24    Metadata.assign( 
25      Capacity + GroupWidth, Ctrl::kEmpty 
26    ); 
27    Keys.assign(Capacity, 0);
28
29    Size = 0;
30    Tombstones = 0;
31
32    for (size_t i{0}; i < OldCapacity; ++i) {
33      if (OldMetadata[i] >= 0) {
34        Insert(OldKeys[i]);
35      }
36    }
37  }
38
39public:
40  // Allocate Capacity + GroupWidth bytes for Metadata
41  SwissSet() 
42    : Metadata(Capacity + GroupWidth, Ctrl::kEmpty), 
43      Keys(Capacity) {} 
44  // ...
45};

With our mirrored Metadata buffer in place, we are ready to replace the scalar while loop in Contains() with SIMD group probing.

When Contains(int key) is called, we first compute the 64-bit hash using Mix64(key), extract the starting bucket H1(hash) & Mask, and extract the 7-bit signature H2(hash).

Before entering the loop, we broadcast h2 and kEmpty into dedicated SIMD registers so the CPU can compare against both values across all lanes:

1GroupBatch h2Batch{GroupBatch::broadcast(h2)};
2GroupBatch emptyBatch{
3  GroupBatch::broadcast(Ctrl::kEmpty)
4};

Inside our probe loop, each iteration now inspects an entire GroupWidth chunk of slots in four steps. Let's walk through them with an example where Contains() is searching for an element where H1 maps to index 4 and we're looking for an H2 signature matching 0x2A.

We'll also imagine we get unlucky and encounter a 1-in-128 H2 collision where two lanes in our register of metadata values match, even though the original keys were different:

Let's update our Contains() with this vectorized implementation:

1// ...
2class SwissSet {
3// ...
4public:
5  // ...
6  bool Contains(int key) const {
7    uint64_t hash{Mix64(key)};
8    size_t Index{H1(hash) & Mask};
9    int8_t h2{H2(hash)};
10
11    GroupBatch h2Batch{GroupBatch::broadcast(h2)};
12    GroupBatch emptyBatch{
13      GroupBatch::broadcast(Ctrl::kEmpty)
14    };
15
16    while (true) {
17      GroupBatch ctrlGroup{
18        GroupBatch::load_unaligned(&Metadata[Index])
19      };
20
21      // Find all lanes in this group matching H2
22      uint64_t matchMask{
23        (ctrlGroup == h2Batch).mask()
24      };
25
26      while (matchMask != 0) {
27        size_t lane{
28          static_cast<size_t>(std::countr_zero(matchMask))
29        };
30        size_t pos{(Index + lane) & Mask};
31
32        if (Keys[pos] == key) return true;
33
34        matchMask &= (matchMask - 1);
35      }
36
37      // If any lane in this group is kEmpty, the probe
38      // chain has ended and the key does not exist
39      uint64_t emptyMask{
40        (ctrlGroup == emptyBatch).mask()
41      };
42      if (emptyMask != 0) return false;
43
44      // Leap forward by an entire SIMD group width
45      Index = (Index + GroupWidth) & Mask;
46    }
47  }
48  // ...
49};

Think about what the CPU executes on the common path here. In a table where most probe chains are shorter than 16 or 32 elements, while (true) does not even loop - it executes a single pass.

For a miss, 99.22% of the time matchMask is 0. The CPU skips the inner while (matchMask != 0) loop completely, sees emptyMask != 0, and returns false without ever touching the Keys array.

Now that Contains() is operating on SIMD groups, let's apply the same vectorized group probing to Erase() and Insert().

Vectorizing Erase()

Deleting a key in Erase(int key) follows the same search flow as Contains(). We load ctrlGroup at Index, find all lanes matching h2Batch, and step through the set bits of matchMask.

Once we find the lane where Keys[pos] == key, we mark that slot as a tombstone by calling SetCtrl(pos, kDeleted) so that both Metadata[pos] and its tail mirror (if pos is less than GroupWidth) are set to -2.

We then decrement Size, increment Tombstones, and return:

1// ...
2class SwissSet {
3// ...
4public:
5  // ...
6  void Erase(int key) {
7    uint64_t hash{Mix64(key)};
8    size_t Index{H1(hash) & Mask};
9    int8_t h2{H2(hash)};
10
11    GroupBatch h2Batch{GroupBatch::broadcast(h2)};
12    GroupBatch emptyBatch{
13      GroupBatch::broadcast(Ctrl::kEmpty)
14    };
15
16    while (true) {
17      GroupBatch ctrlGroup{
18        GroupBatch::load_unaligned(&Metadata[Index])
19      };
20
21      uint64_t matchMask{
22        (ctrlGroup == h2Batch).mask()
23      };
24
25      while (matchMask != 0) {
26        size_t lane{
27          static_cast<size_t>(std::countr_zero(matchMask))
28        };
29        size_t pos{(Index + lane) & Mask};
30
31        if (Keys[pos] == key) {
32          SetCtrl(pos, Ctrl::kDeleted);
33          --Size;
34          ++Tombstones;
35          return;
36        }
37
38        matchMask &= (matchMask - 1);
39      }
40
41      uint64_t emptyMask{
42        (ctrlGroup == emptyBatch).mask()
43      };
44      if (emptyMask != 0) return;
45
46      Index = (Index + GroupWidth) & Mask;
47    }
48  }
49};

Vectorizing Insert()

Vectorizing Insert(int key) requires a bit more care. Remember from our scalar implementation that Insert() has two jobs:

1. Walk the entire probe chain up to the first kEmpty slot to verify that key is not already in the set.
2. Insert the new key into the earliest available slot (kDeleted or kEmpty) encountered along that probe chain.

When we inspect 16 or 32 slots at once in a SIMD group, a subtle ordering edge case can occur. Imagine our probe group loads 16 control bytes where Lane 3 is kEmpty and Lane 7 is kDeleted. This would happen if an unrelated key hashed directly to Index + 7 earlier in the program's life and had been erased later.

If our code checked the group for kDeleted slots before checking for kEmpty, it might see the tombstone at Lane 7 and insert our new key at Index + 7. That would be a bug. Because Lane 3 is kEmpty, any future Contains() query for our key would stop at Lane 3 and return false, never reaching Lane 7.

How do we ensure we always pick whichever available slot (kDeleted or kEmpty) comes first in the group? We combine their bitmasks with a bitwise OR (|). In each group, we compute emptyMask and deletedMask:

1uint64_t emptyMask{(ctrlGroup == emptyBatch).mask()};
2uint64_t deletedMask{(ctrlGroup == deletedBatch).mask()};

If emptyMask == 0, the probe chain continues into the next group. Before we move on, if FirstDeleted == InvalidIndex and deletedMask != 0, we record the earliest tombstone in this group using std::countr_zero(deletedMask). Because emptyMask is 0, every slot in this group precedes the end of the probe chain.

Once we reach a group where emptyMask != 0, the probe chain ends in this group. If we did not already find a FirstDeleted tombstone in an earlier group, the earliest valid insertion slot in this group is simply the lowest set bit of emptyMask | deletedMask:

• If a tombstone sits at Lane 1 and the empty slot sits at Lane 4, std::countr_zero(emptyMask | deletedMask) returns 1, recycling the tombstone that precedes the empty slot.
• If the empty slot sits at Lane 3 and an unrelated tombstone sits at Lane 7, std::countr_zero(emptyMask | deletedMask) returns 3, claiming the empty slot and never jumping past the end of the probe chain.

Then, right before we call SetCtrl(Target, h2), we check if Metadata[Target] is kDeleted, and decrement the tombstone count if so:

1// ...
2class SwissSet {
3// ...
4public:
5  // ...
6  void Insert(int key) {
7    if ((Size + Tombstones) >= (Capacity * 0.7f)) {
8      Grow();
9    }
10
11    uint64_t hash{Mix64(key)};
12    size_t Index{H1(hash) & Mask};
13    int8_t h2{H2(hash)};
14    size_t FirstDeleted{InvalidIndex};
15
16    GroupBatch h2Batch{GroupBatch::broadcast(h2)};
17    GroupBatch emptyBatch{
18      GroupBatch::broadcast(Ctrl::kEmpty)
19    };
20    GroupBatch deletedBatch{
21      GroupBatch::broadcast(Ctrl::kDeleted)
22    };
23
24    while (true) {
25      GroupBatch ctrlGroup{
26        GroupBatch::load_unaligned(&Metadata[Index])
27      };
28
29      // Check for duplicate keys among H2 matches
30      uint64_t matchMask{
31        (ctrlGroup == h2Batch).mask()
32      };
33      while (matchMask != 0) {
34        size_t lane{
35          static_cast<size_t>(std::countr_zero(matchMask))
36        };
37        size_t pos{(Index + lane) & Mask};
38        if (Keys[pos] == key) return;
39        matchMask &= (matchMask - 1);
40      }
41
42      uint64_t emptyMask{
43        (ctrlGroup == emptyBatch).mask()
44      };
45      uint64_t deletedMask{
46        (ctrlGroup == deletedBatch).mask()
47      };
48
49      // If the probe chain ends in this group, insert
50      // at FirstDeleted or the first available lane here
51      if (emptyMask != 0) {
52        size_t Target{FirstDeleted};
53        if (Target == InvalidIndex) {
54          uint64_t availMask{emptyMask | deletedMask};
55          size_t lane{
56            static_cast<size_t>(std::countr_zero(availMask))
57          };
58          Target = (Index + lane) & Mask;
59        }
60
61        if (Metadata[Target] == Ctrl::kDeleted) {
62          --Tombstones;
63        }
64
65        SetCtrl(Target, h2);
66        Keys[Target] = key;
67        ++Size;
68        return;
69      }
70
71      // Otherwise, record the first tombstone if we
72      // haven't seen one yet, and advance to the next group
73      if (FirstDeleted == InvalidIndex &&
74          deletedMask != 0) {
75        size_t lane{
76          static_cast<size_t>(std::countr_zero(deletedMask))
77        };
78        FirstDeleted = (Index + lane) & Mask;
79      }
80
81      Index = (Index + GroupWidth) & Mask;
82    }
83  }
84  // ...
85};

Up to this point, every open-addressed hash table we built - FlatHashSet, RobinHoodSet, and our initial SwissSet - triggered a Grow() reallocation as soon as occupancy hit 70% (Capacity * 0.7f).

We left 30% of our allocated memory empty because, in scalar linear probing, primary clustering causes average probe lengths to climb steeply once a table passes 70% occupancy. At a 70% load factor, a missed query probes around 3 slots on average. At an 87.5% load factor, primary clusters merge, and a missed query can easily probe 10 to 16 slots.

However, with SIMD group probing, that doesn't matter. Probing 16 slots or 32 slots with vector registers takes one instruction. Whether a probe chain is 1 slot long or 14 slots long, a single load_unaligned() swallows the entire cluster in one clock cycle.

Because of this hardware throughput, Swiss Tables raise their maximum load factor from 70% up to 87.5%. At 87.5% occupancy, an average of 2 slots per 16-byte group (or 4 slots per 32-byte group) are still kEmpty. Almost every lookup still terminates on its very first SIMD group check.

Packing buckets to 87.5% capacity before growing means our container stores 25% more elements in the same RAM footprint and triggers fewer expensive heap reallocations as datasets scale.

Why 87.5%?

So, why would we choose the oddly specific $87.5$ for our load factor? Because it is exactly $7/8$ or equivalently, $1 - 1/8$.

This means we can eliminate the floating-point multiplication Capacity * 0.7f from our Insert() path and replace it with exact, single-cycle bitwise shift math:

1// Equivalent: Capacity - (Capacity /  8)
2size_t MaxLoad{Capacity - (Capacity >> 3)};

Fast Reallocation with InsertUnique()

While we are optimizing our growth mechanics, let's take a look at what Grow() currently does when rehashing live keys into the newly doubled buffer:

1for (size_t i{0}; i < OldCapacity; ++i) {
2  if (OldMetadata[i] >= 0) {
3    Insert(OldKeys[i]);
4  }
5}

Calling the public Insert() method inside Grow() does unnecessary work on every single element:

• It checks the load factor threshold on every iteration, even though we just doubled Capacity.
• It compares ctrlGroup == h2Batch and checks Keys[pos] == key to guard against duplicates, even though every element coming from OldKeys is already guaranteed to be unique.
• It checks for kDeleted tombstones, even though the new Metadata buffer was just wiped clean to kEmpty and contains zero tombstones.

We can write a dedicated private helper method called InsertUnique(int key) specifically for Grow().

Because there are no duplicates and no tombstones in a freshly allocated buffer, InsertUnique() simply loads ctrlGroup, checks (ctrlGroup == emptyBatch).mask(), and drops the element directly into the first empty lane:

1// ...
2class SwissSet {
3// ...
4private:
5  // ...
6  // Fast insertion path for Grow(): assumes no duplicates
7  // and no tombstones exist in the freshly allocated table
8  void InsertUnique(int key) {
9    uint64_t hash{Mix64(key)};
10    size_t Index{H1(hash) & Mask};
11    int8_t h2{H2(hash)};
12
13    GroupBatch emptyBatch{
14      GroupBatch::broadcast(Ctrl::kEmpty)
15    };
16
17    while (true) {
18      GroupBatch ctrlGroup{
19        GroupBatch::load_unaligned(&Metadata[Index])
20      };
21
22      uint64_t emptyMask{
23        (ctrlGroup == emptyBatch).mask()
24      };
25
26      if (emptyMask != 0) {
27        size_t lane{
28          static_cast<size_t>(std::countr_zero(emptyMask))
29        };
30        size_t Target{(Index + lane) & Mask};
31
32        SetCtrl(Target, h2);
33        Keys[Target] = key;
34        ++Size;
35        return;
36      }
37
38      Index = (Index + GroupWidth) & Mask;
39    }
40  }
41
42  void Grow() {
43    size_t OldCapacity{Capacity};
44    std::vector<int8_t> OldMetadata{std::move(Metadata)};
45    std::vector<int> OldKeys{std::move(Keys)};
46
47    Capacity *= 2;
48    Mask = Capacity - 1;
49
50    Metadata.assign(
51      Capacity + GroupWidth, Ctrl::kEmpty
52    );
53    Keys.assign(Capacity, 0);
54
55    Size = 0;
56    Tombstones = 0;
57
58    for (size_t i{0}; i < OldCapacity; ++i) {
59      if (OldMetadata[i] >= 0) {
60        Insert(OldKeys[i]); 
61        InsertUnique(OldKeys[i]); 
62      }
63    }
64  }
65
66public:
67  // ...
68  void Insert(int key) {
69    // 87.5% (7/8ths) maximum load factor using bit-shift
70    if ((Size + Tombstones) >= 
71        (Capacity - (Capacity >> 3))) { 
72      Grow();
73    }
74    // ...
75  }
76  // ...
77};

Let's rerun our benchmarks. The following tests are identical to what we ran in the previous lesson - the only difference is that our imported SwissSet is now using SIMD behind the scenes:

1#include <benchmark/benchmark.h>
2#include <unordered_set>
3#include <vector>
4#include <random>
5#include <algorithm>
6#include <dsa/FlatHashSet.h>
7#include <dsa/RobinHoodSet.h>
8#include <dsa/SwissSet.h>
9
10const int kNumElements = 3'000'000;
11const int kNumQueries = 1'000'000;
12
13std::vector<int> GenerateData() {
14  std::vector<int> data(kNumElements);
15  std::mt19937 rng(42);
16
17  std::uniform_int_distribution<int> dist(1, 50'000'000);
18  for (int i = 0; i < kNumElements; ++i) data[i] = dist(rng);
19  return data;
20}
21
22const std::vector<int> Data = GenerateData();
23
24std::vector<int> GenerateQueries(double miss_rate) {
25  std::vector<int> queries;
26  queries.reserve(kNumQueries);
27
28  int misses = kNumQueries * miss_rate;
29  int hits = kNumQueries - misses;
30
31  for (int i = 0; i < hits; ++i) {
32    queries.push_back(Data[i]);
33  }
34
35  for (int i = 0; i < misses; ++i) {
36    queries.push_back(i + 100'000'000);
37  }
38
39  std::mt19937 rng(42);
40  std::shuffle(queries.begin(), queries.end(), rng);
41
42  return queries;
43}
44
45static void BM_StdSet(benchmark::State& state) {
46  double miss_rate = state.range(0) / 100.0;
47  std::vector<int> queries = GenerateQueries(miss_rate);
48  std::unordered_set<int> set(Data.begin(), Data.end());
49
50  for (auto _ : state) {
51    for (int query : queries) {
52      benchmark::DoNotOptimize(set.contains(query));
53    }
54  }
55}
56
57static void BM_FlatHashSet(benchmark::State& state) {
58  double miss_rate = state.range(0) / 100.0;
59  std::vector<int> queries = GenerateQueries(miss_rate);
60
61  FlatHashSet set;
62  for (int val : Data) set.Insert(val);
63
64  for (auto _ : state) {
65    for (int query : queries) {
66      benchmark::DoNotOptimize(set.Contains(query));
67    }
68  }
69}
70
71static void BM_RobinHood(benchmark::State& state) {
72  double miss_rate = state.range(0) / 100.0;
73  std::vector<int> queries = GenerateQueries(miss_rate);
74
75  RobinHoodSet set;
76  for (int val : Data) set.Insert(val);
77
78  for (auto _ : state) {
79    for (int query : queries) {
80      benchmark::DoNotOptimize(set.Contains(query));
81    }
82  }
83}
84
85static void BM_SwissSet(benchmark::State& state) {
86  double miss_rate = state.range(0) / 100.0;
87  std::vector<int> queries = GenerateQueries(miss_rate);
88
89  SwissSet set;
90  for (int val : Data) set.Insert(val);
91
92  for (auto _ : state) {
93    for (int query : queries) {
94      benchmark::DoNotOptimize(set.Contains(query));
95    }
96  }
97}
98
99#define REGISTER_BENCHMARK(func) BENCHMARK(func) \
100  ->Unit(benchmark::kMillisecond) \
101  ->ArgName("MissRatePct") \
102  ->Arg(1) \
103  ->Arg(50) \
104  ->Arg(99)
105
106REGISTER_BENCHMARK(BM_StdSet);
107REGISTER_BENCHMARK(BM_FlatHashSet);
108REGISTER_BENCHMARK(BM_RobinHood);
109REGISTER_BENCHMARK(BM_SwissSet);

1---------------------------------------
2Benchmark                           CPU
3---------------------------------------
4BM_StdSet/MissRatePct:1         71.4 ms
5BM_StdSet/MissRatePct:50        73.9 ms
6BM_StdSet/MissRatePct:99        62.5 ms
7
8BM_FlatHashSet/MissRatePct:1    22.9 ms
9BM_FlatHashSet/MissRatePct:50   42.7 ms
10BM_FlatHashSet/MissRatePct:99   79.9 ms
11
12BM_RobinHood/MissRatePct:1      33.5 ms
13BM_RobinHood/MissRatePct:50     50.0 ms
14BM_RobinHood/MissRatePct:99     42.0 ms
15
16BM_SwissSet/MissRatePct:1       28.0 ms
17BM_SwissSet/MissRatePct:50      25.7 ms
18BM_SwissSet/MissRatePct:99      15.0 ms

In these tests, our SIMD SwissSet completes the 1,000,000 lookups in around half the time of the scalar implementation of the previous lesson. Our vectorized Contains() function is performing 16, 32, or 64 lookups concurrently, but our scalar containers were already designed to avoid such long probe chains.

We set their maximum load factor to 70%, so even when packed to their limit, Contains() would only need to check around 3 slots on average. The SIMD implementation of SwissSet allowed us to increase the maximum load factor to 87.5%. This increases our average probe length, but still keeps it well under 16 - enough to complete in a single vector operation.

This increased load factor also improves memory efficiency. Storing the 3,000,000 elements from this example requires our SwissSet to Grow() to around 4 million slots: $2^{22}$. To store the same elements, FlatHashSet and RobinHoodSet need to increase their capacity to around 8 million - $2^{23}$ - to remain under their 70% load factor limit.

When we combine this with the additional padding and DIB metadata that these containers require, their memory usage is more than double that of our SwissSet.

Optimizing Batch Size

By default, an xsimd::batch tries to use the largest registers it can, giving us the biggest possible lane count.

However, this is not always the best idea. If 16 lookups are almost always going to be sufficient to complete a task, using a 32- or 64-lane batch can add unnecessary overhead. This is particularly true if using that larger batch forces our unaligned data loads and stores to span an additional cache line.

We can specify how many lanes we want to use for a xsimd::batch by setting the target architecture through a second template argument. This is most commonly used to declare that we only need a 128-bit register (sse2) for this batch, but other options are available:

1// 128-bit batch: 16 x int8_t lanes
2xsimd::batch<int8_t, xsimd::sse2> a;
3
4// 256-bit batch: 32 x int8_t lanes
5xsimd::batch<int8_t, xsimd::avx2> b;
6
7// 512-bit batch: 64 x int8_t lanes
8xsimd::batch<int8_t, xsimd::avx512bw> c;

We can check if the build is configured to support a given architecture using the supported() function. This is also available at compile time:

1static_assert(
2  xsimd::avx512bw::supported(),
3  "AVX-512BW not available"
4);

Just because the compiler emitted instructions for a given architecture, that doesn't mean the system our program is currently running on can use them. We can defensively check if an architecture is available at run time using the available_architectures() function:

1if (xsimd::available_architectures().avx512bw) {
2  // safe to run AVX-512 code
3}

The xsimd library provides many more advanced options for writing code that detects, manipulates, and adapts to different architectures. Their official documentation lists all of the options.

Here is the complete, SIMD-accelerated implementation of our SwissSet alongside an example usage in main.cpp:

1Contains 420? Yes
2Contains 420 after erase? No
3Contains 420 after re-insert? Yes

In this lesson, we combined data-oriented design with explicit SIMD vectorization to introduce the modern industry-standard hash table:

1. SIMD Group Probing: By loading 16 or 32 1-byte control values into an xsimd::batch<int8_t> register, we replaced byte-by-byte scalar probe loops with parallel vector comparisons that inspect an entire neighborhood of buckets in a single clock cycle.
2. Mirrored Control Bytes: Unaligned SIMD loads near the end of an array can read out-of-bounds and fail to wrap around the ring. Allocating Capacity + GroupWidth bytes for Metadata and cloning the first GroupWidth bytes into the tail via SetCtrl() lets hardware vector loads wrap around efficiently with no branching.
3. Bitmask Candidate Hopping: Combining mask(), std::countr_zero(), and Kernighan's matchMask &= (matchMask - 1) trick allows the CPU to skip directly to matching 7-bit H2 candidates, and combining emptyMask | deletedMask during insertion prevents jumping past the end of a probe chain.
4. The 87.5% Load Factor: Because SIMD batch comparisons absorb primary clusters in a single instruction, Swiss Tables safely operate up to an 87.5% load factor using Capacity - (Capacity >> 3), packing 25% more data into RAM.
5. Fast Paths: We can use optimized logic when we know our container is in a specific state, such as accelerating insertions into a freshly allocated container via InsertUnique().

Our SwissSet is now fast on a single thread. However, can we get even more performance by bringing in additional threads? In the final lesson of this chapter, we will explore why lock-free resizing is a minefield, and how to scale our Swiss Table across multiple threads using striped hashing instead.