An Innovative Approach to Achieve Compositionality Efficiently Using Multi-version Object Based Transactional Systems

The rise of multi-core systems has necessitated the need for concurrent programming. However, developing correct, efficient concurrent programs is notoriously difficult. Software Transactional Memory Systems (STMs) are a convenient programming interface for a programmer to access shared memory without worrying about concurrency issues. Another advantage of STMs is that they facilitate compositionality of concurrent programs with great ease. Different concurrent operations that need to be composed to form a single atomic unit is achieved by encapsulating them in a single transaction. Most of the STMs proposed in the literature are based on read/write primitive operations on memory buffers. We denote them as Read-Write STMs or RWSTMs. On the other hand, there have been some STMs that have been proposed (transactional boosting and its variants) that work on higher level operations such as hash-table insert, delete, lookup, etc. We call them Object STMs or OSTMs. It was observed in databases that storing multiple versions in RWSTMs provides greater concurrency. In this paper, we combine both these ideas for harnessing greater concurrency in STMs - multiple versions with objects semantics. We propose the notion of Multi-version Object STMs or MVOSTMs. Specifically, we introduce and implement MVOSTM for the hash-table object, denoted as HTMVOSTM and list object, list-MVOSTM. These objects export insert, delete and lookup methods within the transactional framework. We also show that both these MVOSTMs satisfy opacity and ensure that transaction with lookup only methods do not abort if unbounded versions are used. Experimental results show that list-MVOSTM outperform almost two to twenty fold speedup than existing state-of-the-art list based STMs (Trans-list, Boosting-list, NOrec-list, list-MVTO, and list-OSTM). Similarly, HT-MVOSTM shows a significant performance gain of almost two to nineteen times over the existing state-of-the-art hash-table based STMs (ESTM, RWSTMs, HT-MVTO, and HT-OSTM)