Fast, Dynamically-Sized Concurrent Hash Table
| Authors | |
|---|---|
| Year of publication | 2015 |
| Type | Article in Proceedings |
| Conference | Model Checking Software |
| MU Faculty or unit | |
| Citation | |
| Doi | http://dx.doi.org/10.1007/978-3-319-23404-5_5 |
| Field | Informatics |
| Keywords | Data Structures; Concurrency; Hash Tables; Model Checking; DIVINE; C++ |
| Description | We present a new design and a C++ implementation of a high-performance, cache-efficient hash table suitable for use in implementation of parallel programs in shared memory. Among the main design criteria were the ability to efficiently use variable-length keys, dynamic table resizing to accommodate data sets of inpredictable size and fully concurrent read-write access. We show that the design is correct with respect to data races, both through a high-level argument, as well as by using a model checker to prove crucial safety properties of the actual implementation. Finally, we provide a number of benchmarks showing the performance characteristics of the C++ implementation, in comparison with both sequential-access and concurrent-access designs. |
| Related projects: |