Memory Reclamation Methods for Lock-Free Hash Tries

Abstract

Hash tries are a trie-based data structure with nearly ideal characteristics for the implementation of hash maps. Starting from a particular lock-free hash map data structure, named Lock-Free Hash Tries (LFHT), we focus on solving the problem of memory reclamation without losing the lock-freedom property. We propose an approach that explores the characteristics of the LFHT structure in order to achieve efficient memory reclamation with low and well-defined memory bounds. Experimental results show that our approach obtains better results when compared with other state-of-the-art memory reclamation methods and provides a competitive and scalable hash map implementation, if compared to lock-based implementations.

Bibtex

@InProceedings{moreno-sbacpad19,
  author =    {P. Moreno and M. Areias and R. Rocha},
  title =     {{Memory Reclamation Methods for Lock-Free Hash Tries}},
  booktitle = {Proceedings of the International Symposium on Computer Architecture and
               High Performance Computing (SBAC-PAD 2019)}, 
  pages =     {188--195},
  publisher = {IEEE Computer Society},
  editor =    {R. Ferreira and E. Ayguade},
  month =     {October},
  year =      {2019},
  address =   {Campo Grande, Brazil},
}

Download Paper

PDF file
IEEE Computer Society