A collection of high performance containers and utilities for concurrent and asynchronous programming.
See Performance for benchmark results for the containers and comparison with other concurrent maps.
HashMap is a scalable in-memory unique key-value container that is targeted at highly concurrent write-heavy workloads. It uses EBR for its hash table memory management in order to implement non-blocking resizing and fine-granular locking without static data sharding; it is not a lock-free data structure, and each access to a single key is serialized by a bucket-level mutex. HashMap is optimized for frequently updated large data sets, such as the lock table in database management software.
A unique key can be inserted along with its corresponding value, and then the inserted entry can be updated, read, and removed synchronously or asynchronously.
```rust use scc::HashMap;
let hashmap: HashMap
assert!(hashmap.insert(1, 0).isok()); asserteq!(hashmap.update(&1, |v| { *v = 2; *v }).unwrap(), 2); asserteq!(hashmap.read(&1, |, v| *v).unwrap(), 2); assert_eq!(hashmap.remove(&1).unwrap(), (1, 2));
let futureinsert = hashmap.insertasync(2, 1); let futureremove = hashmap.removeasync(&1); ```
It supports upsert as in database management software; it tries to insert the given key-value pair, and if the key exists, it updates the value field with the supplied closure.
```rust use scc::HashMap;
let hashmap: HashMap
hashmap.upsert(1, || 2, |, v| *v = 2); asserteq!(hashmap.read(&1, |, v| *v).unwrap(), 2); hashmap.upsert(1, || 2, |, v| *v = 3); asserteq!(hashmap.read(&1, |, v| *v).unwrap(), 3);
let futureupsert = hashmap.upsertasync(2, || 1, |_, v| *v = 3); ```
There is no method to confine the lifetime of references derived from an Iterator to the Iterator, and it is illegal to let them live as long as the HashMap. Therefore Iterator is not implemented, instead, it provides a number of methods as substitutes for Iterator: for_each, for_each_async, scan, scan_async, retain, and retain_async.
```rust use scc::HashMap;
let hashmap: HashMap
assert!(hashmap.insert(1, 0).isok()); assert!(hashmap.insert(2, 1).isok());
// Inside for_each, an ebr::Barrier protects the entry array.
let mut acc = 0;
hashmap.foreach(|k, vmut| { acc += *k; *vmut = 2; });
asserteq!(acc, 3);
// for_each can modify the entries.
asserteq!(hashmap.read(&1, |, v| *v).unwrap(), 2);
asserteq!(hashmap.read(&2, |, v| *v).unwrap(), 2);
assert!(hashmap.insert(3, 2).is_ok());
// Inside retain, an ebr::Barrier protects the entry array.
assert_eq!(hashmap.retain(|k, v| *k == 1 && *v == 0), (1, 2));
// It is possible to scan the entries asynchronously. let futurescan = hashmap.scanasync(|k, v| println!("{k} {v}")); let futureforeach = hashmap.foreachasync(|k, vmut| { *vmut = *k; }); ```
HashSet is a version of HashMap where the value type is ().
All the HashSet methods do not receive a value argument.
```rust use scc::HashSet;
let hashset: HashSet
assert!(hashset.read(&1, || true).isnone()); assert!(hashset.insert(1).isok()); assert!(hashset.read(&1, || true).unwrap());
let futureinsert = hashset.insertasync(2); let futureremove = hashset.removeasync(&1); ```
HashIndex is a read-optimized version of HashMap. It applies EBR to its entry management as well, enabling it to perform read operations without blocking or being blocked.
Its read method is completely lock-free and does not modify any shared data.
```rust use scc::HashIndex;
let hashindex: HashIndex
assert!(hashindex.insert(1, 0).isok()); asserteq!(hashindex.read(&1, |_, v| *v).unwrap(), 0);
let futureinsert = hashindex.insertasync(2, 1); let futureremove = hashindex.removeif(&1, |_| true); ```
An Iterator is implemented for HashIndex, because any derived references can survive as long as the associated ebr::Barrier lives.
```rust use scc::ebr::Barrier; use scc::HashIndex;
let hashindex: HashIndex
assert!(hashindex.insert(1, 0).is_ok());
let barrier = Barrier::new();
// An ebr::Barrier has to be supplied to iter.
let mut iter = hashindex.iter(&barrier);
// The derived reference can live as long as barrier.
let entryref = iter.next().unwrap();
asserteq!(iter.next(), None);
drop(hashindex);
// The entry can be read after hashindex is dropped.
asserteq!(entryref, (&1, &0));
```
TreeIndex is a B+ tree variant optimized for read operations. The ebr module enables it to implement lock-free read and scan methods.
Key-value pairs can be inserted, read, and removed, and the read method is lock-free.
```rust use scc::TreeIndex;
let treeindex: TreeIndex
assert!(treeindex.insert(1, 2).isok()); asserteq!(treeindex.read(&1, |_, v| *v).unwrap(), 2); assert!(treeindex.remove(&1));
let futureinsert = treeindex.insertasync(2, 3); let futureremove = treeindex.removeif_async(&1, |v| *v == 2); ```
Key-value pairs can be scanned and the scan method is lock-free.
```rust use scc::ebr::Barrier; use scc::TreeIndex;
let treeindex: TreeIndex
assert!(treeindex.insert(1, 10).isok()); assert!(treeindex.insert(2, 11).isok()); assert!(treeindex.insert(3, 13).is_ok());
let barrier = Barrier::new();
let mut visitor = treeindex.iter(&barrier); asserteq!(visitor.next().unwrap(), (&1, &10)); asserteq!(visitor.next().unwrap(), (&2, &11)); asserteq!(visitor.next().unwrap(), (&3, &13)); assert!(visitor.next().isnone()); ```
Key-value pairs in a specific range can be scanned.
```rust use scc::ebr::Barrier; use scc::TreeIndex;
let treeindex: TreeIndex
for i in 0..10 { assert!(treeindex.insert(i, 10).is_ok()); }
let barrier = Barrier::new();
asserteq!(treeindex.range(1..1, &barrier).count(), 0); asserteq!(treeindex.range(4..8, &barrier).count(), 4); assert_eq!(treeindex.range(4..=8, &barrier).count(), 5); ```
Queue is a concurrent lock-free first-in-first-out queue.
```rust use scc::Queue;
let queue: Queue
queue.push(1); assert!(queue.pushif(2, |e| e.mapor(false, |x| x == 1)).is_ok()); assert!(queue.push_if(3, |e| e.map_or(false, |x| *x == 1)).is_err()); assert_eq!(queue.pop().map(|e| *e), Some(1)); asserteq!(queue.pop().map(|e| **e), Some(2)); assert!(queue.pop().isnone()); ```
The ebr module implements epoch-based reclamation and various types of auxiliary data structures to make use of it. Its epoch-based reclamation algorithm is similar to that implemented in crossbeam_epoch, however users may find it easier to use as the lifetime of an instance is safely managed. For instance, ebr::AtomicArc and ebr::Arc hold a strong reference to the underlying instance, and the instance is automatically passed to the garbage collector when the reference count drops to zero.
The ebr module can be used without an unsafe block.
```rust use scc::ebr::{suspend, Arc, AtomicArc, Barrier, Ptr, Tag};
use std::sync::atomic::Ordering::Relaxed;
// atomic_arc holds a strong reference to 17.
let atomic_arc: AtomicArc
// barrier prevents the garbage collector from dropping reachable instances.
let barrier: Barrier = Barrier::new();
// ptr cannot outlive barrier.
let mut ptr: Ptr
// atomic_arc can be tagged.
atomicarc.updatetag_if(Tag::First, |t| t == Tag::None, Relaxed);
// ptr is not tagged, so CAS fails.
assert!(atomicarc.compareexchange(
ptr,
(Some(Arc::new(18)), Tag::First),
Relaxed,
Relaxed,
&barrier).is_err());
// ptr can be tagged.
ptr.set_tag(Tag::First);
// The return value of CAS is a handle to the instance that atomic_arc previously owned.
let prev: Arc
// 17 will be garbage-collected later.
drop(prev);
// ebr::AtomicArc can be converted into ebr::Arc.
let arc: Arc
// 18 will be garbage-collected later.
drop(arc);
// 17 is still valid as barrier keeps the garbage collector from dropping it.
asserteq!(*ptr.asref().unwrap(), 17);
// Execution of a closure can be deferred until all the current readers are gone. barrier.defer_execute(|| println!("deferred")); drop(barrier);
// If the thread is expected to lie dormant for a while, call suspend() to allow other threads
// to reclaim its own retired instances.
suspend();
```
LinkedList is a type trait that implements lock-free concurrent singly linked list operations, backed by EBR. It additionally provides support for marking an entry of a linked list to denote a user-defined state.
```rust use scc::ebr::{Arc, AtomicArc, Barrier}; use scc::LinkedList;
use std::sync::atomic::Ordering::Relaxed;
struct L(AtomicArc
let barrier = Barrier::new();
let head: L = L::default();
let tail: Arc
// A new entry is pushed. assert!(head.pushback(tail.clone(), false, Relaxed, &barrier).isok()); assert!(!head.is_marked(Relaxed));
// Users can mark a flag on an entry. head.mark(Relaxed); assert!(head.is_marked(Relaxed));
// next_ptr traverses the linked list.
let nextptr = head.nextptr(Relaxed, &barrier);
asserteq!(nextptr.as_ref().unwrap().1, 1);
// Once tail is deleted, it becomes invisible.
tail.deleteself(Relaxed);
assert!(head.nextptr(Relaxed, &barrier).is_null());
```
Interpret the results cautiously as benchmarks do not represent real world workloads.
usize integers is assigned to each thread.InsertR -> ReadR -> RemoveR.| | 1 thread | 4 threads | 16 threads | 64 threads | |---------|------------|------------|------------|------------| | Insert | 9.133s | 15.823s | 42.23s | 45.651s | | Scan | 0.147s | 0.688s | 2.903s | 14.127s | | Read | 4.042s | 5.061s | 6.517s | 8.033s | | Remove | 4.72s | 6.415s | 10.924s | 24.141s | | InsertR | 10.755s | 26.254s | 53.422s | 56.357s | | Mixed | 15.066s | 33.032s | 30.241s | 33.765s | | RemoveR | 7.341s | 12.93s | 19.607s | 26.407s |
| | 1 thread | 4 threads | 16 threads | 64 threads | |---------|------------|------------|------------|------------| | Insert | 9.455s | 16.342s | 44.64s | 51.105s | | Scan | 0.298s | 1.361s | 5.457s | 22.87s | | Read | 3.675s | 4.799s | 6.143s | 7.714s | | Remove | 4.917s | 7.32s | 12.323s | 33.625s | | InsertR | 11.024s | 25.733s | 54.258s | 62.372s | | Mixed | 15.963s | 36.317s | 38.364s | 41.437s | | RemoveR | 7.608s | 13.31s | 20.135s | 37.109s |
| | 1 thread | 4 threads | 16 threads | 64 threads | |---------|------------|------------|------------|------------| | Insert | 14.647s | 16.139s | 18.575s | 42.535s | | Scan | 1.23s | 5.016s | 20.639s | 84.051s | | Read | 3.575s | 4.178s | 4.619s | 5.145s | | Remove | 5.902s | 8.594s | 10.555s | 10.912s | | InsertR | 20.163s | 74.159s | 82.621s | 59.809s | | Mixed | 28.002s | 153.103s | 426.883s | 448.8s | | RemoveR | 9.64s | 22.774s | 29.326s | 31.994s |
0.9.0
HashMap::new, HashIndex::new, and HashSet::new.unsafe HashIndex::update for linearizability.0.8.4
ebr::Barrier::defer_execute for deferred closure execution.0.8.3
ebr::AtomicArc::{clone, get_arc} to never return a null pointer if the ebr::AtomicArc is always non-null.0.8.2
0.8.1
Debug for container types.0.8.0