在并行算法中使用range :: view :: iota [英] Using ranges::view::iota in parallel algorithms

问题描述

因为在算法并行/questions/tagged/c％2b％2b17"class =" post-tag"title ="显示标记为'c ++ 17'"rel =" tag> c ++ 17 的问题，我想知道是否可以将ranges::view::iota与std::for_each组合使用以模拟这一点.那就是:

Since there is no index based parallel for algorithm in c++17, I'm wondering if ranges::view::iota can be used in combination with std::for_each to emulate that. That is:

using namespace std;

constexpr int N= 10'000'000;
ranges::iota_view indices(0,N);
vector<int> v(N);

for_each(execution::par_unseq,indices.begin(),indices.end(),[&](int i) { v[i]= i; });

iota_view似乎提供了对适当类型的随机访问( [范围.iota.iterator] ):

iota_view seems to provide random access for appropriate types ([range.iota.iterator]):

iota_view<I, Bound>::iterator::iterator_category的定义如下:

(1.1)—如果I为Advanceable建模，则iterator_category为random_access_iterator_tag.

(1.1) — If I models Advanceable, then iterator_category is random_access_iterator_tag.

(1.2)-否则，如果I建模Decrementable，则iterator_category为bidirectional_iterator_tag.

(1.2) — Otherwise, if I models Decrementable, then iterator_category is bidirectional_iterator_tag.

(1.3)-否则，如果I为Incrementable建模，则iterator_category为forward_iterator_tag.

(1.3) — Otherwise, if I models Incrementable, then iterator_category is forward_iterator_tag.

(1.4)-否则，iterator_category是input_iterator_tag.

(1.4) — Otherwise, iterator_category is input_iterator_tag.

以上代码正确吗?以这种方式使用iota_view是否会降低性能?

Is the above code correct? Is there any performance penalty in using iota_view this way?

编辑:我已经使用 range-v3 进行了一些测试， cmcstl2 和英特尔的

I've made some tests with range-v3, cmcstl2, and Intel's PSTL.

使用range-v3，以上示例无法在GCC 8上编译.编译器抱怨begin和end具有不同的类型:

Using range-v3, the above example fails to compile with GCC 8. The compiler complains about begin and end having different types:

deduced conflicting types for parameter ‘_ForwardIterator’ (‘ranges::v3::basic_iterator<ranges::v3::iota_view<int, int> >’ and ‘ranges::v3::default_sentinel’)

使用cmcstl2，代码可以干净地编译，但不能并行运行.在我看来，它回退到了顺序版本，可能是因为某种程度上无法满足前向迭代器的要求( https://godbolt.org/z/yvr-M2 ).

Using cmcstl2 the code compiles cleanly, but it doesn't run in parallel. It seems to me that it falls back to the sequential version, maybe because the forward iterators requirements are somehow not met (https://godbolt.org/z/yvr-M2).

存在与PSTL有关的问题( https://github.com/intel/parallelstl/issues/22 ).

There is a somewhat related PSTL issue (https://github.com/intel/parallelstl/issues/22).

推荐答案

在深入研究标准草案之后，恐怕答案是否定的:它并非严格符合标准 for_each的并行版本中的ranges::iota_view.

After digging in the standard draft, I'm afraid that the answer is no: it is not strictly standard compliant to use ranges::iota_view in the parallel version of for_each.

for_each的并行重载被声明为 [alg.foreach] :

The parallel overload of for_each is declared as [alg.foreach]:

template<class ExecutionPolicy, class ForwardIterator, class Function>
  void for_each(ExecutionPolicy&& exec,
                ForwardIterator first, ForwardIterator last,
                Function f);

另一方面，在 [algorithms.requirements] 中，找到约束:

On the other hand, in [algorithms.requirements] we find the constraint:

如果算法的模板参数名为ForwardIterator，ForwardIterator1或ForwardIterator2，则模板参数应满足 Cpp17ForwardIterator 的要求.

If an algorithm's template parameter is named ForwardIterator, ForwardIterator1, or ForwardIterator2, the template argument shall satisfy the Cpp17ForwardIterator requirements.

正如Billy O'Neal在我在问题中发布的链接之一所述，ranges::iota_view::iterator的明智实现不太可能满足相等迭代器引用同一对象"的转发迭代器要求

As noted by Billy O'Neal in one of the links I posted in the question, a sensible implementation of ranges::iota_view::iterator is very unlikely to meet the "equal iterators reference the same object" forward iterator requirement [iterator.cpp17]. Therefore, in my understanding, ranges::iota_view::iterator won't satisfy the Cpp17ForwardIterator requirements, and the same goes for e.g. boost::counting_iterator.

但是，实际上，我希望实现会使用std::iterator_traits::iterator_category来调度 适当的算法重载，如PSTL所做的那样.因此，我相信OP中的示例代码将按预期工作. cmcstl2无法正常工作的原因可能是所使用的iterator_category属于 __stl2命名空间，而不是std命名空间.

However, in practice I would expect that implementations will use std::iterator_traits::iterator_category to dispatch the appropriate overload of the algorithm, as PSTL seems to do. Therefore, I believe that the example code in the OP would work as intended. The reason that cmcstl2 doesn't work is probably that the used iterator_category belong to the __stl2 namespace instead of being the std ones.

这篇关于在并行算法中使用range :: view :: iota的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！