Optimistic Transactional Lazy Set
Transactional data structures with the same performance of highly concurrent data structures enable performance-competitive transactional applications. Although Software Transactional Memory (STM) is a promising technology for designing and implementing transactional applications, STM-based transactional data structures still perform inferior to their optimized, concurrent (i.e. non-transactional) counterparts. In this work, we present OTB-Set, an efficient optimistic transactional lazy set based on both linked-list and skip-list implementations. We first provide general guidelines to show how to design a transactional (non-optimized) version of the highly concurrent lazy set with a minimal reengineering effort. Subsequently, we show how to make specific optimizations to the implementations of the OTB-Set for further enhancing its performance. We also prove that our OTB-Set provides linearizable individual operations and opaque transactions. Our experimental study on a 64-core machine reveals that OTB-Set outperforms competitors in most workloads.
Ahmed Hassan, Roberto Palmieri and Binoy Ravindran
Optimistic Transactional Boosting MethodologyShort paper, PPoPP 2014
Optimistic Transactional Lazy SetOPODIS 2014
Source CodeDownload source code of OTB-Set, examples and test-scripts used for experimental evaluation.