Memory Reclamation for an Elastic Lock-Free Hash Trie Map Design Using Hazard Pointers

João Chamiça Pereira, Pedro Moreno and Ricardo Rocha

September 2022

---

Abstract

A hash map is elastic if it can expand and compress. Hash maps expand in order to reduce collisions and compress in order to reduce depth and memory usage. Starting from a particular elastic lock-free hash map design, which implements expansion and compression in constant time while maintaining the high throughput of lock-freedom, we focus on solving the problem of memory reclamation outside garbage collected environments without losing the lock-freedom property. We propose a lock-free and safe memory reclamation method using hazard pointers that is compatible with the compression mechanism of this data structure. Experiments show that our approach obtains results on par with the best state-of-the-art memory reclamation methods, both in execution time and memory footprint.

Bibtex

@InProceedings{pereira-inforum22,
  author =    {J. C. Pereira and P. Moreno and R. Rocha},
  title =     {{Memory Reclamation for an Elastic Lock-Free Hash Trie Map Design Using Hazard Pointers}},
  booktitle = {13th INForum - Simpósio de Informática (INForum 2022)},
  editor =    {M. Freire and M. Pato},
  month =     {September},
  year =      {2022},
  address =   {Guarda, Portugal},
}

Download Paper

PDF file