StackTrack: An Automated Transactional Approach to Concurrent Memory Reclamation

  • Dan Alistarh
  • Patrick Eugster
  • Maurice Herlihy
  • Alexander Matveev
  • Nir Shavit

Proceedings of Eurosys 2014 |

Published by ACM

Dynamic memory reclamation is arguably the biggest open problem in concurrent data structure design: all known solutions induce high overhead, or must be customized to the specific data structure by the programmer, or both. This paper presents StackTrack, the first concurrent memory reclamation scheme that can be applied automatically by a compiler, while maintaining efficiency. StackTrack eliminates most of the expensive bookkeeping required for memory reclamation by leveraging the power of hardware transactional memory (HTM) in a new way: it tracks thread variables dynamically, and in an atomic fashion. This effectively makes all memory references visible without having threads pay the overhead of writing out this information. Our empirical results show that this new approach matches or outperforms prior, non-automated, techniques.