  To maximize the performance of concurrent data structures, researchers have
often turned to highly complex fine-grained techniques, resulting in efficient
and elegant algorithms, which can however be often difficult to understand and
prove correct. While simpler techniques exist, such as transactional memory,
they can have limited performance or portability relative to their fine-grained
counterparts. Approaches at both ends of this complexity-performance spectrum
have been extensively explored, but relatively less is known about the middle
ground: approaches that are willing to sacrifice some performance for
simplicity, while remaining competitive with state-of-the-art handcrafted
designs.
  In this paper, we explore this middle ground, and present PathCAS, a
primitive that combines ideas from multi-word CAS (KCAS) and transactional
memory approaches, while carefully avoiding overhead. We show how PathCAS can
be used to implement efficient search data structures relatively simply, using
an internal binary search tree as an example, then extending this to an AVL
tree. Our best implementations outperform many handcrafted search trees: in
search-heavy workloads, it rivals the BCCO tree [5], the fastest known
concurrent binary tree in terms of search performance [3]. Our results suggest
that PathCAS can yield concurrent data structures that are relatively easy to
build and prove correct, while offering surprisingly high performance.
