saturn
saturn copied to clipboard
A lock-free bounded queue
This implements a lock-free bounded queue — blocking using domain-local-await.
The data structure / algorithm is based on the Michael-Scott queue extended with length maintenance and caching of remaining capacity in such a way that additional contention is avoided in the happy paths.
TODO:
- [x] fix opam files to build on CI
- [x] use backoff from separate package
- [x] fix dune-project
- [ ]
try_push,length(can be done inO(1)),is_empty - [ ] tests
- [ ] ability to change capacity
- [ ] benchmarking
- [ ] consider whether making wakeups fair is worth it (currently all awaiters are woken up so there is no fairness)
- [ ] documentation
FYI, I will squash this PR to a single commit to make this PR a little bit easier to work with.
FYI, I changed this to use Picos instead of DLA.