Concurrent Data Structure for Rust
Goal & Status
Implement sequential, lock-based and lock-free concurrent data structures below:
|
Stack |
Queue |
Linked List |
AVL Tree |
HashTable |
| Sequential |
Done |
Done |
Done |
Done |
|
| Lock-based |
Done |
Done |
|
Done |
|
| Lock-free |
Done |
Done |
|
|
|
Benchmark
You can run bench like this:
cargo install cargo-criterion
# default feature has accumulating stats on available structure.
cargo criterion --bench {bench_name} --no-default-features
Available Benches:
- stack
- queue
- avltree
- btree
Profile
Use CDS stats
Several cds has its own statistics. Use it by printing on test.
Flamegraph
cargo install flamegraph
sudo cargo flamegraph --no-default-features --test tests -- {test_name}
Detail
Lock
- common spin lock and sequece lock(SeqLock)
- flat combining lock
Stack
- lock stack(based on std::sync::Mutex and spin lock)
- Treiber's Stack
- Elimination-Backoff Stack
Queue
- lock queue(based on std::sync::Mutex and spin lock)
- two lock queue
- FCQueue(use flat combining lock)
- Michael-Scott queue
Linked List
- TODO: implement Harris linked list
AVL Tree
- SeqLockAVLTree, RwLockAVLTree(use crossbeam_utils::sync::ShardedLock)
HashTable
Reference
General
Lock
Stack
Queue
Binary Search Tree