Rayon: Parallel iterator inside a map closure where the map is part of a parallel iterator. Possible?

[gbutler69]

Is it possible to perform iteration using Rayon inside a map closure that is already part of a Rayon parallel iteration or will this result in potential deadlock as the task may be put on the Rayon work queue but never gotten to because the task that is waiting for it never finishes while waiting?

In other words, is it OK to do this? As follows:

let vec1 = vec![ .... ];
let vec2 = vec![ .... ];

vec1.par_iter().map(|v1| v2.par_iter().map(|v2|some_computation(v1,v2)).first());

The above is an incredibly simplified version of what I'm doing, but, the compiler seems to be allowing it. I can't help but feel that it is a possible dead-lock though.

Thoughts? Guidance?

[mbrubeck]

Rayon's work queues are lock-free, so there should be no deadlocks possible here, as long as some_computation doesn't perform any explicit locking using std::sync::Mutex or similar.

When you spawn new parallel tasks within an existing task, they will all initially go onto the current worker's queue, and that worker thread will process them one after the other. Additionally, if other worker threads run out of tasks, they may steal the tasks and begin working on them sooner.

[gbutler69]

OK, I understand how the work-stealing works; however, I'm concerned this can happen:

1. The outer parallel iterator spawns a work-queue for each CPU Core/Hyperthread
2. A task is put on the work-queues for the outer iterator (all of them)
3. The inner iterator creates tasks which go on the work queues
4. None of the outer tasks progress because they are waiting for the inner tasks to complete, but, those tasks are on the queues waiting for the outer tasks to complete

Now, this might not happen often due to timing, but, I wonder if it is possible to occur like that or is there some kind of inner-queues or something that prevents it. Am I thinking about it wrong?

[cuviper]

Yes, it's generally fine to nest parallel iterators like this. Behind the scenes, these iterators are themselves just a bunch of nested rayon::join calls.

You can get into trouble if you block rayon threads in a way that causes task inter-dependencies. For instance, if you grab a mutex and spawn more rayon work, while other rayon tasks may try to grab the same mutex, work stealing may end up nesting these on the stack in a deadlock. (e.g. rayon#592)

[mbrubeck]

I think the key thing to note is that a worker never needs to wait on another thread to do a task that it depends on. It will do the task itself, if nobody else gets to it first, and then continue executing the code that depends on that task.

[gbutler69]

Ah, yes, that makes sense. I thought I was missing something in my thought process but couldn't put my finger on it. Thanks for the clarification!