  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.
