使用STL并行算法的用户有哪些限制？

Question

在杰克逊维尔会议上,有效采用Parallelism TS规范的提议P0024r2被接受到C++ 17(草案)中.该提议为许多算法添加了重载,这些算法采用执行策略参数来指示应该考虑哪种并行性.在(20.19.2 [执行])中已经定义了三个执行策略:<execution>

• std::execution::sequenced_policy(20.19.4 [execpol.seq])带有一个constexpr对象std::execution::seq(20.19.7 [parallel.execpol.objects])来表示顺序执行,类似于在没有执行策略的情况下调用算法.
• std::execution::parallel_policy(20.19.5 [execpol.par])带有一个constexpr对象std::execution::par(20.19.7 [parallel.execpol.objects]),表示可能使用多个线程执行算法.
• std::execution::parallel_unsequenced_policy(20.19.6 [execpol.vec])带有一个constexpr对象std::execution::par_unseq(20.19.7 [parallel.execpol.objects]),表示可能使用向量执行和/或多个线程执行算法.

STL算法通常将用户定义的对象(迭代器,函数对象)作为参数.用户定义的对象有哪些限制,使它们可以使用标准执行策略与并行算法一起使用？

例如,当使用如下例中的算法时,对FwdItand 的含义是Predicate什么？

template <typename FwdIt, typename Predicate>
FwdIt call_remove_if(FwdIt begin, FwdIt end, Predicate predicate) {
    return std::remove_if(std::execution::par, begin, end, predicate);
}

Answer 1

简短的回答是,不允许使用执行策略的算法使用的元素访问函数(本质上是算法对各种参数所需的操作;请参阅下面的详细信息)std::execution::parallel导致数据争用或死锁.与使用执行策略的算法一起使用的元素访问函数std::execution::parallel_unsequenced_policy另外不能使用任何阻塞同步.

细节

该描述基于选票文件N4604.我还没有核实是否有一些条款因国家机构评论而被修改(粗略检查似乎暗示到目前为止没有编辑).

第25.2节[algorithms.parallel]指定并行算法的语义.有多个约束不适用于不采用执行策略的算法,分为多个部分:

1. 在25.2.2 [algorithms.parallel.user]中,约束谓词函数可以对其参数执行的操作:

   传递到并行算法类型的对象函数对象Predicate,BinaryPredicate,Compare,和BinaryOperation不得直接或间接地通过它们的参数修改对象.

   编写子句的方式似乎只要遵守其他约束(见下文),就可以修改对象本身.请注意,此约束与执行策略无关,因此即使在使用时也适用std::execution::sequenced_policy.完整的答案比这更复杂,似乎规范目前无意中过度约束(见下面的最后一段).

2. 在25.2.3 [algorithms.parallel.exec]中添加了对元素访问函数(见下文)的约束,这些约束特定于不同的执行策略:

   • 当使用std::execution::sequenced_policy元素时,访问函数都是从同一个线程调用的,即执行不以任何形式交错.
   • 当使用std::execution::parallel_policy不同的线程时,可以从不同的线程同时调用元素访问函数.不允许从不同线程调用元素访问函数导致数据争用或导致死锁.但是,来自同一线程的元素访问的调用是[不确定]序列,即,没有来自同一线程的元素访问函数的交错调用.例如,如果Predicate使用with std::execution::par计算它的调用频率,则需要适当地同步相应的计数.

   • 当使用std::execution::parallel_unsequenced_policy元素调用时,访问函数可以在不同的线程之间以及在一个执行的线程内交错.也就是说,使用阻塞同步原语(如a std::mutex)可能导致死锁,因为同一线程可能尝试多次同步(例如,尝试多次锁定相同的互斥锁).当使用标准库函数进行元素访问函数时,标准中的约束是(25.2.3 [algorithms.parallel.exec]第4段):

     如果指定标准库函数与另一个函数调用同步,或指定另一个函数调用与其同步,并且它不是内存分配或释放函数,则标准库函数是矢量化不安全的.从execution::parallel_unsequenced_policy算法调用的用户代码可能无法调用矢量化不安全的标准库函数.

   • 使用实现定义的执行策略时会发生什么,不出所料,实现定义.

3. 在25.2.4 [algorithm.parallel.exception]中,使用从元素访问函数抛出的异常是一种约束:当元素访问函数抛出异常时,std::terminate()调用它.也就是说,抛出异常是合法的,但结果不太可取.请注意,std::terminate()即使使用也会调用std::execution::sequenced_policy.

元素访问功能

上述约束使用术语元素访问功能.该术语在25.2.1 [algorithm.parallel.defns]第2段中定义.有四组功能分类为元素访问功能:

• 算法实例化的迭代器类别的所有操作.
• 对其规范所需的那些序列元素的操作.
• 如果规范要求,用户提供的函数对象将在算法执行期间应用.
• 对规范要求的那些功能对象的操作.

本质上,元素访问函数是标准在算法规范中明确引用的所有操作或与这些算法一起使用的概念.未提及并且例如检测到存在的功能(例如,使用SFINAE)不受约束,并且实际上不能从对其使用施加同步约束的并行算法中调用.

问题

稍微有点担心似乎不能保证[mutating]元素访问函数所应用的对象在不同线程之间是不同的.特别是,我无法保证应用于迭代器对象的迭代器操作不能从两个不同的线程应用于同一个迭代器对象!这意味着,例如,operator++()在迭代器对象上需要以某种方式同步其状态.operator==()如果在不同的线程中修改对象,我无法看到如何做一些有用的事情.似乎无意中对同一对象的操作需要同步,因为将[mutating]元素访问函数同时应用于对象没有任何意义.但是,我看不到任何文字说明使用了不同的对象(我想,我需要为此提出一个缺陷).