Evaluation of Transactional Memory
Elastic Transactions
ε-STM is the first software transactional memory supporting elastic transactions. Elastic transactions are a variant of the transactional model. Upon conflict detection, an elastic transaction might drop what it did so far within a separate transaction that immediately commits, and initiate a new transaction which might itself be elastic.
Synchrobench
Synchrobench is a micro-benchmark suite to compare STMs with existing lock-free and lock-based counterparts. The current version includes five kinds of data structure implementations: binary search trees, double-ended queue, linked list, skip list and hash table.
Microbench includes the implementation of several algorithms:
- Transaction-based Binary Tree: A Speculation-Friendly Binary Search Tree. Tyler Crain, Vincent Gramoli and Michel Raynal. Proc. of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2012
- Lock-free Linked List: A Pragmatic Implementation of Non-Blocking Linked Lists. Tim Harris. Proc. of the 15th Int'l Symposium on Distributed Computing (DISC) p. 300-314, 2001
- Lock-based Linked List: A Lazy Concurrent List-Based Set Algorithm. Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III and Nir Shavit. Proc. of the 9th Int'l Conf. on Principles of Dist. Systems (OPODIS) p.3-16, 2005
- Lock-free Skip List: Practical Lock Freedom. Keir Fraser. PhD dissertation, September 2003 Cambridge University Technical Report UCAM-CL-TR-579
- Lock-based Skip List A Simple Optimistic Skiplist Algorithm. Maurice Herlihy, Yossi Lev, Victor Luchangco, Nir Shavit. Proc. of the 14th Int'l Colloquim on Structural Information and Communication Complexity (SIROCCO) p.124-138, 2007