inclusive_scan：C++17 里那个悄悄变快的前缀和“并行加速器”

上周帮同事调一个实时信号处理模块，发现单线程累加一万个浮点数组耗时 80 多微秒——不算多，但放在每毫秒要跑上百次的 pipeline 里，就成了瓶颈。他试过手写 OpenMP 循环，结果因依赖关系出错；我也差点建议他切分再合并……直到翻到 <numeric> 里那个不起眼的 inclusive_scan。

它不是新玩具，却是被低估的实干派。

inclusive_scan 做一件事：对序列做含自身的前缀操作（默认加法），生成新序列，其中第 i 项 = op(init, op(...op(init, a[0]), a[1]), ..., a[i])。名字里的 inclusive 就是强调“算上自己”——区别于 exclusive_scan 的“不算自己”。它不光能求前缀和，还能求前缀积、前缀最大值、甚至自定义逻辑（比如按时间戳累积状态）。

关键在 C++17 引入的并行执行策略：你只需传个 std::execution::par_unseq，编译器+标准库就可能把任务拆给多个线程，且自动处理数据局部性与归约同步。这不是“理论上支持”，而是 GCC 12+、Clang 14+、MSVC 2022 在开启 -O2 -march=native 后实打实能飞起来的路径。

但直接套用会踩坑。我第一次改完，性能反而降了 15%——因为原数组才 256 个元素。并行开销不是零：线程创建、任务分片、结果合并，这些在小规模数据上反成累赘。后来划了一条经验线：整型/浮点数组长度 ≥ 2000，或每个元素计算成本较高（如自定义函数含分支/查表），才值得开并行。低于这个量级，inclusive_scan(first, last, out, std::plus{}) 默认串行反而更稳。

真正让它“活”起来的，是和现代硬件特性的咬合。比如，当操作是 std::plus<double>，编译器可能把多个加法打包进 AVX-512 指令；而 par_unseq 策略允许库实现跳过部分同步屏障——前提是你的操作满足无副作用、可重排、可交换结合律。注意：std::max 满足，std::minus 不满足（减法不可交换），lambda [&](auto& a, auto b) { log("add"); return a + b; } 更不行（有副作用）。并行安全不是靠自觉，是靠契约。

实战中，我们把一段音频包络提取逻辑从手写循环换成：

std::vector<float> env(input.size());
std::inclusive_scan(
    std::execution::par_unseq,
    input.begin(), input.end(),
    env.begin(),
    [](float a, float b) { return std::max(a, std::abs(b)); }
);

输入是 128k 采样点的 float32 音频帧。结果：从 1.2ms 降到 0.43ms（i7-12800H，8 性能核全负载）。提速近三倍，代码行数减半，且不再需要手动管理线程局部缓存或归约锁。

这里有个容易被忽略的细节：inclusive_scan 不修改原容器，输出必须另配空间。有人图省事写 inclusive_scan(..., input.begin())，结果覆盖原始数据——尤其当输入输出迭代器重叠时，行为未定义。我们后来统一加了静态断言：

static_assert(!std::is_same_v<std::decay_t<decltype(*input.begin())>,
                              std::decay_t<decltype(*env.begin())>> ||
              input.data() != env.data(),
              "in-place inclusive_scan is unsafe");

它不解决所有问题。比如你需要前缀和的同时还要知道“哪个位置首次超过阈值”，inclusive_scan 只管算，不提供中断机制——这时得配合 std::find_if 或手写带 early-exit 的并行扫描（用 tbb::parallel_scan 或自建分治）。但它把最通用、最易出错的那部分（跨线程依赖处理）彻底封装掉了。

另一个增量认知：inclusive_scan 的并行效率，和内存访问模式强相关。我们曾用它处理链表式结构体数组（每个元素含指针），速度还不如串行——因为 cache line 跳跃太大。改成 AoS 改为 SoA（把 x, y, z 分成三个连续 float 数组），同样数据量，并行加速比从 1.1 提升到 2.8。算法再好，也得让 CPU 缓存愿意配合。

最后说句实在话：别把它当成银弹。如果你的场景是“每次只扫几十个数”，或者“操作本身就很慢（比如调用一次网络请求）”，那它帮不上忙。但它精准卡在“数据够大、操作够轻、依赖够纯”这个黄金三角里——而这恰恰覆盖了科学计算、音视频处理、实时金融风控里大量真实子任务。

现在我看到需要累积计算的地方，第一反应不是开线程池，而是摸 #include <numeric>，敲 std::inclusive_scan，再掂量下数据规模和操作性质。它不炫技，不抢镜，但每次调用，都像拧紧一颗早已备好的螺丝——严丝合缝，静默承重。