Faster scope completion

[chescock]

What problem does this solve or what need does it fill?

When a ThreadPool::scope call runs out of jobs from the current scope before the scope is complete, it runs other jobs from the pool. That works well if the jobs are small and uniform, but for Bevy this can cause Query::par_iter() calls to start executing other systems while waiting! If the stolen systems are long and the blocked system has a lot of dependencies, that removes a lot of concurrency from the schedule.

What solution would you like?

Have Scope::complete only run jobs from the current scope. If it runs out of local jobs before the scope is complete, put the thread to sleep instead of running other jobs, so that it can be awakened immediately when the scope is completed.

Then, to make sure the CPUs are all utilized, add a new worker thread to the pool. When the scope is finally complete, remove the thread that completed it to compensate. This will usually be a different thread then the one added.

It may be possible to do this without resizing the pool by sending the WorkerThread value to the new thread.

Additional context

For comparison, here are the approaches taken by some other pools:

• Rayon runs other work. It assumes that jobs are small, so there won't be much delay in waiting.
• async_scoped can be used with Tokio and does something similar to this proposal. It calls tokio::task::block_in_place, which sends the local queue to a new thread. But if another thread does take the queue, the original one never takes it back! That means it runs one too many threads until the original job completes. It assumes the original job was small and will complete quickly once the block_in_place call is done.
• bevy_tasks either runs other work or blocks, based on the tick_task_pool_executor parameter.
  • The multi-threaded executor passes false, blocking the thread. This runs on the main thread, and we want to keep it idle to handle non-send and exclusive systems.
  • Everything else (including Query::par_iter()) passes true, running other work.

[NthTensor]

I'm interested in this idea. The danger would be that the newly spawned thread might still have to complete it's work item before the old thread could progress because you need to make sure they don't try to write to the same thread info at once.

I'm going to try and articulate a vague idea here: worker threads operate on a sort of "condition stack". Each new call to run_until pushes a new condition on the stack. While waiting for condition A it may run a new task that pushes condition B onto the stack, and then we have to wait for B. We might even go to sleep waiting for B, and in that case we won't wake even if A happens before B. This is the issue we are looking at here basically, right?

Here's my thought: Perhaps we can just pause jobs that want to push additional conditions (by calling run_until) when we are already waiting for something. I think it's fair to assume that most jobs don't call run_until. Not even all the main apis call it: block_on, join (in two different places), and scope all do, but spawn, spawn_future and spawn_async do not!

If we want a specific scope to not get stuck behind other pending conditions, we can actually continue running jobs. We just preempt any other jobs that try to push conditions to the stack. Say we are running job 1, and it calls run_until(A). We keep executing jobs waiting for A. Eventually we run into job 2, which calls run_until(B) (through block_on, join, or scope). Now, instead of progressing, we go to sleep waiting for A. When we receive A we go back to executing job 1. When it completes we start executing jobs waiting for B. When we receive B we go back to executing job 2. The neat thing is that job 2 won't be able to tell anything happened: it will have just called a blocking api and been blocked. It's not intrusive.

In effect this just means we keep executing jobs but if we encounter par_iter we wait to start it until the current thing we are waiting for completes, and then execute once it's done. You could also think of this as "queuing conditions" rather than "stacking them".

The question is: how do we jump from a point in job 2 to a point in job 1, and how do we jump back to job 2 once job 1 completes? Might be possible with async code, probably not with spawn itself.

[chescock]

I'm going to try and articulate a vague idea here: worker threads operate on a sort of "condition stack". Each new call to run_until pushes a new condition on the stack. While waiting for condition A it may run a new task that pushes condition B onto the stack, and then we have to wait for B. We might even go to sleep waiting for B, and in that case we won't wake even if A happens before B. This is the issue we are looking at here basically, right?

There's also the case where the new task doesn't push any condition B, but just does a lot of CPU-intensive work. That's the case for long-running systems, since outside of par_iter they don't usually call back into the executor.

Say we are running job 1, and it calls run_until(A). We keep executing jobs waiting for A. Eventually we run into job 2, which calls run_until(B) (through block_on, join, or scope). Now, instead of progressing, we go to sleep waiting for A. When we receive A we go back to executing job 1. When it completes we start executing jobs waiting for B. When we receive B we go back to executing job 2.

I don't think I see how this would work. The call stack has Job 1 calling into run_until calling into Job 2, right? How could we resume Job 1 while Job 2 is still on the stack?

[chescock]

I realized one thing that will make this less urgent: Forte uses a LIFO local queue, while async-executor was using FIFO.

With a FIFO queue, par_iter() would run any systems in the local queue before starting jobs from the iterator, which made it very likely it would run a system while waiting. With a LIFO queue, it will try to do the parallel jobs first. And since we share the oldest jobs, the parallel jobs are only likely to get stolen when there aren't any systems to steal in the whole pool.

[NthTensor]

Ah interesting. Using fifo locally seems like an odd choice. I bet we could design some stress tests to measure the practical impact of this.

I thought more about my earlier point and I think it would only be possible with lots of really intrusive boxed closures, so probably not worth it.

Also, FYI I'm almost done with the full loom test suite and some semi-realistic synthetic benchmarks. While doing that work I decided you were right and mostly remove the atomic activity counter.

Once we the benchmarks set up we should be able to start making comparisons to Rayon and doing some more targeted optimizations.

[chescock]

Using fifo locally seems like an odd choice.

It makes sense to use FIFO to prefer fairness when you have a lot of unrelated tasks, like in a web server where each web request spawns a task. It's just the wrong tool for Bevy to use for par_iter. :)

Also, FYI I'm almost done with the full loom test suite and some semi-realistic synthetic benchmarks.

Awesome!