Scheduling for IO has fairness and performance problems

[turion]

Since the issue isn't documented well in one place, I'll do that here.

Summary

• In monad-schedule there is a performance and scheduling fairness problem when using the instance MonadSchedule IO repeatedly.
• Currently, it can be worked around by replacing IO by FreeAsyncT IO (added in Add FreeAsync monad-schedule#42, see https://hackage.haskell.org/package/monad-schedule-0.2.0.1/docs/Control-Monad-Schedule-FreeAsync.html).
• I'm investigating ways to fix this, for example by extending monad-schedule, or making rhine not depend on it.

The problem

The instance MonadSchedule IO works roughly like this:

1. Create an empty MVar
2. Launch a new green thread for each given action, putting their results in the MVar
3. Collect the first result with takeMVar
4. Return result, together with the continuations which are takeMVar as well

This is a fine implementation, but it doesn't work well in Rhine because there we schedule at each step of the clock, and use the continuations as actions for the next step. So we create a new green thread that does nothing except waiting for a result arrive on the old MVar and pasting it into the new MVar. The problem is exacerbated when one clock ticks much slower than another. In that case, the slower clock builds up a long chain of MVars which it needs wade through before returning the tick, resulting in a huge overhead and noticeable lags.

Solutions

Extend monad-schedule

From the perspective of Rhine, the problem stems from two assumptions in monad-schedule:

1. The type of continuations (unfinished actions after scheduling) is the same as the type of actions. We cannot distinguish an action that is immediately productive from one that is blocked on an MVar.
2. A new scheduling context (the MVar) is created each time. It's wasteful to create a new MVar, when there still is an older MVar on which operations are waiting.

We can extend the definition of MonadSchedule to include a type of continuations and type of scheduling contexts, with backwards compatible defaults. This is the most conservative solution, a WIP is in https://github.com/turion/monad-schedule/tree/dev_scheduling_context.

Forbid instance MonadSchedule IO

We could mark this instance deprecated and urge people to use FreeAsyncT. An even more lightweight implementation is possible based on the type Either (MVar a) (IO a), see also https://github.com/turion/monad-schedule/tree/dev_scheduling_context. This solution is the easiest to implement. But it is more restrictive and cumbersome on the user.

Drop monad-schedule dependency in Rhine

We would need to develop a concurrency primitive that is tailored directly to Rhine. The type signature would be something like:

class MonadSchedule m where
  schedule :: [Automaton m a b] -> Automaton m a b

Since I'm not aware of any other major users of monad-schedule, this is probably the cleanest solution, but it has some drawbacks:

• High development & testing effort
• It will probably be harder to develop custom instances for users

A WIP is here: #376