Parallel runner deadlocks with idling threads in ComputeTaskPool

[farnoy]

Bevy version

0.6.0

Operating system & version

Windows 11

What you did

let mut app = App::new();

app.insert_resource(bevy_tasks::ComputeTaskPool(
    bevy_tasks::TaskPoolBuilder::new().num_threads(1).build(),
));

let a = Arc::new(FairMutex::new(0usize));
let b = Arc::new(FairMutex::new(0usize));
let c = Arc::new(FairMutex::new(0usize));

let set = SystemSet::new()
    .with_system({
        let a = Arc::clone(&a);
        (move || {
            tracing::info!(
                thread_id = format_args!("{:?}", std::thread::current()),
                "A incrementing"
            );
            *a.lock() += 1;
        })
    })
    .with_system({
        let b = Arc::clone(&b);
        (move || {
            tracing::info!(
                thread_id = format_args!("{:?}", std::thread::current()),
                "B incrementing"
            );
            *b.lock() += 1;
        })
    })
    .with_system(
        (move || {
            tracing::info!(thread_id = format_args!("{:?}", std::thread::current()), "C spinning");
            let mut c = c.lock();
            *c += 1;
            while *a.lock() != *c || *b.lock() != *c {}
        }),
    );

app.add_system_set_to_stage(CoreStage::Update, set);

for ix in 0..500 {
    let _span = tracing::info_span!("iteration", ix).entered();
    app.update();
}

What you expected to happen

With the main thread + one more thread in the task pool, this should be completeable regardless of execution order.

What actually happened

It deadlocks after a number of iterations, here's a snapshot of the tracing logs (only the last entries):

  ...

  2022-03-09T00:54:16.833550Z  INFO repro: C spinning, thread_id: Thread { id: ThreadId(1), name: Some("main"), .. }
    at src/main.rs:123
    in bevy_ecs::schedule::executor_parallel::system with name: "repro::main::{{closure}}"
    in bevy_ecs::schedule::executor_parallel::prepare_systems
    in bevy_ecs::schedule::stage with name: Update
    in repro::iteration with ix: 182

  2022-03-09T00:54:16.833562Z  INFO repro: A incrementing, thread_id: Thread { id: ThreadId(2), name: Some("TaskPool (0)"), .. }
    at src/main.rs:104
    in bevy_ecs::schedule::executor_parallel::system with name: "repro::main::{{closure}}"
    in bevy_ecs::schedule::executor_parallel::prepare_systems
    in bevy_ecs::schedule::stage with name: Update
    in repro::iteration with ix: 182

  2022-03-09T00:54:16.834361Z  INFO repro: B incrementing, thread_id: Thread { id: ThreadId(2), name: Some("TaskPool (0)"), .. }
    at src/main.rs:114
    in bevy_ecs::schedule::executor_parallel::system with name: "repro::main::{{closure}}"
    in bevy_ecs::schedule::executor_parallel::prepare_systems
    in bevy_ecs::schedule::stage with name: Update
    in repro::iteration with ix: 182

  2022-03-09T00:54:16.835071Z  INFO repro: B incrementing, thread_id: Thread { id: ThreadId(1), name: Some("main"), .. }
    at src/main.rs:114
    in bevy_ecs::schedule::executor_parallel::system with name: "repro::main::{{closure}}"
    in bevy_ecs::schedule::executor_parallel::prepare_systems
    in bevy_ecs::schedule::stage with name: Update
    in repro::iteration with ix: 183

  2022-03-09T00:54:16.835076Z  INFO repro: C spinning, thread_id: Thread { id: ThreadId(2), name: Some("TaskPool (0)"), .. }
    at src/main.rs:123
    in bevy_ecs::schedule::executor_parallel::system with name: "repro::main::{{closure}}"
    in bevy_ecs::schedule::executor_parallel::prepare_systems
    in bevy_ecs::schedule::stage with name: Update
    in repro::iteration with ix: 183

These logs show a successful iteration (there were 181 more before it), followed by a deadlock which I exited out after waiting a couple of seconds.

[james7132]

In this particular example, it seems like C will deadlock if A and B both do not occur before or after C, or at least allow one of them to run alongside C. Unfortunately the scheduler also has no information about these conditions as the systems both have no inputs nor explicit labeling and scheduled C then A onto thread 2 after B already ran, causing a deadlock. This is likely less of an issue with systems running with more threads, but unavoidable in single threaded environments (like WASM right now). Not sure if we can address this without implementing explicit work-stealing into the TaskPools we have right now.

[farnoy]

Is work stealing a difficult thing to add? I use a more complicated graph with many more threads and run into this whenever I try to be clever with locking. Hitting the issue is a statistical probability even if you have just one interaction like this as part of your bigger stage.

Alternatively, what would satisfy me is the ability to yield in the middle of a System, thus unblocking the runnable System that is assigned to this thread. Introducing async systems seems like a bigger change though.

[james7132]

If possible try to use ECS storage for your data since the scheduler understands the data dependencies there (it can also be faster due to no/few atomic operations being needed). This should alleviate most if not all of the locking you need to do. Spin-locking like this is also probably not advisable given the potential for deadlocks. What use case are you trying to target with this?

Alternatively, you can try using the AsyncComputeTaskPool or IOTaskPool to offload tasks there instead, and just poll for it's completion in normal ECS systems.

[farnoy]

I already use the AsyncComputeTaskPool for another part of my app. Unfortunately, this specific problem requires references to some Resources that I store in my World instance, and I don't want to box all of them in Arc<T> to be able to use them in a 'static context.

I'm working on a Vulkan renderer where I record & submit work to the GPU in an unordered fashion (from the perspective of the CPU). Using data/system dependencies would narrow down opportunities for parallelism. My stage essentially looks like a big fanout - there's some initialization at the start, but after that, I (almost) don't care about the order of execution, just as long as they all complete before proceeding to the next stage (that's implicit in bevy of course).

So, if I do any kind of locking in these unordered systems (I tried a synchronous Condvar so at least I'm not spin locking on a Mutex until it can proceed), I'm blocking the execution of another such system that has all its dependencies met.

[farnoy]

I've created my own parallel executor based on rayon. It was surprisingly easy to do, and I appreciate the fact that ParallelSystemExecutor is exposed.

[farnoy]

Is this still an issue in 0.10? With the introduction of a closed enum in ExecutorKind, I lost my workaround and don't see a path forward.

[james7132]

Might want to test this again, though I don't think the deadlock can be addressed without exposing internal mutability information to the scheduler. Your only bet really is to add explicit system ordering here instead of letting them be run in an ambiguous order.