Informace o publikaci

Fast, Dynamically-Sized Concurrent Hash Table

Logo poskytovatele
Autoři

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

Rok publikování 2015
Druh Článek ve sborníku
Konference Model Checking Software
Fakulta / Pracoviště MU

Fakulta informatiky

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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info