Document fairness properties

[yoshuawuyts]

Traits such as race and merge produce a single output from multiple inputs. These traits provide fairness properties which should be documented at the trait implementation level, but also on the Race and Merge traits themselves.

[eholk]

I think this is a great idea because there are a few ways we could define fairness and I think it's worth declaring which one we mean and plan to uphold.

Here are a few questions I think would be good to answer:

How do we measure fairness?

Here are some possibilities:

1. We try to poll each future the same number of times.
2. We try to spend the same amount of time executing each future.
3. We want each future to have an equal chance of completing.

I think 3 is probably not what we want. For example, if you do (file.read(), timeout(45)).race(), you want the file.read() future to be the one that completes 100% of the time. The timeout is basically just there to keep things from getting stuck.

Option 2 is probably not great either, since we may not always be running in an environment that has a clock. (Although I think basically any device that can run Rust code will have some way of tracking time.) Also, futures are probably IO bound, rather than CPU bound, so balancing execution time probably doesn't really matter since futures will spend very little time running compared to time spent waiting on IO.

Option 1 is the easiest to implement, but it may not be fair if the futures themselves are unbalanced in how much work each call to poll does.

What assumptions do we make about the behavior of futures?

Since we're doing cooperative multitasking and can't preempt futures, the behavior of the system depends a lot on the futures themselves.

I'd suggest we assume a future that does something like when polled executes for a small, random amount of time, then returns Ready or Pending with some probability. If it returns Pending, then after a random amount of time something will wake up the future.

How do we deal with futures that are Pending?

Say we had future a and b and we polled each of them once. Future a returns Pending and then doesn't wake up until we've polled future b ten times. At this point let's say both futures return Pending when polled but immediately wake up. Do we then poll a ten more times before giving b another chance to run, or do we do round-robin between them as long as they are both ready?

---

I'm sure there are more questions but these are a few I'm currently thinking about. Are there other things we need to consider?

[max-heller]

Would you be open to having non-fair variants of combinators? For use-cases where ordering is important, it'd be great to have biased/prioritized versions (analogous to futures::select_biased!). I'm not sure what would make the most sense for such APIs, but I'd be happy to work on them if they'd be welcome

[yoshuawuyts]

In our case I don't think it matters as much as with the macro variants. Because we reuse futures and streams, and employ perfect wakers in just about every instance, the difference between "fair" and "unfair" waking is really small.

We are of course biased towards being fair; but if you want to preserve ordering in a stream which is being processed concurrently, I don't think new operations specifically to do away with fairness are going to be of much benefit for your use.