并发算法详细介绍

C++17 引入了并行执行策略，允许标准库中的许多算法在多线程环境下并行执行。C++20 进一步扩展了这些策略，增加了向量化执行的支持。以下是并发算法的详细介绍、适用容器以及使用注意事项。

---

并发执行策略

C++ 提供了四种执行策略，定义在 <execution> 头文件中：

1. std::execution::seq：

   • 含义：顺序执行，即算法的执行是单线程的，按照传统的顺序方式运行。
   • 适用场景：默认策略，适合不需要并行化的场景。

2. std::execution::par：

   • 含义：并行执行，算法可能会使用多线程来并行处理数据。
   • 适用场景：适合数据量较大且可以并行化的场景。

3. std::execution::par_unseq：

   • 含义：并行执行，且允许向量化（SIMD，单指令多数据流）。算法可能会使用多线程和 SIMD 指令来加速计算。
   • 适用场景：适合需要高性能计算的场景，如科学计算、图像处理等。

4. std::execution::unseq（C++20）：

   • 含义：向量化执行，算法可能会使用 SIMD 指令来加速计算，但不允许多线程并行。
   • 适用场景：适合需要单线程高性能计算的场景。

---

支持并发算法的标准库算法

C++17 和 C++20 中，许多标准库算法支持并发执行策略，例如：

• 排序算法：std::sort、std::stable_sort
• 查找算法：std::find、std::count
• 数值算法：std::reduce、std::transform_reduce
• 修改算法：std::for_each、std::transform
• 复制算法：std::copy、std::move

---

适用容器

并发算法可以用于支持随机访问迭代器的容器，例如：

• std::vector
• std::array
• std::deque
• std::string

对于不支持随机访问迭代器的容器（如 std::list、std::forward_list），并发算法无法直接使用，因为这些容器的迭代器不支持随机访问。

---

并发算法使用注意事项

1. 线程安全性：

   • 并发算法可能会在多线程环境下运行，因此需要确保操作是线程安全的。
   • 例如，在 std::for_each 中，传递给算法的函数对象必须是线程安全的。

2. 数据竞争：

   • 如果多个线程同时访问共享数据，可能会导致数据竞争。需要使用同步机制（如互斥锁）来避免竞争。

3. 性能开销：

   • 并发算法可能会引入额外的线程创建和管理开销。对于小规模数据，顺序执行可能更快。

4. 向量化的限制：

   • 使用 std::execution::par_unseq 或 std::execution::unseq 时，算法可能会使用 SIMD 指令。需要确保代码对向量化友好，避免依赖顺序执行。

5. 算法复杂度：

   • 某些算法在并行化后复杂度可能会发生变化。例如，std::sort 的并行版本可能比顺序版本更快，但实际性能取决于硬件和数据规模。

---

示例代码

1. 使用 std::execution::par 并行排序

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

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2};

    // 使用并行策略对 vec 进行排序
    std::sort(std::execution::par, vec.begin(), vec.end());

    for (int i : vec) {
        std::cout << i << " "; // 输出: 1 2 3 4 5
    }
    std::cout << std::endl;

    return 0;
}

2. 使用 std::execution::par_unseq 并行累加

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 使用并行策略计算 vec 的和
    int sum = std::reduce(std::execution::par_unseq, vec.begin(), vec.end());

    std::cout << "Sum: " << sum << std::endl; // 输出: 15
    return 0;
}

3. 使用 std::execution::par 并行遍历

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 使用并行策略遍历 vec
    std::for_each(std::execution::par, vec.begin(), vec.end(), [](int& n) {
        n *= 2;
    });

    for (int i : vec) {
        std::cout << i << " "; // 输出: 2 4 6 8 10
    }
    std::cout << std::endl;

    return 0;
}

---

总结

• 并发执行策略：seq（顺序）、par（并行）、par_unseq（并行+向量化）、unseq（向量化）。
• 适用容器：支持随机访问迭代器的容器（如 std::vector、std::array）。
• 注意事项：线程安全性、数据竞争、性能开销、向量化限制等。

并发算法可以显著提升程序的性能，但需要根据具体场景选择合适的执行策略，并注意线程安全和性能优化。