Memory Reclamation Methods for Lock-Free Hash Tries

• Pedro Moreno University of Porto
• Miguel Areias University of Porto
• Ricardo Rocha University of Porto

Resumo

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.

Palavras-chave: Data structures, Instruction sets, Hazards, Message systems, Memory management, Indexes, Synchronization, Memory Reclamation, Lock-Freedom, Hash Maps, Hazard Pointers