Publication details

Fast, Dynamically-Sized Concurrent Hash Table

Authors

BARNAT Jiří ROČKAI Petr ŠTILL Vladimír WEISER Jiří

Type Article in Proceedings
Conference Model Checking Software
MU Faculty or unit

Faculty of Informatics

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: