Commit Phase Variations in Timestamp-based Software Transactional Memory

Timestamp-based Software Transactional Memory (STM) validation techniques use a global shared counter and timestamping of objects being written to reason about sequencing of transactions and their linearization points, while reducing the number of unnecessary validations that have to be performed, thus improving overall system performance. During the commit phase of a timestamp-based validation scheme, several actions have to be performed: locking of the objects being written to the memory, atomically incrementing a shared timestamp counter, updating timestamps for objects being committed to memory, performing a final validation of the transaction’s consistency, and atomically effecting the transaction’s changes to the outside world. The order and manner in which these actions are performed can affect both the correctness of the STM implementation and the overall system performance. We identify several commit sequence designs, prove their correctness, and analyze their performance. We identify cases where timestamps do not have to be unique for different transactions committing concurrently, and cases where unnecessary updates of the global shared counter — which can trigger extra vaidations in other transactions, hurting performance — can be avoided. We evaluate these commit sequence designs on a set of benchmarks on a 16 processor SunFire SMP machine. We show that a carefully chosen commit sequence can improve overall system performance by up to 14% over the current state of the art single counter timestamp-based validation techniques, and we show that it is possible to obtain high performance without incurring space overhead proportional to the number of objects in the system