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

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

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

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

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

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