Tests fail with stack overflow when in breadth-first mode

How to reproduce:

Go to Registry::new in registry.rs and unconditionally enable breadth-first mode:

let breadth_first = true;

Then run tests with (you may have to run multiple times):

cargo test iter::test::check_cmp_l

Output:

    Finished dev [unoptimized + debuginfo] target(s) in 0.10s
     Running target/debug/deps/rayon-5dd50bb9f566bf60

running 3 tests
test iter::test::check_cmp_lt_to_seq ... ok
test iter::test::check_cmp_lt_direct ... ok

thread '<unknown>' has overflowed its stack
fatal runtime error: stack overflow
error: process didn't exit successfully: `/home/stjepan/work/rayon/target/debug/deps/rayon-5dd50bb9f566bf60 'iter::test::check_cmp_l'` (signal: 6, SIGABRT: process abort signal)

I was first worried that there's a bug in crossbeam-deque. After all, Deque::steal has a custom, optimized version of steal. But if I change calls to Deque::steal with good old Stealer::steal (which should be correct!), the bug is still present:

#[inline]
pub unsafe fn take_local_job(&self) -> Option<JobRef> {
    loop {
        match self.worker.stealer().steal() {
            Steal::Empty => return None,
            Steal::Data(d) => return Some(d),
            Steal::Retry => {},
        }
    }
}

This makes me believe that the bug is actually in Rayon.

[cuviper]

My hunch is that breadth_first is turning O(log n) stack depth into O(n), as you'll end up stealing the biggest outer jobs instead of your smallest, most recently pushed jobs.

Is there anything we could do about it? Stack overflows in breadth-first sound like a potential problem (fortunately, Servo hasn't run into it...)

[cuviper]

IIRC, Servo queues their breadth_first jobs with Scope::spawn, which means they wouldn't have nested execution, unlike join and parallel iterators. If each job completes its work and returns to the Scope's base stack frame, then the stack won't get very deep. It could have a problem if they nest scopes though.

Here's a rather small example that stack overflows in breadth-first mode for me:

#[test]
pub fn stack_overflow() {
    let a = vec![0; 1000];
    let b = vec![0; 1000];
    a.par_iter().cmp(&b);
}

Run with: while cargo test stack_overflow; do true; done

[cuviper]

I assume the loop is because work-stealing randomness doesn't always trigger the problem? And it's probably also OK in --release with inlining, right?

As for actually solving this, I wonder if we could separate things so only Scope::spawn jobs are affected by breadth_first? We'd need deque changes, but if possible I'm thinking we could push_front for such spawns, and then just push and pop normally for everything else. We would not need to self-steal for breadth-first anymore.

If a deque push_front is not feasible, then we could also try this with separate queues - the normal LIFO for stack-oriented jobs (like join) and a FIFO for breadth-first spawns. For other threads work-stealing, they don't even need to know about this, just that there will be twice the number of Stealers to try.

I assume the loop is because work-stealing randomness doesn't always trigger the problem?

Exactly.

And it's probably also OK in --release with inlining, right?

It doesn't stack overflow in --release mode. But if I bump up the vector lengths to 10 million, then it always does.

If a deque push_front is not feasible,

It is feasible in the version of crossbeam-deque rayon is currently using. However, in the latest version the deque can only be FIFO or LIFO (the decision is made in the deque constructor). The addition of the new Stealer::steal_many method prohibits pushing into both ends. We technically could still support pushing into both ends, but... it's a little tricky.

then we could also try this with separate queues - the normal LIFO for stack-oriented jobs (like join) and a FIFO for breadth-first spawns.

I like this idea. We could make rayon::join always depth-first, while rayon::spawn would be depth-first or breadth-first depending on the chosen mode.

Or, I might even suggest deprecating the breadth_first configuration flag and add a new function named rayon::spawn_last (or something like it) that hints to the thread pool that this task should be pushed into the back of the queue. That would give the user strictly more control over how tasks get ordered - one can choose the ordering for each task invocation rather choosing a global mode on thread pool creation.

[cuviper]

Or, I might even suggest deprecating the breadth_first configuration flag and add a new function named rayon::spawn_last (or something like it) that hints to the thread pool that this task should be pushed into the back of the queue. That would give the user strictly more control over how tasks get ordered - one can choose the ordering for each task invocation rather choosing a global mode on thread pool creation.

I like that too.

Our current behavior is already kind of inconsistent though. By default local jobs are LIFO, but stolen jobs are always FIFO -- and this includes the global inject queue! So if you call spawn from outside a threadpool, those jobs will be picked off in FIFO order. But within a threadpool, they'll be locally processed LIFO while other threads steal FIFO.

I guess that's sort of the nature of the beast, but at least a spawn_last can be consistently FIFO.

I'm starting to believe that we don't need both spawn and spawn_last at all...

My hypothesis is that the following is true:

• Calls to join tend to recursively divide jobs into halves that we'd prefer to complete in depth-first order.
• Calls to spawn tend to divide jobs into blocks of equal size that we'd prefer to complete in breadth-first order.

We can think of rayon::join(a, b) as the parallel equivalent of a(); b();.

Now, the key point I'd like to make is that rayon::scope(|s| ...) basically creates a temporary queue named s into which we push parallel jobs. At the end of the scope the queue is drained, thus completing all jobs.

So the choice between join and spawn boils down to whether we want to do classic stack-based function calls in parallel (depth-first order) or create a queue of parallel jobs and drain it (breadth-first order).

My feeling is that there is something fundamental about join being depth-first and spawn being breadth-first.

Is there even a scenario where we really want to use scope and process jobs in depth-first order that can't be rewritten using join?

[cuviper]

I'm starting to believe that we don't need both spawn and spawn_last at all...

I think you're right, especially since the current spawn only acts LIFO/depth-first in the local queue, versus globally-injected or stolen jobs. I think it would be fine to just make it FIFO everywhere.

I'm not sure how to make this properly nest though, which is also not really designed well in the current breadth_first mechanism. The scenario I'm imagining is where you have several layers of join, and within you call scope and a series of spawn. We want those spawns to be processed FIFO, but overall we probably should still try to have that whole scope completed before processing more of its own join jobs.

Same goes for nested scopes -- we probably want to process all of the inner scope before popping more of the outer scope. So the scopes themselves are LIFO, while their spawns within are LIFO with respect to one particular scope.

I don't think coarse FIFO and LIFO queues will accomplish this.

[nikomatsakis]

So, @cuviper and I chatted about this on Gitter. We didn't reach any firm conclusions but we decided that this is a hard problem.

On the question of whether it is "more natural" for spawn to have FIFO priority (within a scope) -- at first I was skeptical, but I think I've come around. I think many applications won't care, but I do see an appeal to being able to map the priority to the sequential order: That is, join(a, b) kind of "prioritizes" as a(), b(), and spawn(a); spawn(b); the same.

One challenge is when you try to compose joins/scopes. Ideally, you would sort of treat each scope as a "single unit" on a stack, within which we push onto a queue, such that when the local job is pulling tasks, it pulls from the front of this queue until it is exhausted, and then pops from the stack. That seems like it's more spec than impl strategy, though, and it's pretty unclear how it would work with stealing.

@cuviper had at some point proposed keeping one LIFO and one FIFO queue per thread and having stealers first pop from the LIFO queue, and then dequeue from the FIFO queue. The problem here is that if you have spawns that use join, stealers will steal from the join first and not the spawn, which is suboptimal.

We both agreed that we could likely get away with changing the behavior of spawn to be FIFO and deprecated the breadth_first flag, though it's hard to know what people are using Rayon for.

[cuviper]

I think we can solve the nesting problem, where there's a mix of LIFO and FIFO concerns, by using a little indirection. My idea is to always consume the thread deque as LIFO, and have a private FIFO deque for each scope. When we get a scope::spawn, we push that job to the scope's deque, and then push a indirect job to the thread deque that steals from the front of the scope deque to execute.

So if there are 10 spawns, there will be 10 jobs on both deques. When the thread looks for its own work, it will pop from the back of the thread deque to then steal from the front of the scope deque. When a different thread comes to steal work, it will steal from the front of the victim's thread deque to then also steal from the front of the scope deque.

This way, even when scopes are nested, a thread will always process its own scopes LIFO while still running their spawns FIFO. And other threads will steal FIFO in all cases. The indirection will of course add some overhead, but I hope that will be inconsequential.