A quick look at the performance

[tkf]

I haven't tried any optimizations so far but Schedulers.jl scale quite well for the benchmark of fib(20).

The work-stealing (red) and prioritized (multi-queue; yellow) schedulers can speed up fib computation while the base (blue) scheduler straggles above around 5 threads. That said, this could be because of some missing features in Schedulers.jl.

Links:

• Benchmark driver: https://gist.github.com/tkf/23aac6fb96ed5dd53b8e03564254b226
• Notebook: https://nbviewer.org/gist/tkf/2e522274e00d17c69da9d82bc8138348/00_notebook.ipynb
• Benchmarked version: 9897f5e

[tkf]

Since prioritized (yellow) and base (blue) both use multi-queue, it's suspicious that prioritized performs better than base. Maybe the only "true" effect is the difference between prioritized and workstealing.

[chriselrod]

For me, base threads is always slower than single threaded (IIRC).
Interestingly, Polyester does well on my M1 (4 threads) but is a little slower on a 28 thread Intel machine.

Polyester scales extremely poorly here.
Actually, the only reason it does acceptable on the M1 / with only 4 threads is probably because it quickly runs out of threads, and thus acts sort of like a depth first scheduler.
This isn't the case with more threads, causing it to scale poorly because of some reason like spinning while waiting on the unbalanced load, or contention for the single global scheduler.

I haven't tried the workstealing or prioritized yet, but they look to do far better.

[chriselrod]

┌ Error: Stack-copying not supported
└ @ Schedulers.Internal ~/.julia/dev/Schedulers/src/runtime.jl:225

What's the solution for this?

[tkf]

I noted a bit about it in #27 but the short answer is "I don't know" ATM. There are some horrible hacks in Schedulers.jl for supporting the migration of the task across threads so I may be simply violating some invariance that julia sets up. I need to dig into julia's task/stack management internal more and see how to make it work.

[tkf]

Also, I think something like Polyester.jl is orthogonal tooling. Unless Polyester.jl provides something akin to Base.wait()/Base.schedule(task) (aka park/unpark) it'd be impossible to cover the full concurrency API that Julia needs to provide. In particular, each task needs to have its own call stack (or has some way to make it resumable) for providing the wait/schedule API. Since stack allocation significantly contributes to the slowness of the task startup, it does make sense that the API choice of Polyester.jl contributes to its performance. As always, restricting API enlarges optimizability.

(That said, I think there are several ways to solve/mitigate the stack allocation issue. For example, the scheduler can prefer to run tasks that already have the stack. Under the Tapir task semantics JuliaLang/julia#39773, we can dynamically fuse tasks when stack allocation have failed. I'm hoping that moving scheduler to Julia JuliaLang/julia#43649 would make improving the situation easier.)