We identify a design pattern for concurrent data structures, called teleportation, that uses best- effort hardware transactional memory to speed up certain kinds of legacy concurrent data struc- tures. Teleportation unifies and explains several existing data structure designs, and it serves as the basis for novel approaches to reducing the memory traffic associated with fine-grained locking, and with hazard pointer management for memory reclamation.

State teleportation is a new technique for exploiting hardware transactional memory (HTM) to improve existing synchronization and memory management schemes for highly-concurrent data structures. When applied to fine-grained locking, a thread holding the lock for a node launches a hardware transaction that traverses multiple successor nodes, acquires the lock for the last node reached, and releases the lock on the starting node, skipping lock acquisitions for intermediate nodes. When applied to lock-free data structures, a thread visiting a node protected by a hazard pointer launches a hardware transaction that traverses multiple successor nodes, and publishes the hazard pointer only for the last node reached, skipping the memory barriers needed to publish intermediate hazard pointers. Experimental results show that these applications of state teleportation can substantially increase the performance of both lock-based and lock-free data structures.