Brief Announcement: Faster Data Structures in Transactional Memory using Three Paths

With the introduction of Intel’s restricted hardware transactional memory (HTM) in commodity hardware, the transactional memory abstraction has fi-nally become practical to use. Transactional memory allows a programmer to easily implement safe concurrent code by specifying that certain blocks of code should be executed atomically. However, Intel’s HTM implementation does not offer any progress guarantees. Even in a single threaded system, a transaction can repeatedly fail for complex reasons. Consequently, any code that uses HTM must also provide a non-transactional fallback path to be executed if a trans-action fails. Since the primary goal of HTM is to simplify the task of writing concurrent code, a typical fallback path simply acquires a global lock, and then runs the same code as the transaction. This is essentially transactional lock eli-sion (TLE). Changes made by a process on the fallback path are not atomic, so transactions that run concurrently with a process on the fallback path may see inconsistent state. Thus, at the beginning of each transaction, a process reads the state of the global lock and aborts the transaction if it is held