Fast, Dynamically-Sized Concurrent Hash Table
| Autoři | |
|---|---|
| Rok publikování | 2015 |
| Druh | Článek ve sborníku |
| Konference | Model Checking Software |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.1007/978-3-319-23404-5_5 |
| Obor | Informatika |
| Klíčová slova | Data Structures; Concurrency; Hash Tables; Model Checking; DIVINE; C++ |
| Popis | 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. |
| Související projekty: |