Transactional Data Structure Programming Systems (TD-SPSs) let programmers compose method invocations on concurrent data structures into coarse-grained, isolated transactions. They detect conflicts among concurrent transactions and recover when operations do not commute.

When designing concurrent data structures (CDSs), it can feel like programmers must choose between performance and convenience. On one hand, Software Transactional Memory (STM) is easy, because it allows programmers to simply mark regions of sequential code as requiring atomicity, and then the compiler ensures that no races manifest. However, this can easily lead to false conflicts that hinder scalability. On the other hand, programmers can craft custom lock-based or non-blocking protocols for operating on the CDS. This approach increases scalability, but is hard to get right. For lock-based optimistic data structures, we identify a compelling design point that effectively unifies the two approaches. The key idea is to employ the systems concept of “separation of policy and mechanism”. This allows different operations to use the same transactional synchronization mechanism in different ways, on the same data structure, at the same time. That is, some operations can access the CDS via STM, while others use custom synchronization. We define exoTM as a synchronization mechanism extracted from a popular STM. We then introduce a high-performance exoTM-based multi-word compare-and-swap policy (STMCAS) for creating CDSs. STMCAS can checkpoint and resume read-only operations, and can run concurrently with an exoTM-based STM policy. This allows programmers to create CDSs by starting with STM and then incrementally optimizing with STMCAS until the desired performance is reached. Our experiments find that the low-level mechanisms are fast: our STMCAS-based data structures usually outperform lock-based and lock-free CDSs, at roughly the same level of effort. Furthermore, for complex CDSs (e.g., red/black trees), we can mix STMCAS and STM to keep complicated operations (re-balancing) simple while using STMCAS to optimize the common case (read-only traversal).

The Transactional Data Structure Library (TDSL) methodology improves the programmability and performance of concurrent software by making it possible for programmers to compose multiple concurrent data structure operations into coarse-grained transactions. Like transactional memory, TDSL enables arbitrarily many operations on arbitrarily many data structures to appear to other threads as a single atomic, isolated transaction. Like concurrent data structures, the individual operations on a TDSL data structure are optimized to avoid artificial contention. We introduce techniques for reducing false conflicts in TDSL implementations. Our approach allows expressing the postconditions of operations entirely via semantic properties, instead of through low-level structural properties. Our design is general enough to support lists, deques, ordered and unordered maps, and vectors. It supports richer programming interfaces than are available in existing TDSL implementations. It is also capable of precise memory management, which is necessary in low-level languages like C++.