2 releases
0.1.1 | Feb 6, 2023 |
---|---|
0.1.0 | Feb 18, 2020 |
#2118 in Asynchronous
16KB
284 lines
Waitlist
In Rust async programming it is somewhat common to need to keep track of a set of Waker
s that should be notified when something happens. This is useful for implementing many synchronization abstractions including mutexes, channels, condition variables, etc. This library provides an implementation of a queue of Waker
s, that can be used for this purpose.
Acknowledgements
The implementation (and API) pulls heavily from the waker_set
module in async-std
, and the storage structure was inspired by slab
, although the actual details differ somewhat to optimize for the uses of WaitList
.
Differences from async-std
and futures-util
This implementation differs from the waker_set
implementation and patterns followed in the futures-util
crate. Specifically:
- The order in which tasks are notified is more fair.
Waitlist
uses a FIFO queue for notifying waiting tasks, whereas the usage ofslab
in other implementations can result in task starvation in certains situations (see https://users.rust-lang.org/t/concerns-about-using-slab-to-track-wakers/33653). - Removing an entry from the list is potentially
O(n)
rather thanO(1)
. This is a bit of a tradeoff. Using slab getsO(1)
removal because it doesn't care about the order of the entries. On the other hand, notifying a single entry isO(1)
withWaitlist
, and notifying all waiting only has to iterate through waiting entries, whereas with slab it is necessary to iterate through the entire capacity of the slab. Also, if an entry has already been woken inWaitlist
, "removal" is still onlyO(1)
(because it is really just decrementing a counter). WaitList
uses std::sync::Mutex to synchronize similar tofutures-util
and unlikeasync-std
which uses aMutex
.