Algorithms, Design, Performance

Existing Software Transactional Memory (STM) designs at-tach metadata to ranges of shared memory; subsequent run-time instructions read and update this metadata in order to ensure that an in-flight transaction’s reads and writes remain correct. The overhead of metadata manipulation and inspec-tion is linear in the number of reads and writes performed by a transaction, and involves expensive read-modify-write instructions, resulting in substantial overheads. We consider a novel approach to STM, in which trans-actions represent their read and write sets as Bloom fil-ters, and transactions commit by enqueuing a Bloom filter onto a global list. Using this approach, our RingSTM sys-tem requires at most one read-modify-write operation for any transaction, and incurs validation overhead linear not in transaction size, but in the number of concurrent writ-ers who commit. Furthermore, RingSTM is the first STM that is inherently livelock-free and privatization-safe while at the same time permitting parallel writeback by concur-rent disjoint transactions. We evaluate three variants of the RingSTM algorithm, and find that it offers superior perfor-mance and/or stronger semantics than the state-of-the-art TL2 algorithm under a number of workloads