Efficient Multi-Word Compare and Swap

Rachid Guerraoui, Alex Kogan, Virendra J. Marathe, Igor Zablotchi

TL;DR

Multi-word Compare-and-Swap (MCAS) makes concurrent programming simpler, but historical lock-free implementations have been throttled by requiring $2k + 1$ to $4k$ hardware CAS instructions per $k$-word update. This paper proves a theoretical lower bound of at least $k$ CAS operations and introduces the first lock-free algorithm achieving just $k + 1$ CASes in uncontended execution, along with a persistent memory extension needing only 2 persistence fences.

What Problem Does This Paper Address?

Hardware typically provides atomic compare-and-swap (CAS) for a single memory word. However, coordinating updates across multiple disjoint memory words atomically (e.g., node insertions or splits in concurrent search trees) requires multi-word compare-and-swap (MCAS).

Existing lock-free MCAS algorithms suffer from substantial overhead because they execute multiple costly atomic instructions per word. Traditional three-phase MCAS schemes (locking target words via descriptors, updating a status flag, and unlocking targets back to raw values) usually require between $2k + 1$ and $4k$ CASes for a $k$-word update. This cost compounds further on non-volatile, persistent memory (PM), where memory flushes and ordering fences stall CPU execution.

Methods

The authors design an algorithm based on an unexpected architectural realization: defer the unlocking/cleanup phase off the critical path.

  1. Lazy Descriptors and Off-Path Cleanup:
  2. Instead of immediately clearing installed operation descriptors after status finalization, descriptors are left in place. Target memory words are only updated ("detached") lazily—either when an incoming MCAS overwrites them or during epoch-based descriptor reclamation.
  3. Removing immediate unlocking eliminates $k$ CASes from the critical path.
  4. ABA Prevention "For Free":
  5. Prior approaches (like Harris et al.) rely on specialized double-compare single-swap (RDCSS) primitives to prevent ABA races during acquisition, costing an extra $k$ CASes.
  6. By pairing deferred detachment with standard epoch-based memory reclamation (similar to RCU), the authors achieve ABA safety naturally without needing RDCSS.
  7. Execution Complexity:
  8. In the common uncontended case, the algorithm requires only $k + 1$ CASes ($k$ acquisitions + 1 status update) and standard reads perform zero shared-memory writes.
  9. Persistent Memory Extension (PMCAS):
  10. Guarantees durable linearizability with only 2 persistence fences and $k$ asynchronous flushes in the common case, coordinating recovery states via a single descriptor-level DirtyFlag.

Datasets

The paper evaluates system throughput and helping overheads using synthetic and structural microbenchmarks rather than static machine learning datasets:

  • Random Array Benchmark: Threads execute read-modify-write loops across random subsets of an array ($k = 4$) under varying array sizes (10, 100, and 1,000 words).
  • Ordered Doubly-Linked List: Nodes inserted via 2-CAS and deleted via 3-CAS (initial sizes: 5, 50, and 500 nodes).
  • PiBench / BzTree Benchmark: A production-grade latch-free $B^+$-tree indexing workload evaluated under varying tree sizes (16, 512, and 4,000,000 elements).

Key Insights and Ideas

  • Impossibility Proof (Lower Bound): Using a bivalency argument over a "star configuration" of conflicting operations, the authors prove that any lock-free, disjoint-access-parallel (DAP) $k$-CAS implementation must perform a CAS on at least $k$ distinct locations. Compressing or "packing" coordination into fewer than $k$ locations without breaking linearizability is impossible.
  • The Detachment Phase is Nearly Free in Practice: The empirical detaching ratio (the number of explicit cleanup CASes needed during reclamation per MCAS) was $< 0.001$. In active workloads, subsequent MCAS operations naturally overwrite older descriptors, virtually eliminating explicit unlocking costs.
  • Fewer CASes Mean Shorter Vulnerability Windows: Because an operation finishes in $k + 1$ steps instead of $3k + 1$, the temporal window in which concurrent threads collide and must stop to "help" an incomplete descriptor shrinks dramatically.

Key Results

  • Throughput Gains under Contention:
  • In the doubly-linked list benchmark (80% reads, 20% updates), the proposed algorithm outperformed the state-of-the-art baseline (PMwCAS) by $2.6\times$ on small lists (high contention) and $2.2\times$ on medium lists.
  • In the $B^+$-Tree benchmark, it consistently achieved higher throughput under medium and high contention across thread counts ranging up to 39 threads.
  • Helping Overhead: The helping ratio dropped significantly across all contended workloads, confirming that threads spent less time stalled resolving other operations' states.
  • Persistent Performance Efficiency: Prior persistent implementations required $5k + 1$ CASes and $2k + 1$ fences; this construction achieves persistence using $k + 1$ CASes and only 2 fences.

Limitations and Future Work

  • Read Indirection Overhead: Because descriptors remain in memory addresses after an operation completes, reader threads encounter an extra pointer indirection when inspecting values. In very low contention scenarios with large workloads (e.g., list size 500 at low thread counts), baseline PMwCAS outperformed this algorithm by roughly $1.2\times$ because PMwCAS leaves clean direct values in place.
  • Memory Footprint: Deferring cleanup shifts descriptor retirement into an epoch-based memory reclamation pipeline, demanding tuning between memory footprint and reclamation frequency.

Summary updated

Abstract

Atomic lock-free multi-word compare-and-swap (MCAS) is a powerful tool for designing concurrent algorithms. Yet, its widespread usage has been limited because lock-free implementations of MCAS make heavy use of expensive compare-and-swap (CAS) instructions. Existing MCAS implementations indeed use at least 2k+1 CASes per k-CAS. This leads to the natural desire to minimize the number of CASes required to implement MCAS. We first prove in this paper that it is impossible to "pack" the information required to perform a k-word CAS (k-CAS) in less than k locations to be CASed. Then we present the first algorithm that requires k+1 CASes per call to k-CAS in the common uncontended case. We implement our algorithm and show that it outperforms a state-of-the-art baseline in a variety of benchmarks in most considered workloads. We also present a durably linearizable (persistent memory friendly) version of our MCAS algorithm using only 2 persistence fences per call, while still only requiring k+1 CASes per k-CAS.
BibTeX
@inproceedings{guerraoui2020efficient,
  author = {Rachid Guerraoui and Alex Kogan and Virendra J. Marathe and Igor Zablotchi},
  title = {{Efficient Multi-Word Compare and Swap}},
  booktitle = {DISC},
  year = {2020},
  url = {https://openreview.net/forum?id=4y62A9Sn4P},
}

Loading related content...

Figure