#slotmap #lock-free

ev_slotmap

A lock-free, eventually consistent, concurrent slot map

6 releases

0.2.1 Aug 31, 2020
0.2.0 Jul 27, 2020
0.1.3 Jul 25, 2020
0.1.0 Jun 25, 2020

#142 in Concurrency

38 downloads per month

MIT/Apache

37KB
712 lines

ev_slotmap

Crates.io Documentation

A lock-free, concurrent slot map.

Most of this library is a rip off of Jon Gjengset's evmap but with a few notable simplifications

  • The value-bag map is replaced with a one-way slotmap
  • No batched edits (required because slot map keys need to be returned on insert)
  • No associated metadata

The core synchronization component's of evmap are still present. Out of simplicity, we also use the ShallowCopy straight out of evmap instead of copy-pasting it in. Also the following blurb is almost straight from evmap.

This map implementation allows reads and writes to execute entirely in parallel, with no implicit synchronization overhead. Reads never take locks on their critical path, and neither do writes assuming there is a single writer (multi-writer is possible using a Mutex), which significantly improves performance under contention.

Unlike evmap which provides eventual consistency following explicit refresh calls, synchronization between reads and writers happens before write methods return. For read-heavy workloads, the scheme used by this module is particularly useful. Writers can afford to refresh after every write, which provides up-to-date reads, and readers remain fast as they do not need to ever take locks.

Performance

Benchmarks to come

Dependencies

~305KB