uSTM: A Lightweight and Efficient STM Supporting General Types and Deferred Aborts

Software Transactional Memory (STM) systems allow developers to more easily exploit multicore architectures by wrapping arbitrary sequential code in transactions that are executed concurrently. In recent years, the performance of STM systems has approached that of hand-tuned data structures through techniques that avoid unnecessary aborts and exploit the semantics of underlying data structures. Despite achieving excellent performance, most STM systems do not fully address the concerns they targeted in the first place: safety, usability, and generality. In particular, these systems place restrictions on the data types that may be updated transactionally, such as requiring that these types fit within a word, and can require modification of data layout. Moreover, most STM systems abort transactions in the middle of client code to ensure correctness. This can cause space leaks and other bugs not present in the original code. We present μSTM, a novel STM system addressing all of these shortcomings while still maintaining excellent performance, all within ~300 lines of code. μSTM supports general types while maintaining data layout. Aborts are deferred until the end of the transaction, allowing client code within a transaction to terminate normally. To ensure that μSTM guarantees opacity, we implement a novel timestamping algorithm we call split-increment timestamps. We compare the performance of μSTM to a variety of state-of-the-art (SOTA) STM systems, demonstrating that μSTM matches or outperforms the SOTA on a variety of workloads.