After taking my favourite Imperial module thus far, The Theory and Practice of Concurrent Programming, last year, I decided to revisit some of the content and implement a lock-free hash set as described in the textbook The Art of Multiprocessor Programming by Herlihy and Shavit, and implement epoch-based reclamation (not in the book). I also wrote three other implementations during the course, with varying degrees of lock granularity:

These were benchmarked against two existing implementations, Intel oneTBB and libcds. There were 10 different scenarios representing different types of workloads (mixes of Add/Contains/Remove operations, number of keys, capacities).

The full details of the experiments can be found in the repo’s README. I encourage you to read that, as I only repeat the results here, without the discussion. Instead, I discuss some of the theoretical and implementation-related challenges below.

Results

Compared to oneTBB, my lock-free hash set wins 8/10 workloads, operating up to 2.74x faster. Compared to libcds, it wins 10/10 workloads, up to 5.47x faster.

Challenges

Initially, it was difficult to understand how the split-ordered list algorithm worked for the lock-free set. However, once I understood that, it was fairly straightforward to implement — at least for the first version, which had massive memory leaks!

The book’s implementation is simplified compared to C++ because it is written in Java¹, which has garbage collection. The problem with concurrent data structures in non-GC languages like C++ is that reclaiming memory becomes a nightmare due to the ABA problem.

Here’s an example. Imagine a concurrent stack being used by two threads, with nodes A, B and C from top to bottom. Thread 1 wants to pop A, and reads the top pointer and its next pointer, preparing to do an atomic compare-and-swap (CAS) with them. Before that happens, Thread 2 pre-empts and successfully pops A and B, frees B then pushes A again. Finally, Thread 1 is woken — it attempts the CAS, which succeeds, because the top pointer matches the expected value (A), and so the top pointer then points at B. If the top pointer is dereferenced, a use-after-free will occur.

To resolve this problem, safe memory reclamation techniques are used. They ensure that unlinked nodes are not freed until safe to do so. There are several prominent methods: hazard pointers, read-copy-update — both now part of C++ in C++26 — and epoch-based reclamation (EBR), which is what I implemented.

Epoch-based reclamation

Epoch-based reclamation involves storing garbage temporarily until it can be guaranteed that no thread has access to it anymore. There is a global epoch counter that represents time periods. Each thread has a local counter, which the thread updates to the current global counter before it does any operation.

Because of this, if a node was deleted and is ready to be reclaimed — i.e. was retired — at epoch e, then by epoch e + 2 it is guaranteed that no node can still be referencing it, and the thread that stores the node frees it when it begins the next operation.

Once a certain thread has retired some fixed amount of nodes, it attempts to advance the global counter. To do this, it has to ensure that all the active threads have announced they are at (or past) the current epoch, then it can atomically increment it. Because of this property, each thread’s local counter lags at most 1 epoch behind the global counter.

After a thread completes a set operation, the thread marks its counter as “inactive”, so that it is ignored for the advancement process and thus doesn’t block it. This introduces a vulnerability where a single thread stalling while inside an active operation can cause unbounded memory accumulation, as no memory can be reclaimed until the epoch can be advanced.

That issue is the primary drawback of EBR, but also what allows it to be faster than other methods like hazard pointers (which don’t have this problem). As it simply tracks periods of time rather than individual pointers, the hot path (reading / traversing data) has very little overhead indeed.

The implementation itself was difficult. It turns out to be much more complicated than it seems at first — what isn’t in concurrent programming? If you instantiate multiple sets (each with their own reclaimers) there are still a fixed number of threads operating across them. So each thread must store its own local epoch (and other state) for each set it touches. To overcome this, there is a Participant structure, of which one instance exists per-thread per-set. I won’t dive any further into the details about it here, but feel free to look at the source code if you feel prepared. Also note that I didn’t benchmark the case where you have multiple sets, but it would definitely be something interesting to do in the future, to quantify just how much latency it adds.

After implementing it, the memory usage on the removal-heavy scenarios dropped drastically, from 248 MB in one example to a maximum of 14 MB, and I verified there were no leaks using AddressSanitizer.