saturn icon indicating copy to clipboard operation
saturn copied to clipboard

A lock-free bounded queue

Open polytypic opened this issue 2 years ago • 1 comments

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 in O(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

polytypic avatar Jul 14 '23 13:07 polytypic

FYI, I will squash this PR to a single commit to make this PR a little bit easier to work with.

polytypic avatar Mar 01 '24 11:03 polytypic

FYI, I changed this to use Picos instead of DLA.

polytypic avatar Sep 29 '24 19:09 polytypic