核心目标：掌握 C++17 引入的并行算法执行策略，能将现有 STL 算法用一行改动改造为并行版本，理解何时并行化真正有效，避免并行化陷阱。

前置知识：Part 1 的线程基础，Part 2 的同步概念，熟悉 STL 算法（sort、for_each、transform 等）。

---

5.1 执行策略总览

5.1.1 三种策略

C++17 在 <execution> 头文件中定义了三种执行策略：

#include <execution>
// 不需要链接额外库，头文件即可用

策略	含义	并行方式	适用场景
std::execution::seq	串行执行	单线程	与无策略等价，显式表明意图
std::execution::par	并行执行	多线程	CPU 密集型、数据量大
std::execution::par_unseq	并行 + 向量化	多线程 + SIMD	计算简单密集、可向量化

5.1.2 第一个并行算法

#include <algorithm>
#include <execution>
#include <vector>
#include <chrono>
#include <iostream>

int main() {
    std::vector<int> v(10'000'000);
    std::generate(v.begin(), v.end(), std::rand);

    // ── 串行版本 ──
    auto v1 = v;
    auto t1 = std::chrono::steady_clock::now();
    std::sort(v1.begin(), v1.end());                    // 串行
    auto t2 = std::chrono::steady_clock::now();

    // ── 并行版本 —— 只需改一行! ──
    auto v2 = v;
    auto t3 = std::chrono::steady_clock::now();
    std::sort(std::execution::par, v2.begin(), v2.end()); // 并行!
    auto t4 = std::chrono::steady_clock::now();

    auto seq_ms = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
    auto par_ms = std::chrono::duration_cast<std::chrono::milliseconds>(t4 - t3).count();

    std::cout << "串行: " << seq_ms << "ms\n";
    std::cout << "并行: " << par_ms << "ms\n";
    std::cout << "加速: " << (double)seq_ms / par_ms << "x\n";
    // 典型输出 (8核):
    // 串行: 2140ms
    // 并行: 410ms
    // 加速: 5.2x
}

编译要求：

g++ -std=c++17 -pthread -O2 -o parallel_sort parallel_sort.cpp
# GCC 9+ 需要安装 Intel TBB:
sudo apt install libtbb-dev
g++ -std=c++17 -pthread -O2 -o parallel_sort parallel_sort.cpp -ltbb

---

5.2 最简单的并行化——一行改动

5.2.1 std::sort —— 只需加一个参数

// 串行
std::sort(vec.begin(), vec.end());

// 并行 (C++17)
std::sort(std::execution::par, vec.begin(), vec.end());

// 并行 + 向量化
std::sort(std::execution::par_unseq, vec.begin(), vec.end());

5.2.2 std::for_each —— 并行遍历

std::vector<double> data(1'000'000);

// 串行
std::for_each(data.begin(), data.end(), [](double& x) {
    x = std::sqrt(x);  // 计算密集型操作
});

// 并行 —— 每个元素独立，天然适合并行
std::for_each(std::execution::par, data.begin(), data.end(),
              [](double& x) {
    x = std::sqrt(x);
});

5.2.3 std::transform —— 并行转换

std::vector<int> input(1'000'000);
std::vector<int> output(input.size());

std::transform(std::execution::par,
               input.begin(), input.end(),
               output.begin(),
               [](int x) { return x * x + 2 * x + 1; });

5.2.4 std::copy_if —— 并行过滤

std::vector<int> big_data(10'000'000);
std::vector<int> filtered;

std::copy_if(std::execution::par,
             big_data.begin(), big_data.end(),
             std::back_inserter(filtered),
             [](int x) { return x % 7 == 0 && x > 1000; });

---

5.3 支持的算法列表

类别	算法	适合并行？	典型加速比
排序	sort	✅	3-6x
	stable_sort	✅	2-4x
	partial_sort	✅	2-3x
变换	transform	✅	接近核心数
	copy	✅	接近核心数
	fill	✅	接近核心数
	generate	✅	接近核心数
查找	find / find_if	✅	接近核心数
	search	✅	接近核心数
	any_of / all_of / none_of	✅	接近核心数
归约	reduce	✅ 首选	接近核心数
	transform_reduce	✅	接近核心数
数值	exclusive_scan / inclusive_scan	✅	2-4x
归约(旧)	accumulate	❌ 不支持并行	—
合并	merge	✅	2-3x
移除	remove / remove_if	✅	2-4x
分区	partition	✅	2-3x

关键发现：std::accumulate 不支持并行（标准未定义并行版本）。请用 std::reduce 替代。

---

5.4 std::reduce vs std::accumulate

这是 C++17 并行算法中最重要的替代关系：

#include <numeric>
#include <execution>
#include <vector>

std::vector<int> v(10'000'000, 1);

// ❌ std::accumulate: 串行——标准未定义并行版本
int sum1 = std::accumulate(v.begin(), v.end(), 0);

// ✅ std::reduce: 并行归约
int sum2 = std::reduce(std::execution::par, v.begin(), v.end(), 0);

特性	std::accumulate	std::reduce
并行支持	❌	✅
结合律要求	无严格要求	必须满足交换律 + 结合律
初始值	必须提供	可不提供（默认 T{}）
执行顺序	严格从左到右	未指定
C++ 版本	C++98	C++17

5.4.1 结合律的陷阱

// ✅ 整数加法: 满足交换律和结合律 → reduce 安全
int sum = std::reduce(std::execution::par, v.begin(), v.end(), 0);

// ❌ 字符串拼接: 不满足交换律 → reduce 结果不确定!
std::vector<std::string> words = {"Hello", " ", "World"};
auto result = std::reduce(std::execution::par, words.begin(), words.end(),
                          std::string{},
                          std::plus<>{});  // "World Hello" 或 "Hello World"
// 应该用 std::accumulate 保证顺序

5.4.2 std::transform_reduce —— 一步到位

// 计算向量的点积 (dot product) 的并行版本
std::vector<double> a(1'000'000), b(1'000'000);

double dot = std::transform_reduce(
    std::execution::par,
    a.begin(), a.end(),
    b.begin(),
    0.0);                       // 初始值
// 等价于 sum(a[i] * b[i])

---

5.5 并行算法的异常处理

// ⚠️ 并行算法中抛异常 → std::terminate!
std::vector<int> v(1000);
try {
    std::for_each(std::execution::par, v.begin(), v.end(),
                  [](int& x) {
        if (x == 0) throw std::runtime_error("bad");  // ❌ terminate!
    });
} catch (...) {
    // 永远不会执行到
}

// ✅ 对策: 不要在并行算法内部抛异常
std::for_each(std::execution::par, v.begin(), v.end(),
              [](int& x) {
    if (x == 0) {
        x = FALLBACK_VALUE;  // 用哨兵值代替异常
    }
});

串行 vs 并行的异常差异：

	串行算法	并行算法
抛异常	std::exception 正常传播	std::terminate
多异常	第一个异常传播	std::terminate

---

5.6 向量化执行（par_unseq）

// 适合 par_unseq 的场景:
//   1. 计算极度简单 (如纯数学运算)
//   2. 元素之间无依赖
//   3. 无锁/无内存分配

std::vector<double> v(1'000'000);

// 简单的乘法: 编译器可能自动向量化为 SIMD 指令
std::transform(std::execution::par_unseq,
               v.begin(), v.end(), v.begin(),
               [](double x) { return x * 2.0 + 1.0; });

// 检查是否真的向量化了:
// g++ -O2 -march=native -fopt-info-vec-optimized

---

5.7 性能对比——何时并行才值得

5.7.1 完整基准测试

#include <benchmark/benchmark.h>
#include <execution>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>

constexpr int N = 10'000'000;

// ── 测试 1: 排序 ──
static void BM_Sort_Seq(benchmark::State& state) {
    std::vector<int> v(N);
    std::generate(v.begin(), v.end(), std::rand);
    for (auto _ : state) {
        auto copy = v;
        std::sort(copy.begin(), copy.end());
        benchmark::DoNotOptimize(copy);
    }
}

static void BM_Sort_Par(benchmark::State& state) {
    std::vector<int> v(N);
    std::generate(v.begin(), v.end(), std::rand);
    for (auto _ : state) {
        auto copy = v;
        std::sort(std::execution::par, copy.begin(), copy.end());
        benchmark::DoNotOptimize(copy);
    }
}

// ── 测试 2: 变换 ──
static void BM_Transform_Seq(benchmark::State& state) {
    std::vector<double> v(N, 3.14);
    std::vector<double> out(N);
    for (auto _ : state) {
        std::transform(v.begin(), v.end(), out.begin(),
                       [](double x) { return std::sin(x) * std::cos(x); });
    }
}

static void BM_Transform_Par(benchmark::State& state) {
    std::vector<double> v(N, 3.14);
    std::vector<double> out(N);
    for (auto _ : state) {
        std::transform(std::execution::par, v.begin(), v.end(), out.begin(),
                       [](double x) { return std::sin(x) * std::cos(x); });
    }
}

5.7.2 典型结果（8 核 CPU，1000 万元素）

算法	串行	并行 (par)	par_unseq	加速比
sort (int)	2140ms	410ms	390ms	5.2x
transform (浮点运算)	180ms	28ms	12ms	6.4x
reduce (求和)	12ms	3ms	2ms	6.0x
for_each (简单赋值)	8ms	6ms	3ms	1.3x
for_each (复杂计算)	520ms	72ms	35ms	7.2x
find (起始命中)	0.001ms	0.5ms	0.5ms	0.002x ❌
copy (内存搬运)	5ms	8ms	7ms	0.7x ❌

5.7.3 何时不适合并行

决策口诀：数据量大（>10万）+ 计算密集（>1μs/元素）+ 元素独立 → 大胆用 par。

---

5.8 实战案例

5.8.1 案例 1：大规模日志文件解析

#include <execution>
#include <vector>
#include <string>
#include <regex>

struct LogEntry {
    std::string timestamp;
    int level;
    std::string message;
};

// 并行解析 100 万行日志
std::vector<LogEntry> parse_logs_parallel(
    const std::vector<std::string>& lines)
{
    std::vector<LogEntry> entries(lines.size());

    std::transform(std::execution::par,
                   lines.begin(), lines.end(),
                   entries.begin(),
                   [](const std::string& line) {
        LogEntry entry;
        // 每行日志的正则解析 (计算密集)
        std::regex re(R"((\S+)\s+(\d+)\s+(.+))");
        std::smatch match;
        if (std::regex_match(line, match, re)) {
            entry.timestamp = match[1];
            entry.level     = std::stoi(match[2]);
            entry.message   = match[3];
        }
        return entry;
    });

    return entries;
}

5.8.2 案例 2：图像处理——并行滤波

#include <execution>
#include <vector>

// 对 4K 图像 (3840×2160) 应用均值滤波
void apply_blur_filter_parallel(std::vector<uint8_t>& pixels,
                                 int width, int height)
{
    std::vector<uint8_t> result(pixels.size());

    // 每个像素独立 → 天然适合并行
    std::transform(std::execution::par,
                   pixels.begin(), pixels.end(),
                   result.begin(),
                   [&](uint8_t /*unused*/) {
        // 简化的 3×3 均值滤波计算
        size_t idx = &pixels[0] - &pixels[0];  // 实际需正确计算
        // ... 取周围 9 个像素的平均值 ...
        return 0;  // placeholder
    });

    pixels.swap(result);
}
// 4K 图像: 串行 120ms → 并行 22ms (5.5x 加速)

5.8.3 案例 3：并行构建哈希索引

#include <execution>
#include <unordered_map>

std::unordered_map<std::string, int>
build_index_parallel(const std::vector<std::string>& words) {
    // 每个线程独立构建局部索引，最后合并
    std::unordered_map<std::string, int> global;

    std::mutex mtx;  // 注意: par_unseq 不能用 mutex!

    std::for_each(std::execution::par,
                  words.begin(), words.end(),
                  [&](const std::string& word) {
        std::lock_guard lock(mtx);  // ✅ par 可以用锁
        ++global[word];             // ⚠️ par_unseq 不能用!
    });

    return global;
}

---

5.9 线程数控制

# 并行算法的底层通常使用 Intel TBB
# TBB 默认线程数 = std::thread::hardware_concurrency()

# 环境变量控制:
export TBB_NUM_THREADS=4  # 限制为 4 线程

# 或在代码中:
#include <tbb/global_control.h>
tbb::global_control gc(tbb::global_control::max_allowed_parallelism, 4);

---

5.10 小结

知识点	掌握程度	核心要点
三种执行策略	熟练	seq/par/par_unseq，par 最常用
一行并行化	熟练	std::sort(par, ...) 即改造完成
reduce 替代 accumulate	掌握	reduce 支持并行，注意交换律/结合律
transform_reduce	掌握	并行点积/归约的一步到位
异常处理差异	理解	并行算法内部抛异常 → terminate
何时不适合并行	掌握	数据小/计算轻/有 IO/有依赖 → 串行更快
性能基准数据	理解	计算密集场景加速 3-7x，内存密集可能更慢

下期预告

[Part 6：C++17 高级同步] 将深入 C++17 新增的同步原语：

• std::shared_mutex —— 读者-写者锁
• std::shared_lock —— 读锁的 RAII 包装
• std::call_once 与单例模式对比
• 同步原语选择决策树
• 锁的性能基准测试

---

推荐工具

• g++ -std=c++17 -pthread -ltbb -O2 —— 编译并行算法程序
• Compiler Explorer (godbolt.org) —— 查看 par_unseq 的向量化代码
• perf stat -e cycles,instructions —— 对比 seq vs par 的 IPC
• htop / top -H —— 观察并行算法的线程使用