concache

This crate provides two implementations of fast, concurrent, shared hash maps.

Both implementations provide lock-free implementations that use lock-free linked list buckets. Memory is safely destructed and reclaimed using either crossbeam::epoch or a manual Quiescent-State-Based Reclamation implementation. See the [crossbeam] and [manual] module documentations respectively for further details.

Table resizing is not yet supported in either implementation, but the map will also never fill due to the linked implementation; instead, performance will decrease as the map is filled with more keys.

The crate was written by Aditya Saligrama and Andrew Shen while writing A practical analysis of Rust’s concurrency story as their 2018 project for MIT PRIMES.

Performance

We've run some benchmarks of concache against a standard Rust HashMap protected by a reader-writer lock, as well as against chashmap — a crate which provides "concurrent hash maps, based on bucket-level multi-reader locks". The benchmarks were run using the binary in benchmark/ on a 40-core machine with Intel(R) Xeon(R) CPU E5-2660 v3 @ 2.60GHz CPUs.

The benchmark runs a number of reader and writer threads in tight loops, each of which does a read or write to a random key in the map respectively. Results for both uniform and skewed distributions are provided below. The benchmark measures the average number of reads and writes per second as the number of readers and writers increases.

Preliminary results show that concache performs well under contention.