Fast, Dynamically-Sized Concurrent Hash Table
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 unpredictable 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.
Authors: Jiří Barnat, Petr Ročkai, Vladimír Štill, and Jiří Weiser
Project: DIVINE4
Published in: Model Checking Software (SPIN 2015), Springer International Publishing, 2015, volume 9232 of Lecture Notes in Computer Science, 49-65.