C++17为标准库添加并行算法，都是对之前已存在的一些标准算法的重载，例如：std::find，std::transform和std::reduce。并行版本的函数，在参数列表的中新添加了一个参数（指定要使用的执行策略）。
通过指定执行策略，算法的需求复杂性已经发生变化，并且要比串行版的算法要求要宽松。因为并行算法要利用系统的并行性，从而算法通常会做更多的工作。

1 执行策略

在<execution>头文件中定义了三个相关的策略对象可以传递到算法中，分别对应三种策略（开发者不能自定义执行策略）：

  • std::execution::seq : std::execution::sequenced_policy
  • std::execution::par : std::execution::parallel_policy

  • std::execution::par_unseq : std::execution::parallel_unsequenced_policy

    1.1 策略对算法的影响

    将执行策略传递给标准算法库中的算法，那么算法的行为就由执行策略控制。这会有几方面的影响：

  • 算法复杂化：除了对并行的管理调度开销外，并行算法的核心操作将会被多次执行(交换，比较，以及提供的函数对象)，目的是在总运行时间方面提供性能的整体改进。

  • 抛出异常时的行为：如果有异常未被捕获，那么标准执行策略都会调用std::terminate。如果标准库无法提供给内部操作足够的资源，则在无执行策略算法执行时，会触发std::bad_alloc异常。

  • 算法执行的位置、方式和时间

    • 执行策略指定使用那些代理来执行算法（“普通”线程、向量流、GPU线程等）
    • 执行策略还将对算法步骤进行执行时的约束和安排
    • 是否以特定的顺序运行，算法步骤之间是否可以交错，或彼此并行运行

      1.2 sequenced_policy顺序策略

      序策略并不是并行策略：它使用强制的方式实现，在执行线程上函数的所有操作。但它仍然是一个执行策略，因此对算法的复杂性和异常影响与其他标准执行策略相同。
      策略要求：

  • 需要在同一线程上执行所有操作，而且必须按照一定的顺序进行执行，这样步骤间就不会有交错

  • 对算法使用的迭代器、相关值和可调用对象没什么要求：

    • 可以自由的使用同步机制，并且可以依赖于同一线程上的所有操作，不过他们不能依赖这些操作的顺序。

      1.3 parallel_policy并行策略

      并行策略提供了在多个线程下运行的算法版本。操作可以在调用算法的线程上执行，也可以在库创建的线程上执行。在给定线程上执行需要按照一定的顺序，不能交错执行，但十分具体的顺序是不指定的；并且在不同的调用间，指定的顺序可能会不同。给定的操作将在整个持续时间内，在固定线程上执行。
      策略要求：

  • 对算法所使用的迭代器、相关值和可调用对象有了额外的要求：

    • 不能有数据竞争，也不能依赖于线程上运行的其他操作，或者依赖的操作不能在同一线程上。

      1.4 parallel_unsequenced_policy并行不排序策略

      并行不排序策略提供了最大程度的并行化算法，用以得到对算法使用的迭代器、相关值和可调用对象的严格要求。
      策略要求：

  • 使用并行不排序策略调用的算法，可以在任意线程上执行，这些线程彼此间没有顺序

  • 算法使用的迭代器、相关值和可调用对象不能使用任何形式的同步，也不能调用任何需要同步的函数。


1.5 执行策略的选择

  • std::execution::par是最常使用的策略，除非实现提供了更适合的非标准策略。如果代码适合并行化，那应该与std::execution::par一起工作。

  • 某些情况下，可以使用std::execution::par_unseq进行代替。这可能根本没什么用(没有任何标准的执行策略可以保证能达到并行性的级别)，但它可以给库额外的空间，通过重新排序和交错任务执行来提高代码的性能，以换取对代码更严格的要求（不能使用任何同步）。

    2 标准库并行算法

    标准库中大多数被重载的并行算法都在<algorithm>和<numeric>头文件中：

  • all_of，any_of，none_of，for_each，for_each_n，find，find_if，find_end，find_first_of，adjacent_find，count，count_if，mismatch，equal，search，search_n

  • copy，copy_n，copy_if，move，swap_ranges，transform，replace，replace_if，replace_copy，replace_copy_if，fill，fill_n，generate，generate_n，remove
  • remove_if，remove_copy，remove_copy_if，unique，unique_copy，reverse，reverse_copy，rotate，rotate_copy，is_partitioned，partition，stable_partition
  • partition_copy，sort，stable_sort，partial_sort，partial_sort_copy，is_sorted，is_sorted_until，nth_element，merge，inplace_merge，includes，set_union
  • set_intersection，set_difference，set_symmetric_difference，is_heap，is_heap_until，min_element，max_element，minmax_element，lexicographical_compare
  • reduce，transform_reduce，exclusive_scan，inclusive_scan，transform_exclusive_scan，transform_inclusive_scan和adjacent_difference

对于列表中的每一个算法，每个”普通”算法的重载都有一个新的参数(第一个参数)，这个参数将传入执行策略。

2.1 使用示例

最简单的例子就是并行循环：对容器的每个元素进行处理。这是令人尴尬的并行场景：每个项目都是独立的，所以有最大的并行性：

  1. /*
  2. 使用标准库并行算法for_each的示例
  3. */
  4. #include <algorithm>
  5. #include <vector>
  6. #include <iostream>
  7. #include <execution>
  9. void do_each(int &a)
  10. {
  11.     a++;
  12.     std::cout << " after add, a = " << a << std::endl;
  13. }
  15. int main()
  16. {
  17.     std::vector<int> v = {1, 2, 3, 4, 5};
  18.     // 使用并行算法，对vector中每个元素进行并行操作
  19.     std::for_each(std::execution::par, v.begin(), v.end(), do_each);
  21.     // 打印最后结果
  22.     for (int i = 0; i < v.size(); i++)
  23.     {
  24.         std::cout << v[i] << "  " << std::endl;
  25.     }
  26.     return 0;
  27. }

标准库将创建内部线程，并对数据进行划分，且对每个元素x调用do_stuff(x)。其中在线程间划分元素是一个实现细节。