Skip to main content
Be Bitwise
C++Concurrency in C++

Capstone: Concurrent Data Structures

This capstone walks you through two concurrent data structures: a thread-safe hashmap with fine-grained locking and a lock-free stack. They're the bricks under most high-performance concurrent systems.

Part 1: Thread-Safe HashMap

The naive design slaps one mutex on the whole map. Every access serializes, and concurrency dies in its sleep. The fix is striped locking: split the map into buckets, give each its own mutex. Threads hitting different buckets sail past each other.

cpp
#include <array>
#include <vector>
#include <list>
#include <shared_mutex>
#include <optional>
#include <functional>
#include <iostream>
#include <thread>
template <typename K, typename V, size_t NumStripes = 16>
class ConcurrentHashMap {
struct Entry {
K key;
V value;
};
struct Stripe {
std::list<Entry> entries;
mutable std::shared_mutex mutex;
};
std::array<Stripe, NumStripes> stripes_;
size_t stripe_index(const K& key) const {
return std::hash<K>{}(key) % NumStripes;
}
public:
void insert(const K& key, const V& value) {
auto& stripe = stripes_[stripe_index(key)];
std::unique_lock lock(stripe.mutex);
for (auto& entry : stripe.entries) {
if (entry.key == key) {
entry.value = value;
return;
}
}
stripe.entries.push_back({key, value});
}
std::optional<V> get(const K& key) const {
auto& stripe = stripes_[stripe_index(key)];
std::shared_lock lock(stripe.mutex);
for (const auto& entry : stripe.entries) {
if (entry.key == key) {
return entry.value;
}
}
return std::nullopt;
}
bool remove(const K& key) {
auto& stripe = stripes_[stripe_index(key)];
std::unique_lock lock(stripe.mutex);
for (auto it = stripe.entries.begin(); it != stripe.entries.end(); ++it) {
if (it->key == key) {
stripe.entries.erase(it);
return true;
}
}
return false;
}
size_t size() const {
size_t total = 0;
for (const auto& stripe : stripes_) {
std::shared_lock lock(stripe.mutex);
total += stripe.entries.size();
}
return total;
}
};
Key Concept

Striped locking spreads entries across independent locks to defuse contention. With 16 stripes and a roughly uniform key distribution, two threads colliding on the same lock drops to a 1-in-16 chance. Java's ConcurrentHashMap used exactly this design (16 segments by default) up to Java 7; Java 8 went finer still, locking individual bins.

Testing the HashMap

cpp
void test_concurrent_hashmap() {
ConcurrentHashMap<std::string, int> map;
// Writer threads
std::vector<std::thread> writers;
for (int i = 0; i < 4; i++) {
writers.emplace_back([&map, i]() {
for (int j = 0; j < 1000; j++) {
std::string key = "key_" + std::to_string(i * 1000 + j);
map.insert(key, i * 1000 + j);
}
});
}
for (auto& t : writers) t.join();
std::cout << "Map size: " << map.size() << "\n"; // 4000
// Reader threads
std::vector<std::thread> readers;
std::atomic<int> found{0};
for (int i = 0; i < 4; i++) {
readers.emplace_back([&map, &found, i]() {
for (int j = 0; j < 1000; j++) {
std::string key = "key_" + std::to_string(i * 1000 + j);
if (map.get(key).has_value()) {
found.fetch_add(1, std::memory_order_relaxed);
}
}
});
}
for (auto& t : readers) t.join();
std::cout << "Found: " << found.load() << "\n"; // 4000
}

Part 2: Lock-Free Stack

A lock-free stack swaps locks for compare-and-swap on the head pointer:

cpp
#include <atomic>
#include <memory>
#include <optional>
template <typename T>
class LockFreeStack {
struct Node {
T data;
Node* next;
Node(T val) : data(std::move(val)), next(nullptr) {}
};
std::atomic<Node*> head_{nullptr};
std::atomic<size_t> size_{0};
public:
void push(T value) {
Node* new_node = new Node(std::move(value));
new_node->next = head_.load(std::memory_order_relaxed);
while (!head_.compare_exchange_weak(
new_node->next, new_node,
std::memory_order_release,
std::memory_order_relaxed)) {
// CAS failed; new_node->next updated to current head
}
size_.fetch_add(1, std::memory_order_relaxed);
}
std::optional<T> pop() {
Node* old_head = head_.load(std::memory_order_acquire);
while (old_head != nullptr) {
// acquire on both paths: a failed CAS reloads old_head, and we're
// about to read old_head->next, which another thread's push wrote
if (head_.compare_exchange_weak(
old_head, old_head->next,
std::memory_order_acquire,
std::memory_order_acquire)) {
T value = std::move(old_head->data);
delete old_head;
size_.fetch_sub(1, std::memory_order_relaxed);
return value;
}
// CAS failed; old_head updated to current head
}
return std::nullopt; // Empty
}
size_t size() const {
return size_.load(std::memory_order_relaxed);
}
~LockFreeStack() {
while (pop().has_value()) {}
}
};

Memory Reclamation Challenge

There's a subtle hole in the stack above. In pop(), between the load of old_head and the CAS, another thread could pop and delete old_head. The next access to old_head->next reads freed memory.

On x86 this often appears to work, because freed memory isn't reclaimed instantly. On other architectures or under load, it crashes.

Freeing isn't the only danger. If a popped node's memory gets reused for a later push, a stale CAS can succeed when it should fail: the ABA problem from the previous lesson. You can't schedule real threads in the runner, but you can replay the exact interleaving on one thread. Predict what the stack looks like at the end.

Try itB was popped by thread 2, yet it ends up back on top. Make thread 2 push a brand-new node D instead of reusing A and thread 1's CAS fails, as it should.
C++ (GCC 9.2.0)

Solutions include:

Hazard Pointers: the sketch below shows only the reader's side. For the scheme to work, each thread's hazard pointer has to sit in a shared registry that other threads can scan (a thread_local on its own is invisible to them), retire has to free a node only once no hazard pointer names it, and a real pop retries a failed CAS instead of giving up.

cpp
// Each thread publishes the pointer it is about to access
thread_local Node* hazard_ptr = nullptr;
std::optional<T> safe_pop() {
Node* old_head;
do {
old_head = head_.load();
hazard_ptr = old_head;
// Re-check: if head changed, our hazard ptr protects the wrong node
} while (old_head != head_.load());
if (!old_head) return std::nullopt;
if (head_.compare_exchange_strong(old_head, old_head->next)) {
T value = std::move(old_head->data);
hazard_ptr = nullptr;
// Defer deletion until no hazard pointers reference old_head
retire(old_head);
return value;
}
hazard_ptr = nullptr;
return std::nullopt;
}

Performance Comparison

This harness times the lock-free stack under contention and then runs the hashmap test. One number on its own tells you little, so for a real comparison put a std::stack behind a single std::mutex through the same loop and time that too. Also keep in mind that this stack still deletes nodes other threads may be reading, so a crash here is the reclamation bug above rather than bad luck.

cpp
#include <chrono>
template <typename Func>
long long benchmark(const std::string& name, Func f) {
auto start = std::chrono::high_resolution_clock::now();
f();
auto end = std::chrono::high_resolution_clock::now();
auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
std::cout << name << ": " << ms.count() << "ms\n";
return ms.count();
}
int main() {
benchmark("Lock-free stack", []() {
LockFreeStack<int> stack;
std::vector<std::thread> threads;
for (int i = 0; i < 8; i++) {
threads.emplace_back([&stack]() {
for (int j = 0; j < 100000; j++) {
stack.push(j);
stack.pop();
}
});
}
for (auto& t : threads) t.join();
});
test_concurrent_hashmap();
return 0;
}

What You Built

These two structures showcase the two main concurrency strategies:

  1. Fine-grained locking (hashmap): independent locks cut contention while you keep all the familiar lock-based reasoning.
  2. Lock-free algorithms (stack): CAS dodges locks entirely, but now you owe attention to memory ordering and reclamation.

In practice, fine-grained locking wins most of the time. Lock-free structures are reserved for the hottest paths, the ones where contention has been measured, profiled, and proven to be the bottleneck.