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

• Tipo: Artigo em Revista Científica Internacional
• Data: 2025

Autores

Moreno, P (Autor) Outra; Miguel Areias (Autor) FCUP; Ricardo Rocha (Autor) FCUP

Revista

Título: Parallel Computing

Vol. 126

ISSN: 0167-8191

Editora: Elsevier

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 12