叉连接：叉所有子任务或为当前线程留下一个

Question

我想了解叉连接如何工作的细节。

Wikipedia对于合并排序有以下示例，其中左半部分是分叉的，右半部分是由当前线程处理的。

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; 

维基百科的例子使我更有意义，因为一个线程会做一些有用的东西，而不是阻止并等待子任务。

另一方面，如果我们分叉所有的任务，我们避免递归，并且不能得到StackOverflowError。

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

Answer 1

我想说的首选方法是叉和对待所有子任务相同的方式。这里有几个原因：

1. ForkJoinPool在Java中实现ExecutorService。请注意，ExecutorService中的所有方法都是异步。这是有原因的 - 你可以经常在后台异步地产生一些计算，而你的主线程可以做一些其他有用的工作，直到它需要计算结果（例如，产生更多异步任务。

2. 这很容易推理。如果以同样的方式处理所有子问题，代码通常看起来更清晰，而不是为任务引入某种不对称。

3. 不分叉和做主线程计算的一部分没有任何优势。如果分叉所有任务，然后等待连接，则主线程处于等待状态，并且几乎不消耗资源，并且工作线程可以充分利用处理器。

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

我不能说维基百科的作者，但我的猜测是，她要么试图保持简单的解释，或者她有一个抽象语言较少的背景，其中分叉/连接不像Java那么简单。

---

更新：关于过多线程阻塞，这不符合ForkJoinPool关注。正如here所解释的那样，关于ForkJoinPool的特别之处在于窃取工作确实发生在join调用中。