Memory Reclamation Methods for Lock-Free Hash Tries
Pedro Moreno, Miguel Areias and Ricardo Rocha
October 2019
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