I'm not familiar with the code so excuse me if I'm asking something stupid.
But can't you add the now Due task to the existing runq, and then keep the same loop, it would cause the tasks to be in a roundrobin behaviour instead of always running the wakers first. Now, If you reach the case where you would have enough jobs on Zzz, the runq would now starve, in essence just inverting your problem.

This does need fixing, but I think we need a more general solution. A fiber that keeps yielding will also prevent any other IO from happening, not just sleeps.

Perhaps we should keep a "check-for-IO" job on the run queue. When it gets to the head, we dispatch any IO (and add another check-for-IO job)?

Thanks for your reviews ! Yes indeed I should have warned that this was written on top of my head to fix the specific issue and start a discussion.

Perhaps we should keep a "check-for-IO" job on the run queue. When it gets to the head, we dispatch any IO (and add another check-for-IO job)?

That's what I was thinking, I can try to implement that.

@talex5 I have updated the PR. Please take a look and tell me if something is wrong.
The invariant I'm enforcing is that at any time the run queue has a single IO task.
As a consequence the exit cases have to check if the run queue has a single element (instead of being empty).
I have added the has_single_element but I'm not sure of it's thread-safety.

Thank you for your review.

But with this change, make test_luv now hangs, so we probably need a similar fix there.

I have added a fix to the luv backend in the second commit. In particular I'm using Luv.Async.send to yield back to the event loop when the IO task is due.

I think it would be simpler to delay adding the IO event until just before returning.

Indeed that sounds better and reduces the diff. I have force-pushed my first commit with the suggested changes

It still seems to be working, but might need to make it more robust, or at least update the comment to warn that it might not work now.

Do you have an idea on how to make it more robust ? Do you have tests that are waiting for the run queue to become empty ?

I have added a fix to the luv backend in the second commit. In particular I'm using Luv.Async.send to yield back to the event loop when the IO task is due.

This has a large effect on the benchmarks! e.g.

Before:

$ EIO_BACKEND=luv make bench
dune exec -- ./bench/bench_yield.exe
n_fibers, ns/iter, promoted/iter
       1,   92.68,        4.9931
       2,   91.56,        4.9955
       3,   91.59,        4.9979

After:

$ EIO_BACKEND=luv make bench
dune exec -- ./bench/bench_yield.exe
n_fibers, ns/iter, promoted/iter
       1,  968.06,        9.9792
       2,  535.77,        7.4967
       3,  395.65,        6.6500

io-uring is also affected, though not as much.
Before:

$ EIO_BACKEND=io-uring make bench
dune exec -- ./bench/bench_yield.exe
n_fibers, ns/iter, promoted/iter
       1,   79.11,        4.9939
       2,   77.59,        4.9954
       3,   78.49,        4.9969

After:

$ EIO_BACKEND=io-uring make bench
dune exec -- ./bench/bench_yield.exe
n_fibers, ns/iter, promoted/iter
       1,  165.01,        9.9854
       2,  118.29,        7.4761
       3,  106.06,        6.6621

Thank you for performing the benchmarks. I expected a performance cost but not that high for the luv backend. A single task yielding is indeed the worst case, the run queue having 1 task and and 1 IO at any time, so the IO is performed once every two iterations.

To address the performance cost globally, what we can do is remove the IO event from the run queue, and have instead a counter-based strategy:

• initially counter is at zero
• each run queue pop increases the counter
• when the counter is higher than a threshold (which value?), take the IO path instead of popping the next task
• when the IO path is taken set the counter to zero

This strategy has a negligible runtime cost when no busy yielding is happening.
When busy yielding is happening, the cost will depend on on the number of tasks run between each IO lookup. The higher the threshold, the lower the overhead but it increases latency.

What do you think ? About the luv backend, I'm not familiar enough with it to figure out how to improve the performances on that side.

I have no idea why the CI failure is happening. I have also been able to reproduce the test using the Docker instructions of the CI job..

Thanks!