Support for fork join pattern with multiple parallel tasks in Rayon

[godmar]

In Java's FJP, using ForkJoinTask, I can program in this pattern:

futures = []
for task in tasks:
   futures.push(pool.submit(task))

for future in futures:
   answer = combine(answer, future.join())

This is the pattern I would ordinarily apply for instance for a parallel backtracking problem where I have to spawn tasks at decision points. I need to apply this pattern recursively, and expect the framework to implement helping.

How would I express this pattern in Rayon/does Rayon support this type of dynamic task parallelism?
Thanks.

ps: I have seen the rayon::join function, but it supports spawning only two tasks.
If I were to use rayon::join, I'd be forced to rewrite my app to do

rayon::join(|| { first_task() }, || { recurse_on_remaining_tasks() })

which would require a complete refactoring of my existing backtracking code, which is written in this style:

for o in options:
   partial_result = try_out_option(o)
   answer = combine(answer, partial_result)

[godmar]

To follow up on my own question, I was able to find a partial but not efficient solution using .par_iter_mut():

tasks = []
for o in options:
    tasks.push(Task::new(with option o))

tasks.par_iter_mut().map(|t| { t() }).combine();

However, it's not efficient - I need to create all tasks before I can spawn any of them, losing parallelism.

Without being able to explicitly fork a task, I would need to turn my logic into something that implements std::iter::Iterator, which would require a complete rewrite of the logic and wouldn't be ergonomic. (I understand Rust doesn't (yet?) support generators/yield.)

[adamreichold]

Without being able to explicitly fork a task,

This might be too simple, but perhaps you are looking for spawn et al? You need to add your own mechanism to communicate the results, but usually channels will do.

[godmar]

spawn + channels will not work here because these tasks are recursive, and the worker thread collecting the results must help in their execution. (It would be the equivalent of calling receive on a channel and then finding and inline-executing the task that will produce the matching send - something that's not possible.)

[cuviper]

Can't those recursive tasks call join, or reduce their own ParallelIterator? (the latter is all built on join anyway)

[godmar]

The way I understand it:

• calling join (as in Rayon's join, not std::thread's) means that the task won't be spawned until join is called. Ditto for the form of join that spawns two tasks. Plus, the thread calling join will not return until the task is done, meaning that it cannot spawn more tasks while the first 2 are in progress. This is why I surmised it might require a pattern like rayon::join(|| { first_task() }, || { recurse_on_remaining_tasks() }) (see above.)

• yes, they can reduce the ParallelIterator, as my example shows. However, using par_iter_mut, when applied to a collection such as a vector of tasks, won't spawn any of them until the tasks vector is completely filled and .par_iter_mut() is invoked. During this time, no tasks are available for other workers to steal (at least initially, once all workers are busy it probably won't matter since there would be no idle worker that could pick up any spawned tasks anyway). (If Rayon supported an explicit fork operation, tasks could be worked on as soon as they are forked.)

• To avoid that, I believe would have to implement an iterator myself and use it instead of the tasks vector (I'm assuming that the parallel iterator would then have idle workers draw from this iterator and spawn tasks as soon as the iterator makes them available, probably subject to the availability of idle workers. Just my guess). However, refactoring the existing loop-based code to conform to Rust's iterator protocol would be cumbersome in my opinion, equivalent to manually transforming a generator-style loop that yields values into a state-machine based iterator. Such a refactoring is certainly possible by extracting all local variables and restoring them on each call to .next(), saving them at the end, but I consider it perhaps not ergonomic because of the amount of refactoring required. (PS: I believe .par_bridge() would allow that by linking an ordinary iterator to a parallel iterator.)