On the Implementation of Memory Reclamation Methods in a Lock-Free Hash Trie Design
Pedro Moreno, Miguel Areias and Ricardo Rocha
2021
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, we focus on solving the problem of memory reclamation without
losing the lock-freedom property. To the best of our knowledge,
outside garbage collected environments, there is no current
implementation of hash maps that is able to reclaim memory in a
lock-free manner. To achieve this goal, we propose an approach for
memory reclamation specific to Lock-Free Hash Tries that explores the
characteristics of its structure in order to achieve efficient memory
reclamation with low and well-defined memory bounds. We present and
discuss in detail the key algorithms required to easily reproduce our
implementation by others. 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
@Article{moreno-jpdc21,
author = {P. Moreno and M. Areias and R. Rocha},
title = {{On the Implementation of Memory Reclamation Methods in a Lock-Free Hash Trie Design}},
journal = {Journal of Parallel and Distributed Computing},
pages = {1--13},
volume = {155},
month = {September},
year = {2021},
}
Download Paper
PDF file
Elsevier