10.2 执行策略

10.2 执行策略

三个标准执行策略：

std::execution::sequenced_policy
std::execution::parallel_policy
std::execution::parallel_unsequenced_policy

这些类都定义在<execution>头文件中。这个头文件中也定义了三个相关的策略对象可以传递到算法中：

std::execution::seq
std::execution::par
std::execution::par_unseq

除了复制这三种类型的对象外，不能以自己的方式对执行策略对象进行构造，因为它们有一些特殊的初始化要求。实现还会定义一些其他的执行策略，开发者不能自定义执行策略。

执行策略对算法行为的影响可见10.2.1节。任何给定的实现都可以允许添加执行策略，不管他们需要怎样的语义。来看一个使用标准执行策略算法的影响，就从所有重载异常策略的算法开始吧。

10.2.1 使用执行策略的影响

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

算法复杂度
抛出异常时的行为
算法执行的位置、方式和时间

会让算法更复杂

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

复杂度的变化会根据每个算法的不同有所变化，不过通常的策略会将算法降低到某个O(表达式)。也就是说，带有执行策略的重载执行的操作数，可能是没有执行策略的数倍，这个倍数取决于库实现和平台，而不是传递给算法的数据。

异常行为

具有执行策略的算法在执行期间触发异常，则结果又执行策略确定。如果有异常未捕获，标准执行策略都会调用std::terminate。如果标准库无法提供给内部操作足够的资源，则在无执行策略算法执行时，会触发std::bad_alloc异常。例如：没有执行策略的情况下，对std::for_each的调用会将异常进行传播。

std::for_each(v.begin(),v.end(),[](auto x){ throw my_exception(); });

具有执行策略的调用，将终止程序：

std::for_each(
  std::execution::seq,v.begin(),v.end(),
  [](auto x){ throw my_exception(); });

这就是使用std::execution::seq执行策略和不同执行策略间的区别。

算法执行的位置和时间

这是执行策略的基本面，也是标准执行策略之间不同的地方。相应执行策略指定使用那些代理来执行算法，无论这些代理是“普通”线程、向量流、GPU线程，还是其他的什么。执行策略还将对算法步骤进行执行时的约束和安排：是否以特定的顺序运行，算法步骤之间是否可以交错，或彼此并行运行等。

每个执行策略都会在下面进行详解，先从最基本的std::execution::sequenced_policy开始。

10.2.2 std::execution::sequenced_policy

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

这不仅需要在同一线程上执行所有操作，而且必须按照一定的顺序进行执行，这样步骤间就不会有交错。具体的顺序是未指定的，并且对函数的不同调用也是不存在的。尤其是在没有执行策略的情况下，不能保证函数的执行顺序与相应的重载执行顺序相同。例如：下面对std::for_each的调用，是将1~1000填充到vector中，这里没有指定填充的顺序。这就与没有执行策略的重载不同，执行策略就要按顺序对数字进行存储：

std::vector<int> v(1000);
int count=0;
std::for_each(std::execution::seq,v.begin(),v.end(),
  [&](int& x){ x=++count; });

不能仅依赖这种方式，让数字按顺序进行存储。

也就是顺序策略对算法使用的迭代器、相关值和可调用对象没什么要求：可以自由的使用同步机制，并且可以依赖于同一线程上的所有操作，不过不能依赖这些操作的顺序。

10.2.3 std::execution::parallel_policy

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

这就对算法所使用的迭代器、相关值和可调用对象有了额外的要求：想要并行调用，他们间就不能有数据竞争，也不能依赖于线程上运行的其他操作，或依赖的操作不能在同一线程上。

大多数情况下，可以使用并行执行策略，这样会使用到没有执行策略的标准库算法。只有在元素间有特定的顺序，或者对共享数据有非同步访问时，才会出现问题。将vector中的所有数都加上同一个值，就可以并行：

std::for_each(std::execution::par,v.begin(),v.end(),[](auto& x){++x;});

若使用并行策略填充一个vector中，那这个例子肯定有问题。具体的讲，这样会出现未定义行为：

std::for_each(std::execution::par,v.begin(),v.end(),
  [&](int& x){ x=++count; });

每次调用Lambda表达式时，都会对计数器进行修改，如果有多个线程在执行Lambda表达式，就会出现数据竞争，从而导致未定义行为。std::execution::parallel_policy要求优先考虑这一点：即使库没有使用多线程，之前的调用依旧会产生未定义行为。对象是否出现未定义是调用的静态属性，而不是依赖库实现的细节。不过，这里允许在函数调用间进行同步，因此可以将count设置为std::atomic<int>，而不是仅用简单int来表示，或是使用互斥量。这种情况下，可能会破坏使用并行执行策略的代码，因此这里将对所有操作进行序列化调用。通常情况下，会允许对共享状态的同步访问。

10.2.4 std::execution::parallel_unsequenced_policy

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

使用并行不排序策略调用的算法，可以在任意线程上执行，这些线程彼此间没有顺序。也就是在单线程上也可以交叉运行，这样在第一个线程完成前，第二个操作会在同一个线程上启动，并且操作可以在线程间迁移，因此给定的操作可以在一个线程上启动，在另一个线程上运行，并在第三个线程上完成。

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

也就是，必须对相关的元素或基于该元素可以访问的数据进行操作，并且不能修改线程之间或元素之间共享的状态。

稍后我们将用一些例子来填充这些内容。现在，让我们来看看算法本身。