Fast, Dynamically-Sized Concurrent Hash Table

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

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

Year of publication 2015
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:

You are running an old browser version. We recommend updating your browser to its latest version.