A sleek lock-free hash map in an ERA of safe memory reclamation methods

• Type: Article in International Scientific Journal
• Date: 2025

Authors

Moreno, P (Author) Other; Miguel Areias (Author) FCUP; Ricardo Rocha (Author) FCUP

Journal

Title: Parallel Computing

Vol. 126

ISSN: 0167-8191

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 0 Citations

Other information

Authenticus ID: P-01A-DR5

DOI: 10.1016/j.parco.2025.103162

Abstract (EN): Lock-free data structures have become increasingly significant due to their algorithmic advantages in multi-core cache-based architectures. Safe Memory Reclamation (SMR) is a technique used in concurrent programming to ensure that memory can be safely reclaimed without causing data corruption, dangling pointers, or access to freed memory. The ERA theorem states that any SMR method for concurrent data structures can only provide at most two of the three main desirable properties: Ease of use, Robustness, and Applicability. This fundamental trade-off influences the design of efficient lock-free data structures at an early stage. This work redesigns a previous lock-free hash map to fully exploit the properties of the ERA theorem and to leverage the characteristics of multi-core cache-based architectures by minimizing the number of cache misses, which are a significant bottleneck in multi-core environments. Experimental results show that our design outperforms the previous design, which was already quite competitive when compared against the Concurrent Hash Map design of the Intel's TBB library.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 12