Big Atomics and Fast Hash Tables

In this work, we present theoretically and practically efficient implementations of Big Atomics, i.e., k-word linearizable registers that support the load, store, and compare-and-swap (CAS) operations. While modern hardware supports k = 1 and sometimes k = 2 (e.g., double-width compare-and-swap in x86), our implementations support arbitrary k. Big Atomics are useful in many applications, including atomic manipulation of tuples, version lists, and implementing load-linked/store-conditional (LL/SC). We design fast, lock-free implementations of big atomics based on a novel fast-path-slow-path approach we develop. We then use them to develop an efficient concurrent hash table, as evidence of their utility.