Abstract nested transactions

TM implementations typically use low-level conflict detection based on the memory locations that a transaction accesses. This can cause transactions to be re-executed because of benign conflicts, for example if two transactions insert items into the same hashtable under different keys which happen to hash to the same bucket: the insertions update the same memory locations, even though the higher-level operations they are performing are commutative. In this paper we introduce abstract nested transactions (ANTs) as a way of improving the scalability of atomic blocks that experience some kinds of benign conflict. The main idea is that ANTs should contain operations that are likely to be the victims of benign conflicts. The run-time system then performs extra book-keeping so that, if an ANT does experience a conflict, the ANT can be re-executed without needing to re-run the larger transaction that contains it. Unlike closed nested transactions (CNTs) this re-execution can happen after the ANT has finished running – in our implementation we only re-execute ANTs at the point that we try to commit a top-level atomic block. Moving code into or out of an ANT is semantics preserving: ANTs affect only the program’s performance, not its possible results. This helps open the door for future research in automatic ways to place ANTs in programs in order to deal with contention ‘hot spots’ that they experience.