An Efficient Software Transactional Memory Using Commit-Time Invalidation

To improve the performance of transactional memory (TM), re-searchers have found many eager and lazy optimizations for conflict detection, the process of determining if transactions can commit. Despite these optimizations, nearly all TMs perform one aspect of lazy conflict detection in the same manner to preserve serializabil-ity. That is, they perform commit-time validation, where a transac-tion is checked for conflicts with previously committed transactions during its commit phase. While commit-time validation is efficient for workloads that exhibit limited contention, it can limit transac-tion throughput for contending workloads. This paper presents an efficient implementation of commit-time invalidation, a strategy where transactions resolve their con-flicts with in-flight (uncommitted) transactions before they commit. Commit-time invalidation supplies the contention manager (CM) with data that is unavailable through commit-time validation, al-lowing the CM to make decisions that increase transaction through-put. Commit-time invalidation also requires notably fewer opera-tions than commit-time validation for memory-intensive transac-tions, uses zero commit-time operations for dynamically detected read-only transactions, and guarantees full opacity for any transac-tion in O(N) time, an improvement over incremental validation’s O(N2) time. Our experimental results show that for contending workloads, our efficient commit-time invalidating software TM (STM) is up to 3 ⇥ faster than TL2, a state-of-the-art validating STM