Concurrency and Striped Hashing

In the previous lesson, we completed our single-threaded SwissSet. By splitting our container into a structure of arrays and inspecting 16, 32, or 64 control bytes simultaneously using xsimd, we built a hash table that outperforms std::unordered_set by nearly an order of magnitude.

However, our SwissSet assumes a single thread is executing operations sequentially. Modern servers and game engines run across dozens of physical CPU cores. If two threads simultaneously call Insert() and Contains() on our SwissSet, they will corrupt the control bytes, tear key writes, or trigger an immediate segmentation fault when Grow() reallocates the underlying buffers.

In this final lesson of the chapter, we will build a thread-safe ConcurrentSwissSet. We will start with a simple global lock, see why it fails under multithreaded contention, and incrementally evolve our class to use striped sharding, reader-writer locks, and cache-line alignment.

Earlier in the course, we built lock-free data structures like the MPMC Ring Buffer using hardware Compare-And-Swap (CAS) loops. It is natural to wonder if we can make SwissSet lock-free by simply turning our Metadata and Keys arrays into std::atomic variables.

Unfortunately, our SIMD Swiss Table relies on two physical mechanisms that conflict directly with lock-free CAS instructions.

First, a hardware CAS instruction can only update a single contiguous memory location. In our SwissSet, inserting a single element requires updating two separate heap allocations -Metadata[Target] and Keys[Target] - plus a potential third write to the mirrored tail byte at Metadata[Capacity + Target]. We cannot update three disjointed addresses atomically in a single hardware instruction.

Second, and even more importantly, our lock-free ring buffer had a fixed capacity, whereas a hash table must dynamically reallocate via Grow(). If one thread allocates a new buffer and starts rehashing keys, any threads simultaneously working with the old buffer will be severely disrupted.

Since lock-free resizing is incompatible with our SIMD layout, we need mutual exclusion . Let's begin by building a baseline version of ConcurrentSwissSet that wraps a single SwissSet instance with a std::mutex.

First, so that we can verify our multithreaded insertions in our test programs, let's add a simple GetSize() method to the bottom of SwissSet.h from the previous lesson:

1// ...
2class SwissSet {
3// ...
4public:
5  // ...
6  void Erase(int key) {
7    // ...
8  }
9
10  size_t GetSize() const { return Size; } 
11};

Now let's create a new class in ConcurrentSwissSet.h that will manage concurrent access to our SwissSet.

In this initial implementation, every call to Insert(), Contains(), Erase(), or GetSize() acquires a std::lock_guard on the Mutex member before interacting with the underlying SwissSet.

Note that we mark Mutex with the mutable keyword so that const methods like Contains() and GetSize() can still lock and unlock it:

1#pragma once
2#include <mutex>
3#include <cstddef>
4#include <dsa/SwissSet.h>
5
6class ConcurrentSwissSet {
7private:
8  SwissSet Set;
9  mutable std::mutex Mutex;
10
11public:
12  ConcurrentSwissSet() = default;
13
14  void Insert(int key) {
15    std::lock_guard<std::mutex> lock{Mutex};
16    Set.Insert(key);
17  }
18
19  bool Contains(int key) const {
20    std::lock_guard<std::mutex> lock{Mutex};
21    return Set.Contains(key);
22  }
23
24  void Erase(int key) {
25    std::lock_guard<std::mutex> lock{Mutex};
26    Set.Erase(key);
27  }
28
29  size_t GetSize() const {
30    std::lock_guard<std::mutex> lock{Mutex};
31    return Set.GetSize();
32  }
33};

Let's verify that this class protects our container across multiple threads.

In main.cpp, we will spawn 4 worker threads using std::jthread. Each thread will concurrently insert 10,000 integers into ConcurrentSwissSet, forcing the underlying SwissSet through multiple Grow() reallocations while other threads are actively inserting:

1#include <iostream>
2#include <thread>
3#include <vector>
4#include <dsa/ConcurrentSwissSet.h>
5
6int main() {
7  ConcurrentSwissSet Set;
8
9  constexpr int kNumThreads{4};
10  constexpr int kItemsPerThread{10'000};
11
12  // Spawn 4 threads inserting 40,000 keys concurrently
13  {
14    std::vector<std::jthread> workers;
15    for (int t{0}; t < kNumThreads; ++t) {
16      workers.emplace_back([&Set, t]() {
17        int start{t * kItemsPerThread};
18        int end{start + kItemsPerThread};
19        for (int i{start}; i < end; ++i) {
20          Set.Insert(i);
21        }
22      });
23    }
24  } // All jthreads automatically join here
25
26  std::cout << "Total elements inserted: "
27    << Set.GetSize() << "\n";
28
29  std::cout << "Contains 42? "
30    << (Set.Contains(42) ? "Yes" : "No") << "\n";
31  std::cout << "Contains 35000? "
32    << (Set.Contains(35'000) ? "Yes" : "No") << "\n";
33
34  Set.Erase(42);
35  std::cout << "Contains 42 after erase? "
36    << (Set.Contains(42) ? "Yes" : "No");
37}

1Total elements inserted: 40000
2Contains 42? Yes
3Contains 35000? Yes
4Contains 42 after erase? No

Why the Global Mutex Kills Scaling

Our ConcurrentSwissSet is now thread-safe, and all 40,000 keys are accounted for without a single race condition. However, from a hardware perspective, wrapping a fast data structure in a single global mutex destroys multicore performance.

When 8 CPU cores call Contains() or Insert() at the same time, 1 core acquires Mutex while the other 7 cores are forced to wait. Even though we have 8 physical cores available, our hash table can run on only 1 core at a time.

Worse still, because a SIMD SwissSet operation only takes a few nanoseconds, all 8 cores are constantly fighting to modify the same 64-byte cache line holding Mutex.

As we learned in our lesson on Cache Coherency and False Sharing , this triggers a storm of MESI cache invalidations across the CPU interconnect. The processor spends far more clock cycles bouncing the mutex's cache line between cores than it spends probing our hash table.

To let multiple CPU cores operate on ConcurrentSwissSet in parallel without giving up our SIMD group probing, we need to split our single point of contention.

We already solved a version of this problem in the previous chapter when we built our Consistent Hash Ring . When a single server could not handle the network traffic of millions of players, we used a hash function to partition the keys across an array of independent servers.

We can apply that same architecture inside our ConcurrentSwissSet. This pattern is called Striped Hashing (or Sharding).

Instead of storing one giant SwissSet guarded by one global std::mutex, we divide ConcurrentSwissSet into an array of independent sub-tables called stripes (or shards). Each stripe owns its own SwissSet and its own dedicated mutex.

Every possible key gets routed to only one of the stripes, allowing multiple threads to interact with different keys concurrently. The following diagram shows this architecture with our data divided across only four shards, but we typically use many more:

Suppose we partition our ConcurrentSwissSet into NumStripes = 64 stripes. When Thread A wants to insert a key, it hashes the key to select one of the 64 stripes - say, Stripes[12] - locks Stripes[12].Mutex, and inserts the key into Stripes[12].Set.

If Thread B simultaneously queries a key that routes to Stripes[19], it locks Stripes[19].Mutex and runs its SIMD probe completely in parallel with Thread A.

Even if Stripes[12] hits its load factor limit and triggers Grow(), only Stripes[12] pauses to reallocate. Additionally, because each stripe only stores $1/64$ of the total dataset, we don't need to rehash every key to grow our container. Our sharded design therefore has the added benefit of smoothing out our reallocation spikes.

Orthogonal Hash Bit Slicing

To route a key to one of our 64 ($2^6$) stripes, we need 6 bits from the key's 64-bit hash, but we should be careful about which 6 bits we choose. Because both ConcurrentSwissSet and SwissSet are using the same keys and the same Mix64() function, these allocations risk becoming correlated, which can drastically degrade performance.

Remember, we want to keep our hashing mechanisms as randomized as possible - distributing keys throughout the container to minimize collisions and to minimize the length of primary clusters when collisions do occur.

The worst case of correlation would be if we used the same bits from our hash to assign both the shard index within ConcurrentSwissSet and the bucket index within SwissSet.

This could create a situation where, for example, every key routed to Stripes[5] by our top-level ConcurrentSwissSet would get assigned to bucket 5 within that stripe's SwissSet, causing 100% of them to collide and form a huge, single primary cluster.

To avoid correlation, we should pick bits for our stripe index that never overlap with the bits used by H1 or H2 within the SwissSet. Because 64 stripes only require 6 bits, we can use the top 6 bits to allocate hashes to a shard:

This relies on a hash function that avalanches across all 64 bits. Our Mix64() function meets this requirement - the top 6 bits are statistically independent of the lower bits.

Implementing the Striped Container

Let's update ConcurrentSwissSet.h to replace our single Set and Mutex with a std::array<Stripe, 64>.

We will include <array> and <cstdint>, add the Mix64() function to compute the routing hash, and use GetStripeIndex() to direct Insert(), Contains(), and Erase() to the appropriate stripe.

For GetSize(), we iterate over all 64 stripes and sum their individual sizes:

1#pragma once
2#include <array> 
3#include <mutex>
4#include <cstdint> 
5#include <cstddef>
6#include <dsa/SwissSet.h>
7
8class ConcurrentSwissSet {
9private:
10  // 2^6 = 64 independent stripes
11  static constexpr size_t StripeBits{6};
12  static constexpr size_t NumStripes{1ULL << StripeBits};
13
14  struct Stripe {
15    SwissSet Set;
16    mutable std::mutex Mutex;
17  };
18
19  std::array<Stripe, NumStripes> Stripes;
20
21  uint64_t Mix64(uint64_t x) const {
22    x ^= x >> 30;
23    x *= 0xbf58476d1ce4e5b9ULL;
24    x ^= x >> 27;
25    x *= 0x94d049bb133111ebULL;
26    x ^= x >> 31;
27    return x;
28  }
29
30  // Extract the top 6 bits (Bits 58..63) to select
31  // a stripe without overlapping H1 or H2
32  size_t GetStripeIndex(int key) const {
33    uint64_t hash{Mix64(key)};
34    return static_cast<size_t>(
35      hash >> (64 - StripeBits)
36    );
37  }
38
39public:
40  ConcurrentSwissSet() = default;
41
42  void Insert(int key) {
43    Stripe& stripe{Stripes[GetStripeIndex(key)]};
44    std::lock_guard<std::mutex> lock{stripe.Mutex};
45    stripe.Set.Insert(key);
46  }
47
48  bool Contains(int key) const {
49    const Stripe& stripe{Stripes[GetStripeIndex(key)]};
50    std::lock_guard<std::mutex> lock{stripe.Mutex};
51    return stripe.Set.Contains(key);
52  }
53
54  void Erase(int key) {
55    Stripe& stripe{Stripes[GetStripeIndex(key)]};
56    std::lock_guard<std::mutex> lock{stripe.Mutex};
57    stripe.Set.Erase(key);
58  }
59
60  size_t GetSize() const {
61    size_t total{0};
62    for (const Stripe& stripe : Stripes) {
63      std::lock_guard<std::mutex> lock{stripe.Mutex};
64      total += stripe.Set.GetSize();
65    }
66    return total;
67  }
68};

Let's look closely at what happens on the CPU whenever we call Contains(key) in the code above.

First, ConcurrentSwissSet calls GetStripeIndex(key), which runs the Mix64(key) bit-mixer to compute the 64-bit hash and shifts it right by 58 bits to locate the Stripe.

Then, inside that stripe, stripe.Set.Contains(key) runs Mix64(key) a second time on the same integer to extract H1 and H2. We are executing twice as many hash multiplications and shifts as necessary on every single operation, and duplicating the Mix64() code across two classes.

We can eliminate this wasted work by computing the 64-bit hash once in ConcurrentSwissSet and passing that precomputed hash directly into SwissSet.

Let's update SwissSet to make Mix64() a public static method, and split Insert(), Contains(), and Erase() into overloads that accept a precomputed uint64_t hash:

1// ...
2class SwissSet {
3// ...
4private:
5  // ...
6  static constexpr size_t InvalidIndex{
7    std::numeric_limits<size_t>::max()
8  };
9
10// Expose Mix64 as a public static helper
11public: 
12  static uint64_t Mix64(uint64_t x) { 
13    x ^= x >> 30;
14    x *= 0xbf58476d1ce4e5b9ULL;
15    x ^= x >> 27;
16    x *= 0x94d049bb133111ebULL;
17    x ^= x >> 31;
18    return x;
19  }
20
21private: 
Unchanged Functions|Show
93
94public:
95  SwissSet()
96    : Metadata(Capacity + GroupWidth, Ctrl::kEmpty),
97      Keys(Capacity) {}
98
99  // Pre-hashed overload for zero-overhead stripe routing
100  void Insert(int key, uint64_t hash) { 
101    uint64_t hash{Mix64(key)};
Remaining code unchanged|Show
173  }
174
175  void Insert(int key) { 
176    Insert(key, Mix64(key)); 
177  } 
178
179  bool Contains(int key, uint64_t hash) const { 
180    uint64_t hash{Mix64(key)};
Remaining code unchanged|Show
215  }
216
217  bool Contains(int key) const { 
218    return Contains(key, Mix64(key)); 
219  } 
220
221  void Erase(int key, uint64_t hash) { 
222    uint64_t hash{Mix64(key)};
Remaining code unchanged|Show
263  }
264
265  void Erase(int key) { 
266    Erase(key, Mix64(key)); 
267  } 
268
269  size_t GetSize() const { return Size; }
270};

Now we can simplify ConcurrentSwissSet so that it calls SwissSet::Mix64(key) once and forwards hash into the target stripe:

1// ...
2class ConcurrentSwissSet {
3private:
4  static constexpr size_t StripeBits{6};
5  static constexpr size_t NumStripes{1ULL << StripeBits};
6
7  struct Stripe {
8    SwissSet Set;
9    mutable std::mutex Mutex;
10  };
11
12  std::array<Stripe, NumStripes> Stripes;
13
14  static size_t GetStripeIndex(uint64_t hash) { 
15    return static_cast<size_t>(
16      hash >> (64 - StripeBits)
17    );
18  }
19
20public:
21  ConcurrentSwissSet() = default;
22
23  void Insert(int key) {
24    uint64_t hash{SwissSet::Mix64(key)}; 
25    Stripe& stripe{Stripes[GetStripeIndex(hash)]}; 
26    std::lock_guard<std::mutex> lock{stripe.Mutex};
27    stripe.Set.Insert(key, hash); 
28  }
29
30  bool Contains(int key) const {
31    uint64_t hash{SwissSet::Mix64(key)}; 
32    const Stripe& stripe{Stripes[GetStripeIndex(hash)]}; 
33    std::lock_guard<std::mutex> lock{stripe.Mutex};
34    return stripe.Set.Contains(key, hash); 
35  }
36
37  void Erase(int key) {
38    uint64_t hash{SwissSet::Mix64(key)}; 
39    Stripe& stripe{Stripes[GetStripeIndex(hash)]}; 
40    std::lock_guard<std::mutex> lock{stripe.Mutex};
41    stripe.Set.Erase(key, hash); 
42  }
43
44  // ...
45};

Splitting our container into 64 stripes dramatically reduces lock contention, but we are still leaving performance on the table when multiple threads read from the same stripe.

Right now, each stripe uses a full-blown std::mutex. A std::mutex is an exclusive lock: it treats a read-only Contains() query identically to a mutating Insert() or Erase() call.

In most production systems, hash table traffic is heavily dominated by reads. A server might check if a session ID or asset handle exists 99% of the time, and only insert or remove entries 1% of the time.

If two threads concurrently call Contains() on keys that map to Stripes[12], neither thread is modifying a single byte of memory, yet std::mutex forces the second thread to wait until the first thread finishes.

Using std::shared_mutex

C++17 provides std::shared_mutex in the <shared_mutex> header, which acts as a Reader-Writer Lock.

When a thread wants to mutate a stripe, it acquires an exclusive lock using std::unique_lock<std::shared_mutex>. While an exclusive lock is held, no other writer or reader can enter that stripe. If Insert() triggers Grow(), it has exclusive ownership of that stripe's buffers.

When a thread only wants to read from a stripe using Contains() or GetSize(), it acquires a shared lock using std::shared_lock<std::shared_mutex>. Any number of reader threads can hold a std::shared_lock on the same stripe at the same time, running their SIMD Contains() probes concurrently without blocking each other.

Let's update ConcurrentSwissSet to use std::shared_mutex, std::unique_lock, and std::shared_lock:

1#pragma once
2#include <array>
3#include <mutex>
4#include <shared_mutex> 
5#include <cstdint>
6#include <cstddef>
7#include <dsa/SwissSet.h>
8
9class ConcurrentSwissSet {
10private:
11  static constexpr size_t StripeBits{6};
12  static constexpr size_t NumStripes{1ULL << StripeBits};
13
14  struct Stripe {
15    SwissSet Set;
16    mutable std::shared_mutex Mutex; 
17  };
18
19  std::array<Stripe, NumStripes> Stripes;
20
21  static size_t GetStripeIndex(uint64_t hash) {
22    return static_cast<size_t>(
23      hash >> (64 - StripeBits)
24    );
25  }
26
27public:
28  ConcurrentSwissSet() = default;
29
30  void Insert(int key) {
31    uint64_t hash{SwissSet::Mix64(key)};
32    Stripe& stripe{Stripes[GetStripeIndex(hash)]};
33
34    // Exclusive lock: only one writer allowed in this stripe
35    std::unique_lock<std::shared_mutex> lock{ 
36      stripe.Mutex 
37    }; 
38    stripe.Set.Insert(key, hash);
39  }
40
41  bool Contains(int key) const {
42    uint64_t hash{SwissSet::Mix64(key)};
43    const Stripe& stripe{Stripes[GetStripeIndex(hash)]};
44
45    // Shared lock: multiple readers can probe simultaneously
46    std::shared_lock<std::shared_mutex> lock{ 
47      stripe.Mutex 
48    }; 
49    return stripe.Set.Contains(key, hash);
50  }
51
52  void Erase(int key) {
53    uint64_t hash{SwissSet::Mix64(key)};
54    Stripe& stripe{Stripes[GetStripeIndex(hash)]};
55
56    // Exclusive lock for mutation
57    std::unique_lock<std::shared_mutex> lock{ 
58      stripe.Mutex 
59    }; 
60    stripe.Set.Erase(key, hash);
61  }
62
63  size_t GetSize() const {
64    size_t total{0};
65    for (const Stripe& stripe : Stripes) {
66      std::shared_lock<std::shared_mutex> lock{ 
67        stripe.Mutex 
68      }; 
69      total += stripe.Set.GetSize();
70    }
71    return total;
72  }
73};

Our ConcurrentSwissSet is now logically partitioned into 64 stripes with reader-writer locks. However, we must check one final hardware detail: how does std::array<Stripe, 64> sit in physical memory?

Because std::array stores its elements contiguously, Stripes[0], Stripes[1], and Stripes[2] are packed back-to-back in RAM.

Because the size of Stripe is unlikely to be a clean multiple of a 64-byte CPU cache line, the end of one stripe may sit in the same 64-byte physical cache line as the beginning of the next stripe:

This creates situations where, for example, Core 0 might lock Stripes[0].Mutex, causing a write operation that invalidates the shared 64-byte cache line across all other cores. When Core 1 tries to read Stripes[1].Set.Mask from that same cache line, it suffers a cache miss.

Even though the two threads are operating on completely different stripes, they are sabotaging each other through false sharing .

Padding Stripes

To guarantee that no two stripes ever share a physical 64-byte cache line, we can add the alignas(64) specifier to our Stripe struct:

1// ...
2class ConcurrentSwissSet {
3private:
4  static constexpr size_t StripeBits{6};
5  static constexpr size_t NumStripes{1ULL << StripeBits};
6
7  // Align each stripe to a 64-byte cache line boundary
8  // to eliminate false sharing between adjacent stripes
9  struct alignas(64) Stripe { 
10    SwissSet Set;
11    mutable std::shared_mutex Mutex;
12  };
13
14  std::array<Stripe, NumStripes> Stripes;
15  // ...
16};

Marking Stripe as alignas(64) forces the compiler to pad the size of every Stripe to a multiple of 64 bytes and align the start of every Stripe to a 64-byte address boundary. Now, modifying a stripe never invalidates a single byte of a different stripe.

We're using alignas(64) here for simplicity, but 64 could be replaced with std::hardware_destructive_interference_size from #include <new>. We explain why we might want this (portability) in the dedicated false sharing lesson

Let's benchmark our ConcurrentSwissSet across multiple threads, as well as using our SwissSet directly to measure the overhead of our ConcurrentSwissSet layer.

Each container is pre-populated with 2,000,000 integers, and the worker threads execute a realistic workload of roughly 99% Contains() lookups and 1% Insert() mutations:

1#include <benchmark/benchmark.h>
2#include <vector>
3#include <random>
4#include <dsa/SwissSet.h>
5#include <dsa/ConcurrentSwissSet.h>
6
7constexpr int kInitialElements = 2'000'000;
8
9std::vector<int> GenerateInitialData() {
10  std::vector<int> data(kInitialElements);
11  std::mt19937 rng{42};
12  std::uniform_int_distribution<int> dist{1, 50'000'000};
13  for (int i{0}; i < kInitialElements; ++i) {
14    data[i] = dist(rng);
15  }
16  return data;
17}
18
19const std::vector<int> InitialData = GenerateInitialData();
20
21SwissSet* Swiss = nullptr;
22ConcurrentSwissSet* ConcurrentSwiss = nullptr;
23
24static void BM_SwissSet(benchmark::State& state) {
25  Swiss = new SwissSet();
26  for (int v : InitialData) Swiss->Insert(v);
27
28  for (auto _ : state) {
29    for (int i{0}; i < kInitialElements; ++i) {
30      int key = InitialData[i];
31      if ((i % 100) == 0) {
32        Swiss->Insert(key + 60'000'000);
33      } else {
34        benchmark::DoNotOptimize(Swiss->Contains(key));
35      }
36    }
37  }
38  delete Swiss;
39}
40
41static void BM_Concurrent(benchmark::State& state) {
42  if (state.thread_index() == 0) {
43    ConcurrentSwiss = new ConcurrentSwissSet();
44    for (int v : InitialData) ConcurrentSwiss->Insert(v);
45  }
46
47  for (auto _ : state) {
48    for (int i{0}; i < kInitialElements; ++i) {
49      int key = InitialData[i];
50      if ((i % 100) == 0) {
51        ConcurrentSwiss->Insert(key + 60'000'000);
52      } else {
53        benchmark::DoNotOptimize(
54          ConcurrentSwiss->Contains(key)
55        );
56      }
57    }
58  }
59  if (state.thread_index() == 0) delete ConcurrentSwiss;
60}
61
62BENCHMARK(BM_SwissSet)
63  ->Unit(benchmark::kMillisecond)
64  ->UseRealTime();
65
66BENCHMARK(BM_Concurrent)
67  ->Unit(benchmark::kMillisecond)
68  ->UseRealTime()
69  ->Threads(1)
70  ->Threads(2)
71  ->Threads(4)
72  ->Threads(8)
73  ->Threads(16);

1--------------------------------------------
2Benchmark                               Time
3--------------------------------------------
4BM_SwissSet/real_time                 110 ms
5BM_Concurrent/real_time/threads:1     135 ms
6BM_Concurrent/real_time/threads:2    76.8 ms
7BM_Concurrent/real_time/threads:4    37.9 ms
8BM_Concurrent/real_time/threads:8    21.7 ms
9BM_Concurrent/real_time/threads:16   15.2 ms

We can see from these tests that making our SwissSet thread-safe through the ConcurrentSwissSet wrapper adds a small performance cost.

However, as soon as we have a second thread working on our task, the concurrent implementation pulls comfortably ahead, and that advantage widens with every additional core we allocate to the work.

Here are the complete implementations of our ConcurrentSwissSet and updated SwissSet:

In this lesson, we scaled our SIMD Swiss Table across multiple CPU cores by wrapping it in a ConcurrentSwissSet.

We started by examining why lock-free CAS instructions struggle with dynamic hash table reallocations and the split structure of array writes, and built an initial ConcurrentSwissSet protected by a single global std::mutex. While thread-safe, a single lock serialized execution and triggered severe MESI cache-line invalidations across cores.

We then partitioned the container into 64 independent stripes, routing keys using the top 6 bits of Mix64() (Bits 58..63) so that stripe selection remained completely independent of H1 and H2, and passed the precalculated hash directly into SwissSet to avoid hashing keys twice.

Finally, we replaced std::mutex with std::shared_mutex so multiple readers can probe the same stripe simultaneously, and marked each Stripe with alignas(64) to eliminate false sharing across adjacent cache lines.