加上 `std::execution::par`，为什么程序既没变快，还可能直接终止？

我们有一段顺序计算：

const auto result = std::transform_reduce(
    values.begin(), values.end(), std::uint64_t{0},
    std::plus<>{},
    [](std::uint32_t value) {
        return std::uint64_t{value} * value;
    });

为了“免费获得多线程”，只增加一个执行策略：

const auto result = std::transform_reduce(
    std::execution::par,
    values.begin(), values.end(), std::uint64_t{0},
    std::plus<>{},
    [](std::uint32_t value) {
        return std::uint64_t{value} * value;
    });

代码确实更像并行版本了，但运行后可能出现三种结果：CPU 使用率没有变化；线程增加了，耗时却更长；lambda 一旦抛异常，原本期待的 catch 没有执行，进程直接进入 std::terminate。

问题不在于标准算法“失效”，而在于执行策略表达的是允许怎样执行，不是对线程数、调度后端和性能收益的承诺。与此同时，一旦允许重排、并行或向量化，用户提供的操作也必须满足更严格的独立性、数值和异常约束。

本文将围绕“为什么加了 par 仍不一定更快”展开，建立一条完整判断链：API 是否可用、实现是否真的并行、工作量是否足够、操作是否能安全重排，以及结果是否仍满足业务要求。

1. 我们遇到了什么问题？

1.1 最短的并行写法也可能包含数据竞争

想把数组元素求和时，初学者很容易把顺序循环机械地换成并行 for_each：

// 错误示例：多个调用并发修改 sum
std::uint64_t sum = 0;

std::for_each(std::execution::par,
              values.begin(), values.end(),
              [&](std::uint32_t value) {
                  sum += value;
              });

不同迭代可能同时执行 sum += value。这个表达式是一次读—改—写，不是原子操作；冲突访问没有同步，程序产生数据竞争，行为未定义。

给 sum 加 mutex 虽然可以消除数据竞争，却把所有迭代重新串在同一临界区，还引入调度和锁开销。更合理的方向不是“修好共享累加”，而是使用能够表达局部归约与合并的 std::reduce 或 std::transform_reduce。

1.2 编译成功不等于已经启用有效并行后端

一条并行算法要真正获益，至少要连续通过四道门：

头文件与重载可用
        |
        v
标准库实现拥有可工作的执行后端
        |
        v
该次调用实际选择了并行执行
        |
        v
工作量收益大于分块、调度、同步和内存开销

任何一层不满足，par 都可能与顺序版本相近或更慢。不同 libstdc++、libc++、MSVC STL 版本及其构建配置可能采用不同后端和链接要求，需要在目标工具链验证。

2. 执行策略到底承诺了什么？

执行策略（execution policy）是传给算法的标签，用于说明实现被允许采用的执行方式。

策略	引入版本	允许的执行方式	用户操作的主要限制
std::execution::seq	C++17	调用线程内按顺序执行	仍应满足算法本身要求
std::execution::par	C++17	可在调用线程或库管理的线程中并行	不得产生数据竞争或依赖迭代顺序
std::execution::par_unseq	C++17	可并行，并在单个线程内无序交错/向量化	不能调用向量化不安全的同步操作
std::execution::unseq	C++20	调用线程内可无序交错/向量化	同样受无序执行限制

最关键的词是“允许”。par 并不承诺：

• 一定创建多个线程；
• 使用多少线程；
• 使用哪个线程池；
• 某个元素先于另一个元素执行；
• 小输入也会并行；
• 比 seq 更快。

实现可根据资源、输入和内部策略退回顺序执行。这保证了算法能在更多环境运行，却意味着线程数与调度策略并不由标准接口直接控制。

2.1 为什么策略不能改变程序含义？

如果把 seq 改成 par 后业务结果的逻辑含义发生变化，通常说明迭代间存在未表达的依赖。例如：

// 错误思路：依赖“前一个元素已更新”
std::for_each(std::execution::par,
              indices.begin(), indices.end(),
              [&](std::size_t i) {
                  values[i] += values[i - 1];
              });

这不是独立的逐元素变换，而是前缀依赖。应使用 scan 类算法，或保留明确的顺序/分阶段实现。执行策略不会自动识别并修复数据依赖。

3. 哪种代码形状适合标准并行算法？

最理想的形状是：输入范围已经存在，每次迭代读取自己的输入，写入唯一输出位置，迭代之间没有可见副作用。

input[i] -- transform --> output[i]
input[j] -- transform --> output[j]

i 与 j 不共享可写状态

例如：

std::vector<float> output(input.size());

std::transform(std::execution::par,
               input.begin(), input.end(),
               output.begin(),
               [](float value) {
                   return value > 0.0f ? value * value : 0.0f;
               });

以下写法则把容器扩容和共享写带进每次迭代：

// 错误示例：push_back 并不是线程安全的唯一输出槽
std::vector<float> output;

std::for_each(std::execution::par,
              input.begin(), input.end(),
              [&](float value) {
                  output.push_back(value * value);
              });

预先分配输出不仅消除共享 push_back，还让写入地址可预测，更利于缓存和向量化。

3.1 不同元素真的代表不同存储位置吗？

对普通 std::vector<int>，不同元素是不同对象；但 std::vector<bool> 是位压缩特化，多个逻辑元素可能共享同一个机器字。并行写不同下标仍可能冲突。

类似风险还包括位图、打包字段、相互重叠的输入输出范围，以及多个索引映射到同一对象。判断并行安全时要看实际存储和别名关系，不能只看下标不同。

4. 如何写出一个可验证的 seq / par 对照？

下面用 std::transform_reduce 计算整数平方和。输入在运行期构造，预期结果由构造过程独立计算；两种策略分别预热并重复 9 次，输出校验和与最小/中位/最大耗时。

这段代码只能告诉你当前机器、标准库、构建选项和输入规模下的表现。它不会证明 par 在所有环境更快。

4.1 运行条件

• 语言标准：C++17；
• 第三方依赖：源码层面没有；
• 构建方式：Release 优化；
• 输入：4 Mi 个取值为 1～100 的 std::uint32_t；
• 结果类型：std::uint64_t，当前规模不会溢出；
• 后端限制：某些标准库版本可能需要额外并行运行时或链接选项，必须结合目标环境验证。

将代码保存为 parallel_algorithms.cpp：

#include <algorithm>
#include <chrono>
#include <cstdint>
#include <execution>
#include <functional>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

using Values = std::vector<std::uint32_t>;

template <class ExecutionPolicy>
std::uint64_t sum_squares(ExecutionPolicy&& policy, const Values& values) {
    return std::transform_reduce(
        std::forward<ExecutionPolicy>(policy),
        values.begin(), values.end(),
        std::uint64_t{0},
        std::plus<>{},
        [](std::uint32_t value) {
            return std::uint64_t{value} * value;
        });
}

struct Report {
    std::string name;
    std::uint64_t checksum;
    double minimum_ms;
    double median_ms;
    double maximum_ms;
};

template <class Work>
Report measure(std::string name,
               const Work& work,
               std::uint64_t expected) {
    constexpr int sample_count = 9;

    if (work() != expected) {
        throw std::runtime_error(name + " failed during warmup");
    }

    std::vector<double> samples;
    samples.reserve(sample_count);
    std::uint64_t checksum = 0;

    for (int i = 0; i < sample_count; ++i) {
        const auto begin = std::chrono::steady_clock::now();
        const std::uint64_t result = work();
        const auto end = std::chrono::steady_clock::now();

        if (result != expected) {
            throw std::runtime_error(name + " produced a wrong result");
        }

        checksum += result;
        const std::chrono::duration<double, std::milli> elapsed = end - begin;
        samples.push_back(elapsed.count());
    }

    std::sort(samples.begin(), samples.end());
    return Report{
        std::move(name),
        checksum,
        samples.front(),
        samples[samples.size() / 2],
        samples.back()
    };
}

void print_report(const Report& report) {
    std::cout << std::fixed << std::setprecision(3)
              << report.name
              << ": checksum=" << report.checksum
              << ", min=" << report.minimum_ms << " ms"
              << ", median=" << report.median_ms << " ms"
              << ", max=" << report.maximum_ms << " ms\n";
}

int main() {
    constexpr std::size_t element_count = std::size_t{1} << 22;

    Values values;
    values.reserve(element_count);

    std::uint64_t expected = 0;
    for (std::size_t i = 0; i < element_count; ++i) {
        const auto value = static_cast<std::uint32_t>(i % 100 + 1);
        values.push_back(value);
        expected += std::uint64_t{value} * value;
    }

    try {
        print_report(measure(
            "seq",
            [&] { return sum_squares(std::execution::seq, values); },
            expected));

        print_report(measure(
            "par",
            [&] { return sum_squares(std::execution::par, values); },
            expected));
    } catch (const std::exception& error) {
        std::cerr << "benchmark failed: " << error.what() << '\n';
        return 1;
    }
}

在支持执行策略重载的工具链上编译：

clang++ -std=c++17 -O2 -DNDEBUG -Wall -Wextra -pthread \
  parallel_algorithms.cpp -o parallel_algorithms
./parallel_algorithms

输出形式如下，固定校验和应一致，时间必须以本机结果为准：

seq: checksum=127722726720, min=<本机结果> ms, median=<本机结果> ms, max=<本机结果> ms
par: checksum=127722726720, min=<本机结果> ms, median=<本机结果> ms, max=<本机结果> ms

如果两个耗时非常接近，不能仅据此判断编译器“忽略了 par”。还要用线程时间线或 profiler 检查是否创建工作线程，并测试更大/更小输入规模。并行版本也可能实际运行了多个线程，却被调度开销或内存带宽抵消收益。

5. 这段代码为什么适合并行归约？

5.1 变换操作没有共享副作用

lambda 只读取参数并返回平方值，不捕获外部可写状态。任意两个调用都可以交换、并发或向量化，不会改变整数结果。

乘法前先转换为 std::uint64_t：

return std::uint64_t{value} * value;

如果两个 std::uint32_t 先相乘，乘法可能在 32 位无符号类型中发生并取模，之后再转成 64 位已经来不及恢复高位。类型宽度是归约正确性的一部分。

5.2 合并操作满足当前数据下的重排要求

std::plus<> 对当前范围内、不溢出的无符号整数求和，分块顺序不会改变最终结果。实现因此可以做：

chunk 0 -> local sum --+
chunk 1 -> local sum --+--> tree reduction -> result
chunk 2 -> local sum --+
chunk 3 -> local sum --+

若结果可能超过 std::uint64_t，无符号加法会按模运算；这可能是定义良好的语言行为，却未必符合业务数学含义。Benchmark 的结果校验不能替代输入范围分析。

5.3 校验在算法调用之外完成

执行策略下用户操作抛异常会触发特殊异常规则，因此 transform lambda 保持不抛。每次算法返回后，普通代码再对结果进行校验并抛 runtime_error，这个异常可以被外层 catch 正常捕获。

预热和 9 个样本只是一套教学用最小测量。严肃性能结论仍应交替候选顺序、多进程重复、记录后端与硬件，并观察完整样本分布。

6. reduce 为什么不等于更快的 accumulate？

6.1 accumulate 是左折叠，reduce 允许重排

std::accumulate 的直观执行顺序是：

(((init op x0) op x1) op x2) op x3

std::reduce 表达 generalized sum，即使不提供执行策略，也允许以不同分组顺序组合：

(init op (x0 op x1)) op (x2 op x3)

这种自由度让树形归约和向量化成为可能，也要求二元操作在实际定义域内适合重排。不要把带副作用、依赖左右参数角色或不满足结合规律的操作传给 reduce。

6.2 浮点加法不满足数学上的结合律

有限精度下：

(a + b) + c  可能不等于  a + (b + c)

因此顺序 accumulate、reduce(seq) 和 reduce(par) 都可能给出末位不同的结果。seq 只限制调用的执行方式，不把 reduce 变回严格左折叠。

如果业务需要逐位可复现，应使用固定分块和固定合并树、顺序累加，或经过论证的补偿求和方案。若只要求误差容限，应比较相对/绝对误差，而不是盲目使用 ==。

6.3 有符号整数重排也不是天然安全

有符号溢出是未定义行为。即使数学最终值落在类型范围内，不同归约分组也可能让某个中间结果先溢出。选择足够宽的类型、限制输入范围，或使用显式溢出检查，比假设“整数一定确定”更可靠。

7. par_unseq 为什么限制最多？

par_unseq 允许调用分布在未指定线程中，还允许同一线程内的多个调用无序交错，以便实现 SIMD。此时阻塞同步可能出现这样的局面：一个 SIMD lane 获取锁，另一个 lane 在同一线程上等待这把锁，而持锁 lane 没机会继续执行并释放。

// 错误示例：par_unseq 下调用 mutex 属于不允许的同步形状
std::for_each(std::execution::par_unseq,
              values.begin(), values.end(),
              [&](std::uint32_t value) {
                  std::lock_guard lock(mutex);
                  log.push_back(value);
              });

这不只是“性能可能差”，而可能落入标准规定的未定义行为。适合 par_unseq 的 callable 应接近纯数值函数：不阻塞、不等待、不依赖执行顺序、不修改共享非原子状态，并避免复杂 I/O 和不可预测副作用。

thread_local 也不代表“每次迭代私有”。同一线程可能交错执行多个迭代，它们仍共享该线程的 thread-local 对象。

对于不能证明满足这些约束的代码，先使用 seq 或 par。par_unseq 不是一个应该默认打开的“最快档位”。

8. 常见算法分别解决什么问题？

算法	数据流	典型用途	关键边界
transform	输入元素 → 唯一输出位置	逐元素转换	输出范围足够且别名合法
reduce	多个元素 → 一个结果	求和、最大值、统计	操作应允许重排
transform_reduce	先映射，再归约	点积、范数、平方和	同时满足变换与归约约束
inclusive_scan	前缀包含当前元素	累积偏移、前缀和	输出语义依赖前缀定义
exclusive_scan	前缀不含当前元素	地址/槽位计算	初值与操作顺序要明确
sort	原地重排范围	大规模排序	比较函数必须形成严格弱序

8.1 scan 不是普通 transform

输入：

1 2 3 4

inclusive scan 输出：

1 3 6 10

exclusive scan 以零为初值时输出：

0 1 3 6

scan 专门表达前缀依赖，允许实现用并行算法构造结果。用 for_each(par) 手写 out[i] = out[i - 1] + in[i] 会直接引入未同步依赖。

8.2 sort 的比较函数不能顺便统计

// 错误示例：计数器产生数据竞争，比较函数还有副作用
std::size_t comparisons = 0;
std::sort(std::execution::par,
          values.begin(), values.end(),
          [&](auto left, auto right) {
              ++comparisons;
              return left < right;
          });

比较函数应稳定地表达严格弱序。调试统计若确实需要，应使用不改变比较结果的线程安全机制，并接受它可能严重扭曲性能；更常见的做法是在专门诊断构建中测量，而不是污染正式 Benchmark。

9. 从最小示例走向工程实践

9.1 把异常挡在并行 callable 外面

对于标准执行策略，若算法调用的元素访问函数以未捕获异常退出，标准规定调用 std::terminate；即使使用 std::execution::seq 这个策略对象，也不能套用“不带策略的顺序算法会传播异常”的直觉。算法为并行化申请临时资源失败时则可以抛出 std::bad_alloc。

因此应优先在调用前完成格式、范围和资源验证，让热路径 callable 不抛。若错误只能在元素处理中发现，可以返回状态到预分配的独立槽位，算法结束后统一检查；使用共享“第一个错误”还需要同步，并可能破坏并行收益。

9.2 标准策略不提供精细资源控制

标准接口没有直接参数指定线程数、grain size、线程亲和性或 NUMA node。若应用已有其他线程池，库管理的并行任务还可能与其叠加，造成过度订阅（oversubscription）。

需要任务 arena、固定并行度、NUMA-aware 分区、pipeline 或嵌套任务调度时，TBB 等任务框架通常更合适。少量长期 worker、自定义低延迟协议则可能需要明确的线程与同步代码。

9.3 连续内存常比“算法名字带 par”更重要

标准只要求算法规定的迭代器类别，但链表和指针追逐结构通常缺乏连续访问、分块成本高。规则的 vector/array、均衡的每元素工作和独立输出，更容易获得实际收益。

这不是说并行算法只能处理连续容器，而是性能要同时受数据布局、缓存、内存带宽和调度开销约束。

9.4 C++17～23 不要假定 ranges 算法接受执行策略

经典迭代器算法与 std::ranges 算法是不同重载体系。在 C++17～C++23 项目中，不应直接假设 std::ranges::transform(std::execution::par, ...) 可用。并行 ranges 的标准化仍需要结合所用语言版本和实现支持验证。

9.5 性能验证至少回答四个问题

1. 与不带策略和 seq 相比，结果是否正确？
2. profiler 是否显示实际并行或向量化？
3. 从小到大的输入规模曲线在哪里出现收益拐点？
4. 与应用其他线程池同时运行时，尾延迟和总吞吐是否改善？

只看一次 wall-clock 时间，无法区分后端未并行、任务太小、内存带宽饱和和系统噪声。

10. 常见误区

10.1 误区：加上 par 就保证多线程

par 只允许并行，实现可以退回顺序执行。应结合目标标准库文档、线程时间线和 profiler 验证，而不是通过源代码标签推断。

10.2 误区：并行算法会自动保护 lambda 捕获的对象

算法只管理自己的分块和内部同步，不会为用户共享状态加锁。捕获引用后执行 push_back、计数或写 map，仍可能数据竞争。

10.3 误区：reduce(seq) 与 accumulate 一定逐位相同

reduce 的语义允许重排，seq 只要求元素访问调用不并行。浮点和非结合操作可能产生不同结果。

10.4 误区：par_unseq 是默认最快策略

它只扩大实现自由度，同时对 callable 施加最严格约束。复杂分支、共享状态、阻塞操作和较小输入都可能让它不合适。

10.5 误区：lambda 内部 try/catch 能恢复所有异常

它只能捕获 lambda 自己覆盖范围内的异常，而且错误记录仍需线程安全。算法内部资源分配失败、迭代器操作和其他元素访问函数还有各自路径。设计不抛热循环通常更可靠。

10.6 误区：标准并行算法可以替代所有调度框架

它擅长形状规则的数据并行，不提供所有资源、拓扑和任务依赖控制。调度本身成为核心需求时，应换用更合适的抽象。

11. 什么时候应该使用标准并行算法？

它适合连续或容易分块的数据、独立的逐元素变换、可重排归约、点积、scan 和大规模排序。代码从顺序算法自然演化而来，输入输出边界清楚，且团队愿意在各目标工具链上维护性能基线。

如果数据量很小、工作主要是 I/O、迭代间存在复杂依赖、必须精确控制线程数/NUMA、需要稳定的逐位浮点结果，或者 callable 依赖阻塞同步，就不应把 par 当成第一选择。

标准算法最大的价值往往是先把计算写成“无共享副作用的数据流”。即使最终改用 TBB、GPU 或手写向量化，这种形状也更容易迁移和验证。

12. 总结

加上 std::execution::par 后没有变快，并不自动说明标准库有缺陷。它可能没有启用并行后端、选择了顺序回退、工作量太小，或已经受到内存带宽限制。

1. 执行策略表达许可，不承诺线程数和加速比；“能编译、真并行、能加速”是三个独立问题。
2. 并行 callable 应尽量无共享副作用，每次迭代拥有独立输出；算法不会替用户消除数据竞争。
3. reduce 允许重排，浮点误差、整数溢出和操作结合性必须在业务层验证。
4. par_unseq 允许无序交错，mutex 等向量化不安全操作可能导致未定义行为。
5. 标准策略下的 callable 异常可能触发 std::terminate，热路径应优先设计为不抛并在外部校验。

可以直接用于实践的建议是：把第一次 par 改动当成实验，而不是优化结论：保留 seq 基线，校验结果，扫描输入规模，用 profiler 确认后端行为，再决定标准算法是否适合当前工作负载。

参考资料

• C++ 工作草案：Parallel algorithms and execution policies
• C++ 工作草案：transform_reduce
• WG21 P0024R2：Introducing Execution Policies
• WG21 P2214R2：A Plan for C++23 Ranges