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 by the high overhead of existing implementations. Traditional MCAS algorithms require at least $2k+1$ compare-and-swap (CAS) instructions to update $k$ memory locations. This paper presents a new algorithm that achieves the theoretical lower bound of $k+1$ CASes in the common uncontended case. By utilizing a "lazy unlocking" strategy and integrating with epoch-based memory reclamation, the proposed algorithm (AOPT) significantly reduces the window of interference and improves throughput by up to 2.6x. Additionally, we provide a durably linearizable version for persistent memory that requires only two persistence fences per call.
Introduction
In concurrent programming, the Compare-and-Swap (CAS) instruction is the fundamental building block for lock-free data structures. While modern hardware provides atomic CAS for a single memory word, many complex data structures—such as doubly-linked lists, B-trees, and skip lists—require atomic updates to multiple disjoint memory locations to maintain consistency.
Software-based Multi-word CAS (MCAS) primitives allow developers to treat multiple updates as a single atomic unit. However, the performance cost has historically been prohibitive. Existing state-of-the-art implementations typically follow a three-phase approach: locking the target locations with descriptors, atomically changing the operation status, and then cleaning up (unlocking) those descriptors. This process usually consumes $2k+1$ or even $3k+1$ CAS instructions for a $k$-word update, creating a significant bottleneck in high-performance systems.
The Theoretical Lower Bound
A primary contribution of this research is establishing the theoretical limits of MCAS performance. Using a "bivalency" argument, the authors prove that any lock-free, disjoint-access-parallel (DAP) MCAS implementation must perform a CAS on at least $k$ different locations. This establishes that $k$ is the absolute floor for the initial phase of any MCAS operation.
Given this floor, the challenge becomes minimizing the overhead of the subsequent phases (status changes and cleanup). The authors' goal was to design an algorithm that approaches this $k$ limit as closely as possible, resulting in the $k+1$ CAS implementation.
The AOPT Algorithm: Lazy Unlocking
The core innovation of the AOPT algorithm is the concept of Lazy Unlocking. In traditional MCAS, the "cleanup" phase—where descriptors are replaced with the final values—is performed immediately to ensure subsequent readers do not have to follow pointers to metadata. This cleanup requires an additional $k$ CAS instructions.
AOPT defers this cleanup. Instead of removing descriptors immediately, the algorithm leaves them in place. The descriptors are eventually removed by:
- A background memory reclamation process.
- A subsequent operation that needs to access that specific memory location.
By moving the unlocking phase off the critical path, the latency of the MCAS call is drastically reduced. Furthermore, by integrating the algorithm with an epoch-based memory reclamation (EBR) scheme, the authors solve the "ABA problem" (where a memory location is changed and then changed back, potentially misleading a thread) without needing the expensive RDCSS (Restricted Double-Compare Single-Swap) primitive used in prior work.
Extension to Persistent Memory
The rise of non-volatile main memory (NVMM) introduces the need for durably linearizable MCAS. In these environments, data must not only be updated atomically in DRAM but also persisted to non-volatile storage using FLUSH and FENCE instructions.
Traditional persistent MCAS implementations require $2k+1$ persistence fences. Because AOPT reduces the number of critical-path CAS instructions, it also reduces the required persistence overhead. The persistent version of AOPT requires only two persistence fences per call, regardless of the number of words ($k$) being updated. This makes it exceptionally well-suited for high-performance persistent data structures.
Performance Evaluation
The authors evaluated AOPT against PMwCAS, a state-of-the-art baseline from Microsoft Research, across several benchmarks on a 40-thread Intel Xeon system:
- Array Benchmark: In random read-modify-write operations, AOPT demonstrated superior scalability and lower latency as contention increased.
- Doubly-Linked List: In a standard ordered set implementation where insertions and deletions require 2-CAS or 3-CAS operations, AOPT outperformed the baseline by 2.2x to 2.6x.
- B+tree: Using the PiBench and BzTree frameworks, AOPT showed significant throughput gains in production-quality data structures.
One of the most notable findings was the reduction in the "helping ratio." In lock-free programming, threads often have to "help" other threads finish their operations if they encounter a descriptor. Because AOPT finishes its critical path faster, the window of interference is smaller, leading to fewer threads needing to help each other and, consequently, better overall throughput.
Considerations and Trade-offs
While AOPT offers significant performance gains, it introduces a trade-off regarding read latency. Because descriptors are left in memory, a subsequent read operation might encounter a descriptor and be forced to follow a pointer to the operation's metadata to find the current value.
In purely read-heavy workloads with zero contention, this extra indirection can cause a slight performance dip. However, the evaluation shows that in almost all practical scenarios—especially those with any degree of contention—the gains from reducing the number of CAS instructions far outweigh the cost of the occasional extra pointer dereference. Additionally, memory pressure can be managed by tuning the frequency of the epoch-based reclamation to ensure descriptors do not accumulate excessively.
Conclusion
By reducing the complexity of Multi-word CAS from $2k+1$ to $k+1$ CASes, this work provides a highly efficient primitive for concurrent programming. The AOPT algorithm demonstrates that by rethinking the necessity of immediate cleanup and leveraging modern memory reclamation techniques, we can reach the theoretical limits of atomic multi-word updates in both volatile and persistent memory environments.
Summary updated