承接的问题
12.1 和 12.2 都用到了分治，但都绕开了一个数字：切到多小为止。RecursiveTask 把这个决定交给写代码的人，parallelStream 替你做了决定但不告诉你。这个数字同时影响三件事：
- 任务数量：叶子数约等于
n / threshold，每个任务都是一次对象分配加两次队列操作； - 单任务成本：叶子里的算法在这个规模下是否还高效；
- 并行收益：每个 worker 分到的活够不够多，窃取是否还有意义。
这一节用归并排序把阈值扫一遍，量出「太小」和「太大」各自的代价，然后补齐分治里最容易忽略的两块语义：异常怎么传播、取消到底取消了什么。
阈值决定两件事
先看任务数。一个长度为 n 的数组，每次对半切，切到长度不超过 threshold 为止：
| 阈值 | 叶子数 n/threshold | 递归深度 log2(叶子数) | 任务对象总数（约） |
|---|---|---|---|
| 1 | 1 000 000 | 20 | 2 000 000 |
| 16 | 65 536 | 16 | 131 072 |
| 256 | 4 096 | 12 | 8 192 |
| 4 096 | 256 | 8 | 512 |
| 65 536 | 16 | 4 | 32 |
每个任务都要分配对象、fork 进队列、join 时同步。按本机实测折算，一个任务的固定开销在几十纳秒量级——单看不多，乘以两百万就是上百毫秒。
再看叶子成本。叶子不是「什么都不做」，它要做一段顺序计算。如果叶子算法是 O(k²) 的插入排序，阈值从 16 涨到 65536，单叶子的比较次数涨了 1600 万倍：
插入排序的比较次数 ≈ k² / 4
k = 16 → 64 次
k = 4096 → 4.2 × 10^6 次，乘 256 个叶子 ≈ 1.1 × 10^9
k = 65536 → 1.07 × 10^9 次，乘 16 个叶子 ≈ 1.7 × 10^10
所以阈值不是「越大越省调度」，它同时被叶子算法的复杂度卡住。最优阈值 = 任务开销与叶子计算成本曲线的交点，而这两条曲线的形状取决于你叶子里的代码，没有通用答案。
带阈值的归并排序长这样：
import java.util.concurrent.RecursiveAction;
public final class SortTask extends RecursiveAction {
private final int[] a;
private final int[] tmp;
private final int lo;
private final int hi;
private final int threshold;
public SortTask(int[] a, int[] tmp, int lo, int hi, int threshold) {
this.a = a;
this.tmp = tmp;
this.lo = lo;
this.hi = hi;
this.threshold = threshold;
}
@Override
protected void compute() {
if (hi - lo <= threshold) {
insertionSort(a, lo, hi);
return;
}
int mid = (lo + hi) >>> 1;
invokeAll(new SortTask(a, tmp, lo, mid, threshold),
new SortTask(a, tmp, mid, hi, threshold));
merge(a, tmp, lo, mid, hi);
}
private static void insertionSort(int[] a, int lo, int hi) {
for (int i = lo + 1; i < hi; i++) {
int v = a[i];
int j = i - 1;
while (j >= lo && a[j] > v) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = v;
}
}
private static void merge(int[] a, int[] tmp, int lo, int mid, int hi) {
System.arraycopy(a, lo, tmp, lo, hi - lo);
int i = lo;
int j = mid;
int k = lo;
while (i < mid && j < hi) {
a[k++] = (tmp[i] <= tmp[j]) ? tmp[i++] : tmp[j++];
}
while (i < mid) {
a[k++] = tmp[i++];
}
while (j < hi) {
a[k++] = tmp[j++];
}
}
}
两处细节决定了它是否正确：
a和tmp都是共享数组，但每个任务只写自己的[lo, hi)。左半和右半的区间不相交，所以不需要锁；合并阶段父任务独占[lo, hi)，此时两个子任务都已join完成。invokeAll会先fork一个再算另一个，不是两个都fork后干等。join时的可见性由ForkJoinTask内部的同步保证，父任务看到的是子任务写入后的数组。
本机实测：阈值扫掠
环境：Apple M1 Pro，10 核，32 GB，Temurin 25.0.5+8。测量时 load averages 约 280（机器上还有别的实验），所以只看同一轮内的相对关系。数组长度 100 万，随机 int，每个阈值预热一轮后取四轮，并校验排序结果。
availableProcessors = 10
n = 1000000, loadAverage = 280.58984375
threshold=1 leaves=1000000 maxDepth=20 runs=[142, 134, 127, 140] median=140ms
threshold=16 leaves=65536 maxDepth=16 runs=[36, 21, 21, 21] median=21ms
threshold=256 leaves=4096 maxDepth=12 runs=[21, 22, 22, 23] median=22ms
threshold=4096 leaves=256 maxDepth= 8 runs=[105, 101, 97, 101] median=101ms
threshold=65536 leaves=16 maxDepth= 4 runs=[1636, 1525, 1610, 1629] median=1629ms
sequential merge sort runs=[104, 105, 108, 104] median=105ms
Arrays.sort runs=[59, 59, 59, 59] median=59ms
Arrays.parallelSort runs=[13, 10, 10, 9] median=10ms
读法：
- 曲线是 U 形，但两侧的成因完全不同。 左侧（阈值 1）是任务开销：约 200 万个任务，比阈值 16 多了约 120ms，折算每个任务几十纳秒。右侧（阈值 4096、65536）是叶子算法退化：任务数明明更少，耗时却从 21ms 涨到 101ms 和 1629ms。
- 最优区间是 16–256，都是 21–22ms，相对顺序版 105ms 约 5 倍加速。10 核机器上 5 倍不算高，原因是归并的合并阶段是串行内存操作，而且高负载下 worker 拿不到满额 CPU。
- 阈值 16 和 256 几乎没差别，说明在这个区间里任务开销和叶子成本都不占主导。工程上选 128 或 256 这种「一个 cache line 友好的块」比精确调参更实际。
- 手写版打不过
Arrays.parallelSort（21ms vs 10ms）。JDK 的小数组用双枢轴快排、合并阶段也做了优化，这个例子是教学实现，不是性能基准。
阈值的选择可以按这个顺序做：
- 先让叶子里的算法在「几百到几千个元素」规模上是线性的（快排、插入排序在小数组上表现好，但别用到几万）。
- 用
n / threshold估任务数，确保「任务数 » 并行度」，否则 worker 分不到活。100 万元素、10 核，叶子数在 1000 以上比较稳妥。 - 实测扫三档（比如 64、256、1024），选拐点，不要凭直觉写死。
异常传播：join 是一个重抛点
分治里的异常有两个容易踩的坑：兄弟任务不会自动取消，以及异常跨线程后会被重新包装。
FailingSum left = new FailingSum(lo, mid, ...);
FailingSum right = new FailingSum(mid, hi, ...);
left.fork();
Long r;
try {
r = right.compute();
} catch (RuntimeException e) {
left.cancel(false); // 不写这一行，左半会继续跑完
throw e;
}
return r + left.join();
本机实测（1024 个元素、阈值 16、共 64 个叶子，故意让第 500 号元素所在分片抛异常，三次运行）：
未取消兄弟: java.lang.IllegalStateException: java.lang.IllegalStateException: java.lang.IllegalStateException: bad shard [496,512)，异常后叶子共执行 64/64 个
显式取消兄弟: java.lang.IllegalStateException，异常后叶子共执行 57/64 个
已取消任务的 get(): java.util.concurrent.CancellationException
cancel(true) 返回 true，子任务完成后 finished=1（取消不会中断正在执行的叶子）
三次运行里，不取消兄弟时都是 64/64，显式取消后是 57/57/61。差异不是随机的：fork 出去的任务只要已经开始执行，cancel 就只能改状态，不能把它从栈上拽下来。
顺带对比一下：如果用 invokeAll(left, right)，框架在检测到异常时会主动 cancel(false) 另一个分片，不需要你写 catch。上面这段手写 fork/join 没有这层兜底——这正是「用库的封装」和「自己控制」的差别。
为什么消息会嵌套两层？ 这不是你的代码包出来的。ForkJoinTask.getException() 的逻辑是：如果记录的异常不是当前线程抛出的，就反射找一个 (Throwable) 构造器，新建一个同类型异常、把原异常设为 cause，目的是给出「在当前线程重抛」的准确堆栈。跨两次线程边界就套两层，最底下的 cause 才是原始异常。所以：
catch (RuntimeException e) {
Throwable root = e;
while (root.getCause() != null) {
root = root.getCause();
}
// root 才是真正抛出的那个
}
异常类型会保留，消息会被改写。日志里看到三层 IllegalStateException: 前缀时，不要去搜「谁会抛这个嵌套异常」，它是 JDK 造的。
取消：标记，不是中断
ForkJoinTask.cancel(boolean) 的基类实现只看状态位，mayInterruptIfRunning 参数根本没用上：
public boolean cancel(boolean mayInterruptIfRunning) {
int s = trySetCancelled();
return (s >= 0 || (s & (ABNORMAL | THROWN)) == ABNORMAL);
}
但这里有一个反直觉的差别，本机实测：
submit(Runnable): cancel=true, outcome=interrupted, interruptedFlag=true
RecursiveAction: cancel=true, outcome=finished-normally
同样是 cancel(true)：通过 pool.submit(Runnable) 提交的任务被中断了，而自己继承 RecursiveAction 的任务跑完了。原因是前者被包装成 JDK 内部的 InterruptibleTask，它重写了 cancel 并调用 interruptIfRunning；后者走的是基类实现，只置状态位。
所以对自定义的 RecursiveTask / RecursiveAction：
cancel之后join()抛CancellationException，isCancelled()为真；- 已经进入
compute()的叶子不会停，它会把这段算完； - 想让叶子尽早退出，必须在叶子的循环里自己检查
isCancelled()或中断标志。
这也是分治取消的实践建议：取消要自上而下传播，执行要自下而上检查。父任务 cancel 后，子任务如果还没开始，fork 时会被跳过；已经开始的那部分只能靠代码自觉。
在 libraryd-conc 里落地
借阅系统要生成「即将到期」列表：把当天的借阅快照按 dueAt 排序，取最早的一批发提醒。快照可能有几十万条，排序是纯 CPU 活，适合分治。
package com.plume.conc.core;
import java.time.Instant;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
public final class LoanDueSorter {
private static final int THRESHOLD = 256;
private static final Comparator<Loan> BY_DUE =
Comparator.comparing(Loan::dueAt).thenComparing(Loan::loanId);
private final ForkJoinPool pool = new ForkJoinPool(4);
private static final class SortTask extends RecursiveAction {
private final Loan[] items;
private final Loan[] tmp;
private final int lo;
private final int hi;
SortTask(Loan[] items, Loan[] tmp, int lo, int hi) {
this.items = items;
this.tmp = tmp;
this.lo = lo;
this.hi = hi;
}
@Override
protected void compute() {
if (hi - lo <= THRESHOLD) {
for (int i = lo + 1; i < hi; i++) {
Loan v = items[i];
int j = i - 1;
while (j >= lo && BY_DUE.compare(items[j], v) > 0) {
items[j + 1] = items[j];
j--;
}
items[j + 1] = v;
}
return;
}
int mid = (lo + hi) >>> 1;
invokeAll(new SortTask(items, tmp, lo, mid),
new SortTask(items, tmp, mid, hi));
merge(lo, mid, hi);
}
private void merge(int lo, int mid, int hi) {
System.arraycopy(items, lo, tmp, lo, hi - lo);
int i = lo;
int j = mid;
int k = lo;
while (i < mid && j < hi) {
items[k++] = BY_DUE.compare(tmp[i], tmp[j]) <= 0 ? tmp[i++] : tmp[j++];
}
while (i < mid) {
items[k++] = tmp[i++];
}
while (j < hi) {
items[k++] = tmp[j++];
}
}
}
public List<Loan> sortByDueAt(List<Loan> snapshot) {
Loan[] items = snapshot.toArray(Loan[]::new);
if (items.length > 1) {
pool.invoke(new SortTask(items, new Loan[items.length], 0, items.length));
}
return List.of(items);
}
public void close() {
pool.shutdown();
}
}
四点说明：
- 排序的是快照数组，不是
LoanRepository。分治任务里不能查库；Loan是 record，取出dueAt和loanId后不可变，切片之间没有共享写。 - 比较器必须无副作用且可重复调用。
BY_DUE是静态常量，并加了loanId作为决胜键：归并排序本身是稳定的，相同dueAt会保留输入顺序；再加一层loanId是为了让结果与输入顺序无关，便于对账和重跑。 - 阈值 256 是在 100 万规模上量出来的，几十万条数据下叶子数仍有上千，能把 4 个 worker 喂饱；如果快照只有几千条，直接用
List.sort更划算。 List.of(items)返回不可变副本，防止调用方在排序后改动数组；如果调用方要按「最早到期」截断，再subList即可。
什么时候不要用
- 数据量不够大。叶子数少于并行度的几倍时，拆分和合并的成本高于收益。几千条记录的排序用
List.sort就够了。 - 叶子里的算法不是线性的。插入排序、冒泡排序在阈值上千后会退化成平方复杂度，实测 65536 的阈值让总耗时涨到 21ms 的 77 倍。
- 需要稳定的全局顺序且比较器有大量并列。并行合并的顺序由树形决定，并列元素的相对顺序与顺序流未必一致。
- 任务里要做 IO 或加锁。分治的收益来自「每片独立算」，一旦共享资源，worker 会互相等。
- 需要精确的取消或超时。
cancel停不下正在执行的叶子，也没有超时机制；这种需求用Future/虚拟线程更合适。
常见错误与边界
| 错误 | 后果 | 正确做法 |
|---|---|---|
| 阈值设成 1 | 任务数等于元素数，分配与调度吞掉收益 | 叶子保留几百到几千个元素 |
| 阈值设得过大且叶子用插入排序 | 叶子退化为 O(k²)，实测 1629ms | 叶子算法与阈值一起选 |
共享 tmp 数组但切片重叠 | 数据竞争，结果错乱 | 保证每个任务只写自己的区间 |
| 子任务失败后不管兄弟 | 已 fork 的任务继续跑，浪费资源 | 捕获后 cancel 兄弟，见上文 |
用 e.getMessage() 判断异常 | 消息可能是嵌套后的 cause.toString() | 沿 getCause() 找到根因 |
以为 cancel(true) 会中断 | 自定义任务照常跑完 | 叶子内检查 isCancelled() |
在 compute 里 System.out | 输出交错、拖慢整体 | 汇总后统一打印 |
| 递归没有深度上限 | 退化输入导致栈溢出 | 加深度上限，超过就顺序处理 |
小结
- 阈值同时决定任务数和叶子成本。本机 100 万元素、10 核：阈值 1 是 140ms（约 200 万个任务），16 是 21ms，256 是 22ms，4096 是 101ms，65536 是 1629ms，顺序版 105ms。左端是调度开销，右端是插入排序的平方复杂度。
- 最优阈值没有通用值，用「任务数 » 并行度」和「叶子算法在 k 规模上仍线性」两条约束先框定，再实测三档选拐点。
- 异常会从
join/invoke重抛，但跨线程时ForkJoinTask会新建同类型异常并把原异常设为 cause，所以消息会嵌套，根因在getCause()链底部。 - 兄弟任务不会自动取消：不取消时 64/64 个叶子全部执行，显式
cancel后减到 57–61 个。cancel(true)对自定义RecursiveTask不中断，对submit(Runnable)包装的任务才中断。 Arrays.parallelSort比手写归并快一倍，工程上优先用 JDK 现成的实现；手写分治的价值在于理解阈值与合并逻辑。
第 12 章到此结束。下一章换一个维度：不再关心「怎么把活切开」，而是「怎么把多个异步结果拼起来」——CompletableFuture 的创建、组合与异常。
阅读导航：上一节 12.2 并行流的边界与 commonPool 陷阱 ｜ 下一节 13.1 CompletableFuture 的创建与组合
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。