seqmap

The seqmap crate provides a set of data structures optimized for highly performant concurrent access with thounds of readers and writers. The basic building block is the SeqArray, which is in turn used to implement the more complex SeqMap, which is designed to greatly out-perform DashMap and other lock-free concurrent hash map solutions. The main caveat when using this crate is that your key and value types must implement Copy.

SeqArray and data structures that use it as a backing allow for lock-free concurrent reads to all elements (except during resizing, when a spin-wait strategy is used), and highly concurrent writes on all elements with minimal contention. Internally each data cell is protected by a seqlock::SeqLock.

SeqMap is a thin veneer over SeqArray that implements open addressing with linear probing. It provides a highly concurrent map interface with minimal contention, and supports concurrent reads and writes with no locks.

All data structures in this crate use interior mutability and can be safely shared and passed between threads. They are designed to be used in a highly concurrent environment where many threads are reading and writing concurrently, and match the performance of their non-current counterparts in single-threaded scenarios.

Special care has also been taken to ensure important atomics are placed on isolated cache lines to avoid false sharing, which can significantly degrade performance in real-world concurrent environments.

SeqMap Example

use seqmap::SeqMap;

let map = SeqMap::<u64, u8>::new();

map.insert(1, 42);
map.insert(2, 43);

std::thread::scope(|s| {
   s.spawn(|| {
       assert_eq!(map.get(1), Some(42));
       map.insert(3, 100);
   });
   s.spawn(|| {
      assert_eq!(map.get(2), Some(43));
      map.insert(4, 101);
   });
});

assert_eq!(map.get(1), Some(42));
assert_eq!(map.get(2), Some(43));
assert_eq!(map.get(3), Some(100));
assert_eq!(map.get(4), Some(101));

SeqArray Example

use seqmap::SeqArray;

let arr = SeqArray::<u32>::with_capacity(4);

arr.set(0, 1);
arr.set(1, 2);

std::thread::scope(|s| {
    s.spawn(|| {
        assert_eq!(arr.get(0), Ok(1));
        assert_eq!(arr.get(1), Ok(2));
        arr.set(2, 3);
    });
    s.spawn(|| {
        assert_eq!(arr.get(0), Ok(1));
        assert_eq!(arr.get(1), Ok(2));
        arr.set(3, 4);
    });
});

assert_eq!(arr.get(0), Ok(1));
assert_eq!(arr.get(1), Ok(2));
assert!(
    (arr.get(2) == Ok(3) && arr.get(3) == Ok(4)) ||
    (arr.get(2) == Ok(4) && arr.get(3) == Ok(3))
);