A deep dive into making MSI (Mask-Step-Index) hash tables safe for concurrent access without locks. Starting from a single-threaded integer hash set, the post progressively adds atomic operations to handle single-producer/multiple-consumer (SPMC) and multiple-producer/multiple-consumer (MPMC) scenarios. It covers relaxed atomics for out-of-order integer sets, acquire-release semantics for pointer-based tables where object initialization must be visible before the pointer is observed, and compare-and-swap for lock-free multi-producer insertion. GCC atomic builtins are used throughout, avoiding the need for _Atomic qualifiers and allowing asymmetric atomicity between producer and consumer paths.
Table of contents
Multiple producersQuestions this post answers
How do I make an MSI hash table safe for concurrent reads and writes in C without locks?
Use GCC atomic builtins asymmetrically: consumers use __atomic_load_n with __ATOMIC_ACQUIRE, while a single producer uses __atomic_store_n with __ATOMIC_RELEASE. For multiple producers, add a compare-and-swap (__atomic_compare_exchange_n) with RELEASE on success and ACQUIRE on failure, so the losing thread acquires the winning element and continues probing. No _Atomic qualifiers are needed, and on x86 this often generates identical code to the single-threaded version. Developers building concurrent data structures in C find related low-level patterns discussed on daily.dev.
When should I use relaxed vs acquire-release atomics in a concurrent hash table?
Use relaxed atomics (__ATOMIC_RELAXED) when consumers tolerate out-of-order insertions and keys carry no associated data — for example, a plain integer hash set. Upgrade to acquire-release when keys are pointers to objects that must be fully initialized before consumers observe them: the release store ensures all prior writes to the object are visible after the consumer's acquire load. Engineers choosing between memory orderings for concurrent C code track these trade-offs on daily.dev.