Possibly unnecessary use of Mutex in Merge implementation?

[extremeandy]

This is more of a question than an issue right now, but may have want some action depending on the answer to the question.

I noticed in the implementation impl<S, const N: usize> Stream for Merge<S, N> that WakerArray is being used, which requires locking a Mutex for read/write. However, since poll_next borrows Self mutably, it's guaranteed that we won't get any re-entrant calls to poll_next.

Just wondering if there is a reason this is needed - something I'm missing - or whether there is room for improvement here, say a WakerArray implementation that didn't require Mutex?

Thanks!

[wishawa]

When merging N streams, we can either

• poll each of them every time, or
• poll only the ones that have are ready to be polled.

We go with the second approach (because when N is huge, the first can become quite slow).

This requires keeping track of which streams are ready to be polled. Each stream tell us that it is ready by waking the waker we passed to it when we polled it last time. So when one of our wakers is woken, we need to record that the associated stream is ready to be polled again.

The way Rust's async is designed, wakers can be woken from anywhere at anytime. It doesn't matter what is going on with the Merge; one stream might have sent a waker to a different thread and that thread can wake it at will.

So the state where we record streams' readiness needs to be accessible from any thread at anytime. Hence the Mutex.

That said, the Mutex is not absolutely required; we can switch WakerArray from having an array of bool inside a Mutex to using an array of AtomicBool.
PR #115, will make things harder (as WakerArray will then contain a list of woken futures/streams), but even then avoiding Mutex is still possible by use of a non-blocking linked list or something similar.