Nesting task pool's `Scope`s

[MiniaczQ]

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

Currently scopes cannot be nested, which means tasks spawned in a scope cannot spawn more tasks.

What solution would you like?

Modify Scope definition (for wasm and non-wasm) to use interior mutability.
That way many spawn-able scopes can be passed deeper.

This in both current cases means wrapping the results vector with a thread-safe interior mutability type, like Mutex or RwLock.

What alternative(s) have you considered?

A alternative to scopes mentioned in #4287 could cover some of the nesting use cases.

Additional context

This solution was used in other crates such as crossbeam

[jakobhellermann]

I don't know if its related but std recently figured out how to have a nested thread scope API without having the |s| parameter at every level

thread::scope(|s| {
    s.spawn(|| {
        println!("hello from the first scoped thread");
        s.spawn(|| println!("nested"));
    });
});

https://doc.rust-lang.org/nightly/std/thread/fn.scope.html
https://twitter.com/m_ou_se/status/1501520959433543683

[TheRawMeatball]

That isn't identical to nested scopes, as the nested spawns can still only borrow locals defined outside the outermost scope.

[maniwani]

That isn't identical to nested scopes, as the nested spawns can still only borrow locals defined outside the outermost scope.

Either way would be fine for what I personally need (spawning system tasks from executor task). I should look into what std did.

[MiniaczQ]

I hit an unusual error (in the context of nesting scopes), because of the spawn_local functionality, so I'd like to discuss a fix.
Scope holds LocalExecutor reference which is intentionally !Send + !Sync, which means we cannot nest a reference to it through a spawn call, which has a chance of running it in another thread. Nesting does however work with spawn_local, which runs on the same thread.

So decision has to be made:

• get rid of LocalExecutor and spawn_local
  definitely don't want this
• create a ScatteredScope, which doesn't hold a LocalExecutor reference
  when calling spawn this would replace the original Scope during nesting, it wouldn't implement spawn_local
  this will prevent us from doing the argumentless closure thingy

Do you think there are other options?

[MiniaczQ]

As @maniwani suggested I'll proceed with 3rd solution:
Split (local+global) Scope into LocalScope and (non-local) Scope.
LocalScope::spawn will be able to use both scopes in it's nesting
Scope::spawn will only use Scope in it's nesting
example:

pool.scope(|scope, local_scope| {
    let local_task = |scope, local_scope| async {
        let nested_local_task = |scope, local_scope| async {
            /*...*/
        };
        local_scope.spawn(nested_local_task(scope, local_scope));

        let nested_task = |scope| async {
            /*...*/
        };
        scope.spawn(nested_task(scope));
    };
    local_scope.spawn(local_task(scope, local_scope));

    let task = |scope| async {
        let nested_task = |scope| async {
            /*...*/
        };
        scope.spawn(nested_task(scope));
    }
    scope.spawn(task(scope))
});

[hymm]

As a note you can do nested spawns this way with the current API.

fn test_nested_scopes() {
        let pool = Arc::new(TaskPool::new());
        pool.clone().scope(|scope| {
            scope.spawn_local(async move {
                pool.scope(|scope| {
                    scope.spawn(async move {

                    });
                });
            });
        });
    }

This isn't ideal as the parallel executor would have to run on a locally spawned thread and non send systems would end up blocking the spawning of parallel tasks. It would be preferred if we could have nested spawning instead.

I don't think the mutex approach taken in #4343 can work. To drive the tasks forward we need to take a lock on the tasks which will prevent the currently running tasks from spawning any new tasks.

The work from @TheRawMeatball https://github.com/hymm/bevy/blob/taskpool-scope-shenanigans/crates/bevy_tasks/src/task_pool.rs is promising. I cleaned up a couple things on my branch, but I don't think we can use channels to pass the results as it doesn't have a stable ordering and there are some tests that expect it to be stable. (i.e. the order that tasks are queued in is the order the results are returned).

I'll probably keep poking at this a bit more and see if I can come up with something that has a stable order.

[TheRawMeatball]

Alternatively, we could simply remove the stable order guarantee? Furthermore, it might actually be necessary to remove this guarantee as when tasks can be spawned from multiple threads at once ordering is bound to be lost anyways.

[hymm]

The place where stable ordering would be important is with ParallelIterator, ParallelSlice and ParallelSliceMut traits. They use the scope API internally. As they're not implemented anywhere right now, I'm not sure how important it is. But if we would want to implement these traits again or use scope for a similar API, then not returning a stable ordering would block that.

Internally bevy doesn't depend on scope returning a stable ordering. Most uses don't expect any data to be returned. The one usage where it does return data is in the gltf loader and that promptly uses for_each.

I do agree that as soon as you start using nested spawns any stable ordering is thrown out the window. We would only be able to guarantee a stable ordering in cases where you only spawn things directly from the closure.

[TheRawMeatball]

Then personally I'd prefer simply removing the ParallelSlice iterator etc. as they can't really be used anyways and move forward. We can think about a stable-ordered alternative later on when we need it.

[hymm]

Progress Update

I have a branch with concurrent_queue instead of using channels to maintain the ordering. https://github.com/hymm/bevy/tree/nested-scopes. Perf wise it's pretty close to main except on the cases of 0 to 1 spawns.

https://github.com/hymm/bevy/blob/taskpool-scope-shenanigans/ has an issue where all the tasks aren't completing in time when I use nested spawns in one of my tests.

Both approaches have some UB too. Turns out that sticking Scope into an Arc improperly extended the lifetime of the scope object. I can pass the scope into a thread not on the scope and things still compile. Also tried transmuting lifetimes and passing an &Scope, but that has the same issue. Going to take a look tonight at what std::thread::scope is doing and hopefully get inspiration from there on how to fix the lifetimes.

// this test should fail to compile
// TODO: once it does fail move it to a compile fail doc test.
#[test]
fn compile_fail() {
    let pool = TaskPool::new();
    let foo = Box::new(42);
    pool.scope(|scope| {
        std::thread::spawn(move || {
            // UB. This could spawn on the scope after `.scope` returns and the internal Scope is dropped.
            scope.spawn(async move {
                assert_eq!(*foo, 42);
            });
        });
    });
}