Parallel for loop with std::for_each and std::views::iota

Question

I want to set up an easy workaround for parallelized index-based for-loops using std::views.

For running in sequence the code looks like this:

int main() {

    //pseudo-random numbers

    random_device rd;
    default_random_engine eng(rd());
    uniform_int_distribution<int> distr(0, 100);

    auto r = ranges::views::iota(0, 10);
    vector<double> v(10, 1);
    for_each(r.begin(), r.end(), [&](int i) {v[i] = distr(eng); });
    for (auto&& i : v) cout << i << " "; cout << endl;
}

This works fine. I am using the standard version of std::for_each(), not the one in the ranges namespace, because those don't have the execution policies. Now the parallel version. Only difference:

for_each(execution::par, r.begin(), r.end(), [&](int i) {v[i] = distr(eng); });

MSVC gives an error:

error C2338: Parallel algorithms require forward iterators or stronger

I found a similar issue here: Using ranges::view::iota in parallel algorithms and I implemented the solution offered there:

    auto r = views::iota(0) | views::take(10);
    vector<double> v(10, 1);
    auto input_range = ranges::common_view(r);

    for_each(execution::par, ranges::begin(input_range), ranges::end(input_range), [&](int i) {v[i] = distr(eng); });
    for (auto&& i : v) cout << i << " "; cout << endl;

However, I am still facing the error

error C2338: Parallel algorithms require forward iterators or stronger.

Does someone know whether there is a solution to this issue?

score 6 · Answer 1 · answered Mar 23 '22 at 14:10

The return type of operator*() of views::iota's iterator is not a reference type but a value type, which makes it not a forward iterator but an input iterator in C++17. Since the C++17 parallel algorithm requires forward iterators, you cannot apply it to views::iota.

Does someone know whether there is a solution to this issue?

There is already a paper p2408r4 addressing this issue, so there is no simple solution in the standard until it is adopted.

Thanks a lot for your helpful answer! (I would upvote if I could :) ) — Urwald, Mar 23 '22 at 14:12

fir las · Accepted Answer · 2023-05-15T06:54:51.910

2

p2408 is adopted in C++23 now. In MSVC 19.34 (VS 17.4) or later, the code will compile if you turn on /std:c++latest (/std:c++20 will also work). EXAMPLE

edited May 15 '23 at 06:54

answered May 15 '23 at 04:13

fir las

46
7

1

[link to p2408](https://wg21.link/p2408). A TL;DR of what p2408 would be nice. – starball May 15 '23 at 07:00
Tried it, it works! – Urwald May 15 '23 at 08:41

Urwald · Answer 3 · 2022-03-30T09:30:12.470

Maybe just a small update. As was pointed out, the code does not compile with MSVC. The code does, however, compile with g++-11 since libstd++ does not do any up-front checking of the iterator category. However, the code runs always in serial, irrespective of the execution policy.

Important: The following is just my suggestion, please correct me if I am wrong. If you still want to implement an easy parallelized index-based for loop, you can make use of STL containers rather than views:

template<typename Policy, typename func>
void parallel_for(Policy p, int first, int last, func f) {

    vector<int> idxs(last - first);
    iota(idxs.begin(), idxs.end(), first);
    for_each(p, begin(idxs), end(idxs), f);
}

Instead of having a view, we now just store the indices in a vector<int>. This of course comes with a memory and runtime overhead since memory for the container must be allocated and the container must be filled with the indices. The function in action could look like this:

int fib(int i) {
    if (i <= 1)
        return i;
    return fib(i - 1) + fib(i - 2);
}

int main() {

    vector<vector<double>> mat(100, vector<double>(100, 1));

    parallel_for(execution::par, 0, mat.size(), [&mat](int i) {

        for (int j = 0; j < mat[i].size(); ++j) {
            mat[i][j] = fib(40);
        }
        });
}

Parallel for loop with std::for_each and std::views::iota

3 Answers3

Linked