Cats-effect: Auto-yielding semantics

[RaasAhsan]

Cats Effect 1 and 2 historically did not exhibit any auto-yielding semantics in its IO implementation, that is, a fiber will never yield back to the scheduler unless an asynchronous boundary is explicitly inserted. Therefore, whether or not a fiber yields and how frequently it does so is left to the discretion of the user. There was no shortage of discussion around this point in the past, but we should revisit it for Cats Effect 3.

The argument for auto-yielding is usually one centered around fairness and liveness. On machines with a small number of cores, it's surprisingly easy to end up in a situation where one or more fibers are perpetually in a flatMap loop that never yields, which ends up starving other fibers. To an observer, it may look like a completely different bug. For example, FS2 encountered this issue while porting to CE3 recently (https://github.com/typelevel/fs2/pull/2005). It seemed as if cancellation wasn't being respected because of memory publication semantics, but it turns out that the cancelling fiber was just being starved of a carrier thread.

On the other hand, a higher degree of fairness generally implies lower throughput and higher (but more consistent) latencies. I suspect for most applications that deal with I/O (which account for a supermajority), this is probably negligible since they, by nature, frequently encounter asynchronous boundaries. CE1/2 also implement many common combinators like bracket and guarantee in terms of Async, which is no longer the case in 3.

Some discussion questions I have:

1. How would auto-yielding interact with a work stealing pool? We could reschedule the task on the local task queue, or the global task queue.
2. How would auto-yielding interact with auto-cancellation semantics?
3. Could auto-yielding could be controlled by a system property?
4. What kind of behavior makes for the best user experience? If we can help people avoid weird bugs which require familiarity of internals to understand, then I think it's well worth it. I'm not sure how often people run into these kinds of problems today though.

Relevant Gitter discussions:

1. https://gitter.im/typelevel/cats-effect-dev?at=5f4221ce48237809373903f7

[djspiewak]

How would auto-yielding interact with a work stealing pool? We could reschedule the task on the local task queue, or the global task queue.

Rescheduling on the local pool actually takes all of the penalties of auto-yielding semantics and removes them. We can reschedule on the local pool because all we really need to do is give the scheduler a chance to pick someone else. If the scheduler doesn't need that capability, then it should resume us immediately, on the same thread, without any cache dumping and a minimum of memory barriers. Work-stealing is perfect for that.

I would actually be reticent to go with auto-yielding if we didn't have work-stealing in the works.

How would auto-yielding interact with auto-cancellation semantics?

One thought: we might consider removing the forced memory boundary, though usually auto-yielding is once every 1024 by default, while auto-cancelation is checked every 512.

Could auto-yielding could be controlled by a system property?

And it should be! Also a global property on JavaScript, where auto-yielding is particularly helpful due to single-threaded semantics.

What kind of behavior makes for the best user experience? If we can help people avoid weird bugs which require familiarity of internals to understand, then I think it's well worth it. I'm not sure how often people run into these kinds of problems today though.

I think that, as far as avoiding weird bugs go, auto-yielding helps a lot. My concern is it would set us up in a situation where people might write code as fs2 did, trusting auto-yielding semantics to "save" them, even when it isn't actually guaranteed in the abstractions.

[vasilmkd]

In #1134, cede reschedules the fiber at the back of the local queue and is the cheapest form of yielding in the run loop. Does auto-yielding become a case of sprinkling cede in the code then?

[djspiewak]

Does auto-yielding become a case of sprinkling cede in the code then?

Yep! We basically count the number of runloop ticks between async boundaries. If we go more than a set amount (ZIO and Monix default to 1024), then we insert a cede.

[TimWSpence]

I can have a go at this if nobody else has started working on it?