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 |
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-featuresAvailable Benches:
- stack
- queue
- avltree
- btree
Several cds has its own statistics. Use it by printing on test.
cargo install flamegraph
sudo cargo flamegraph --no-default-features --test tests -- {test_name}- common spin lock and sequece lock(SeqLock)
- flat combining lock
- lock stack(based on std::sync::Mutex and spin lock)
- Treiber's Stack
- Elimination-Backoff Stack
- lock queue(based on std::sync::Mutex and spin lock)
- two lock queue
- FCQueue(use flat combining lock)
- Michael-Scott queue
- TODO: implement Harris linked list
- SeqLockAVLTree, RwLockAVLTree(use crossbeam_utils::sync::ShardedLock)
- TODO: ?
- The Art of Multiprocessor Programming
- https://github.com/kaist-cp/cs431
- https://github.com/khizmax/libcds
- https://www.cs.cmu.edu/~yihans/papers/tutorial.pdf
- flat combining lock: https://people.csail.mit.edu/shanir/publications/Flat%20Combining%20SPAA%2010.pdf
- Treiber's Stack: https://dominoweb.draco.res.ibm.com/58319a2ed2b1078985257003004617ef.html
- Elimination-Backoff Stack: https://people.csail.mit.edu/shanir/publications/Lock_Free.pdf
- two lock queue, Michael-Scott Queue: https://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf