Использование range :: view :: iota в параллельных алгоритмах - PullRequest
Новая
       50

Использование range :: view :: iota в параллельных алгоритмах

0 голосов
/ 05 июля 2018

Поскольку для алгоритма в нет параллели на основе индекса , мне интересно, можно ли использовать ranges::view::iota в сочетании с std::for_each для эмуляции этого , То есть: 

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, по-видимому, обеспечивает произвольный доступ для соответствующих типов ( [range.iota.iterator] ):

iota_view<I, Bound>::iterator::iterator_category определяется следующим образом:

(1.1) - если I модели Advanceable, то iterator_category равно random_access_iterator_tag.

(1.2) - В противном случае, если I модели Decrementable, тогда iterator_category равно bidirectional_iterator_tag.

(1.3) - В противном случае, если I модели Incrementable, тогда iterator_category равно forward_iterator_tag.

(1.4) - В противном случае iterator_category равно input_iterator_tag.

Правильно ли указан код выше? Есть ли какие-либо потери производительности при использовании iota_view таким образом?

РЕДАКТИРОВАТЬ: Я провел несколько тестов с range-v3 , cmcstl2 и Intel PSTL .

При использовании range-v3 вышеприведенный пример не скомпилируется с GCC 8. Компилятор жалуется на begin и end, имеющие разные типы: 

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).

Существует несколько связанная с этим проблема с PSTL (https://github.com/intel/parallelstl/issues/22).

1 Ответ

0 голосов
/ 10 декабря 2018

После копания в стандартном черновике, я боюсь, что ответ - нет: он не совсем соответствует стандарту использования ranges::iota_view в параллельной версии for_each.

Параллельная перегрузка for_each объявлена ​​как [alg.foreach] : 

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

С другой стороны, в [gorithms.requirements] мы находим ограничение:

Если параметр шаблона алгоритма имеет имя ForwardIterator, ForwardIterator1 или ForwardIterator2, аргумент шаблона должен удовлетворять требованиям Cpp17ForwardIterator .

Как отметил Билли О'Нил в одной из ссылок, которые я опубликовал в этом вопросе, разумная реализация ranges::iota_view::iterator вряд ли будет соответствовать требованию прямого итератора "равные итераторы ссылаются на один и тот же объект" [итератор .cpp17] . Поэтому, в моем понимании, ranges::iota_view::iterator не будет удовлетворять требованиям Cpp17ForwardIterator , и то же самое относится, например, к. boost::counting_iterator.

Однако на практике я ожидаю, что реализации будут использовать std::iterator_traits::iterator_category для отправки соответствующая перегрузка алгоритма, как это делает PSTL. Поэтому я считаю, что пример кода в OP будет работать так, как задумано. Причина, по которой cmcstl2 не работает, заключается в том, что используемые iterator_category принадлежат __stl2 пространству имен , а не std.

...