Can I use std::transform in place with a parallel execution policy?

user_8732793 0
Viewed 3115

If I am not mistaken, I can make std::transform perform in place by using the same range as an input and output iterator. Assume I have some std::vector object vec, then I would write

std::transform(vec.cbegin(),vec.cend(),vec.begin(),unary_op)

using a suitable unary operation unary_op.

Using the C++17 standard, I would like to execute the transform in parallel by sticking an std::execution::par in there as the first argument. This would make the function go from overload (1) to (2) in the cppreference article on std::transform. However the comments to this overload says:

unary_op [...] must not invalidate any iterators, including the end iterators, or modify any elements of the ranges involved. (since C++11)

Does "modify any elements" really mean I cannot use the algorithm in place or is this talking about a different detail that I misinterpreted?

c++17 parallel-processing stl c++
3 Answers

I believe that it's talking about a different detail. The unary_op takes an element of the sequence and returns a value. That value is stored (by transform) into the destination sequence.

So this unary_op would be fine:

int times2(int v) { return 2*v; }

but this one would not:

int times2(int &v) { return v*=2; }

But that's not really what you're asking about. You want to know if you can use the unary_op version of transform as a parallel algorithm with the same source and destination range. I don't see why not. transform maps a single element of the source sequence to a single element of the destination sequence. However, if your unary_op isn't really unary, (i.e, it references other elements in the sequence - even if it only reads them, then you will have a data race).

user_9924900

To quote the standard here

[alg.transform.1]

op [...] shall not invalidate iterators or subranges, or modify elements in the ranges

this forbids your unary_op to modify either the value given as argument or the container itself.

auto unary_op = [](auto& value) 
{ 
    value = 10;    // this is bad
    return value;
}

auto unary_op = [&vec](auto const& value) 
{ 
    vec[0] = value;   // also bad
    return value;
}

auto unary_op = [&vec](auto& value) 
{ 
    vec.erase(vec.begin());   // nope 
    return value;
}

However, the follwing is ok.

auto unary_op = [](auto& value)  // const/ref not strictly needed
{         
    return value + 10;   // totally fine
}

auto unary_op = [&vec](auto& value)
{         
    return value + vec[0];   // ok in sequential but not in parallel execution
}

Independent from the UnaryOperation we have

[alg.transform.5]

result may be equal to first in case of unary transform [...].

meaning in-place operations are explicitly allowed.

Now

[algorithms.parallel.overloads.2]

Unless otherwise specified, the semantics of ExecutionPolicy algorithm overloads are identical to their overloads without.

means that the execution policy has no user visible difference on the algorithm. You can expect the algorithm to yield the exact same result as if you wouldn't specify an execution policy.

user_62053790

As you can see in the example of the link you cited, modifying any elements doesn't does mean all types of modifying on the elements:

The signature of the function should be equivalent to the following:

Ret fun(const Type &a);

That includes modification on the elements. In the worst case if you use the same iterator for destination, the modification should not cause invalidation of iterators that is e.g. a push_back to vector or erasing from vector which will probably cause the invalidation of iterators.

See an example of failure which you SHOULDN'T do Live.

user_109338090
Related