fork-join：fork所有子任务或者为当前线程留一个

Question

我正在尝试了解 fork-join 工作原理的细节。

维基百科有以下合并排序示例，其中左半部分被分叉，右半部分由当前线程处理。

mergesort(A, lo, hi):
    if lo < hi:                     // at least one element of input
        mid = ⌊(hi - lo) / 2⌋
        fork mergesort(A, lo, mid)  // process (potentially) in parallel with main task
        mergesort(A, mid, hi)       // main task handles second recursion
        join
        merge(A, lo, mid, hi)

然而，我见过的大多数 Java 示例都会分叉所有子任务并等待它们的结果：

for (Document document : folder.getDocuments()) {
    DocumentSearchTask task = new DocumentSearchTask(document, searchedWord);
    forks.add(task);
    task.fork();
}
for (RecursiveTask<Long> task : forks) {
    count = count + task.join();
}
return count;

维基百科的例子对我来说更有意义，因为线程会做一些有用的事情而不是阻塞和等待子任务。

另一方面，如果我们fork所有的任务，我们就避免了递归，得不到WhosebugError.

拆分任务的首选方式是什么？为什么？

Answer 1

我会说首选的方法是分叉并以相同的方式处理所有子任务。以下是几个原因：

ForkJoinPool 在 Java 实现 ExecutorService。请注意，ExecutorService 中的所有方法都是 异步的 。这是有原因的——你通常可以在后台异步生成一些计算，而你的主线程可以做一些其他有用的工作，直到它需要计算结果，例如产生更多的异步任务。
比较容易推理。如果您以相同的方式处理所有子问题，而不是在任务中引入某种不对称性，代码通常看起来会更清晰。
不分叉并在主线程上进行部分计算并没有任何优势。如果你fork所有任务然后等待加入，你的主线程处于等待状态，几乎不消耗资源，工作线程可以充分利用处理器。

不过，这更像是一个偏好问题，而不是一个严格的选择。除了您提到的潜在堆栈溢出外，它们在功能上是等效的。

我不能代表维基百科的作者，但我的猜测是她要么试图让事情变得简单以便解释，要么她有不那么抽象的语言背景，其中 forking/joining 不像Java.

更新： 关于太多线程阻塞，这与 ForkJoinPool 无关。正如 here 所解释的，ForkJoinPool 的特殊之处在于工作窃取确实发生在 join 调用中。

fork-join：fork所有子任务或者为当前线程留一个

Fork-join: fork all subtasks or leave one for the current thread

java

fork-join