Concurrent Hash Tables
| Autor: | Peter Sanders, Tobias Maier, Roman Dementiev |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
D.1.3 E.2 Computer science Linear probing Hash function 020207 software engineering 02 engineering and technology Parallel computing Data structure Hash table Computer Science Applications Computational Theory and Mathematics Hardware and Architecture 020204 information systems Modeling and Simulation Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Overhead (computing) Data Structures and Algorithms (cs.DS) E.1 Software |
| Zdroj: | ACM Transactions on Parallel Computing. 5:1-32 |
| ISSN: | 2329-4957 2329-4949 |
| DOI: | 10.1145/3309206 |
| Popis: | Concurrent hash tables are one of the most important concurrent data structures, which are used in numerous applications. For some applications, it is common that hash table accesses dominate the execution time. To efficiently solve these problems in parallel, we need implementations that achieve speedups in highly concurrent scenarios. Unfortunately, currently available concurrent hashing libraries are far away from this requirement, in particular, when adaptively sized tables are necessary or contention on some elements occurs. Our starting point for better performing data structures is a fast and simple lock-free concurrent hash table based on linear probing that is, however, limited to word-sized key-value types and does not support dynamic size adaptation. We explain how to lift these limitations in a provably scalable way and demonstrate that dynamic growing has a performance overhead comparable to the same generalization in sequential hash tables. We perform extensive experiments comparing the performance of our implementations with six of the most widely used concurrent hash tables. Ours are considerably faster than the best algorithms with similar restrictions and an order of magnitude faster than the best more general tables. In some extreme cases, the difference even approaches four orders of magnitude. All our implementations discussed in this publication can be found on github [17]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|