--- res: bibo_abstract: - '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.@eng' bibo_authorlist: - foaf_Person: foaf_givenName: Trevor A foaf_name: Brown, Trevor A foaf_surname: Brown foaf_workInfoHomepage: http://www.librecat.org/personId=3569F0A0-F248-11E8-B48F-1D18A9856A87 - foaf_Person: foaf_givenName: William foaf_name: Sigouin, William foaf_surname: Sigouin - foaf_Person: foaf_givenName: Dan-Adrian foaf_name: Alistarh, Dan-Adrian foaf_surname: Alistarh foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0003-3650-940X bibo_doi: 10.1145/3503221.3508410 dct_date: 2022^xs_gYear dct_identifier: - UT:000883318200027 dct_isPartOf: - http://id.crossref.org/issn/9781450392044 dct_language: eng dct_publisher: Association for Computing Machinery@ dct_title: 'PathCAS: An efficient middle ground for concurrent search data structures@' ...