Memory Reclamation for an Elastic Lock-free Hash Trie Map

João Pereira

November 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, called the lock-free hash trie map, 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, in execution time. On the other hand, our proposed method is capable of maintaining lower memory consumption than the alternative methods.

Bibtex

@MastersThesis{pereira-msc,
  author =  {J. Pereira},
  title =   {{Memory Reclamation for an Elastic Lock-free Hash Trie Map}},
  school =  {University of Porto},
  address = {Portugal},
  month =   {November},
  year =    {2022},
  type =    {{MSc Thesis}},
}

Download Thesis

PDF file