par_sort 比 sort 还慢

主线位置：主线 2 之外，slice 上的并行算法。实验和算法来源在 并行排序。

flowchart TB
  ps["par_sort(v)"] --> l1{"len ≤ 2000？"}
  l1 -->|是| seqm["调用线程上顺序归并（std 旧版算法）"]
  l1 -->|否| chunks["每 2000 个一块并行排序，再 join 归并"]
  pu["par_sort_unstable(v)"] --> part["调用线程上分区一次"]
  part --> l2{"某一边 > 2000？"}
  l2 -->|否| seqq["继续顺序 pdqsort"]
  l2 -->|是| jn["join 两边"]

现象

把 v.sort() 换成 v.par_sort()（或 sort_unstable 换成 par_sort_unstable），小数组上明显变慢；大数组上也只快 3 倍左右，远不到核数。

复现

实验 E9（exp-rayon/par-sort/），随机 u64，5 次中位数，12 线程，1 / 5 分钟负载 1.69 / 2.96。括号里是 std / rayon，大于 1 表示 rayon 快：

在 1 线程池里 par_sort 只有 sort 的 0.28–0.31 倍、par_sort_unstable 是 sort_unstable 的 0.48–0.52 倍，各个 n 都一样。用计数比较函数统计：n ≤ 2000 时两种并行排序的比较全部发生在调用线程上，worker 上是 0。

从哪来

两件事叠在一起：

1. 小数组不并行。 par_sort 在长度 ≤ 2000（CHUNK_LENGTH）时直接顺序归并排序；par_sort_unstable 只在分区后某一边 > 2000（MAX_SEQUENTIAL）时才 join。所以 10³ 时慢 1.6–3.3 倍和并行调度无关。
2. 顺序部分是旧算法。 src/slice/sort.rs 的文件头写「mostly copied from the core::slice::sort module」，对照之后它保留的是 std 换成 driftsort / ipnsort 之前的 pdqsort 和类 TimSort 归并；本机 std 1.99.1 已经是新实现（并行排序）。1 线程时的 0.3 / 0.5 倍就是这个差距。大数组上 12 线程相对自己的 1 线程有 9.5 / 6.7 倍，对 std 只剩 3 倍左右，因为起点慢了 2–3.5 倍。

另外 par_sort_unstable 的第一次分区在调用线程上顺序完成（n = 10⁶ 时调用线程上恰好 n + 13 次比较），已排序输入还会在调用线程上跑一遍 partial_insertion_sort：已排序的 10⁷ 个元素上它比 sort_unstable 慢（4.2 对 3.0 ms）。

怎么改

• 10⁵ 以下用 std：sort / sort_unstable。可以写一个按长度切换的小函数。
• 10⁶ 以上再用 rayon，并且优先 par_sort_unstable（不分配，本机约 3.5 倍）；需要稳定排序时 par_sort 约 3 倍，多一份 n 个元素的缓冲。
• 比较或取键很贵时收益会更大（排序算法的差距被比较开销稀释，本页没实测，属推测）；键要计算的用 par_sort_by_cached_key，键只算一次且并行算。
• 排序只是更大计算的一部分时，考虑先把数据分成线程数个块，各块用 std 排序（par_chunks_mut(..).for_each(|c| c.sort_unstable())），再自己合并；这样顺序部分用的是 std 的新算法。合并是否划算要实测。

小结

• n ≤ 2000 时 rayon 的两种并行排序都不进池，慢 1.6–3.3 倍完全来自顺序算法：rayon 保留的是 std 旧版算法（E9）。
• 大数组上 12 线程约 3 倍（稳定）/ 3.5 倍（不稳定）于 std，相对自己的 1 线程 9.5 / 6.7 倍。
• 10⁵ 以下用 std，10⁶ 以上用 par_sort_unstable；中间按实测定。