java - Fork-join: fork 所有子任务或为当前线程留下一个子任务

Question

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

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

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 示例都会 fork 所有子任务并等待其结果:

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 所有任务，我们就可以避免递归并且无法得到 StackOverflowError。

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

Answer 1

我想说，首选的方法是以相同的方式 fork 和处理所有子任务。原因如下:

Java中的

1. ForkJoinPool实现了ExecutorService。请注意，ExecutorService 中的所有方法都是异步的。这是有原因的 - 您通常可以在后台异步生成一些计算，而您的主线程可以在需要计算结果之前执行一些其他有用的工作，例如产生更多异步任务。

2. 这更容易推理。如果您以相同的方式处理所有子问题而不是在任务中引入某种不对称性，那么代码通常看起来会更干净。

3. 不 fork 并在主线程上执行部分计算实际上没有任何优势。如果你fork所有任务然后等待join，那么你的主线程处于等待状态，几乎不消耗任何资源，工作线程可以充分利用处理器。

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

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

<小时/>

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