parallel algorithm constraints: element access functions are not per object?

[dietma...@gmail.com]

I'm trying to determine the constraints imposed by the standard on users of the parallel algorithms. The relevant section in the standard seems to be 25.2 which defines element access functions and their concurrent use (in 25.2.3). The basic constraints are quite straight forward (see <http://stackoverflow.com/a/41333175/1120273> for a write-up). Unfortuately, I can't see any constraint which prohibits invocations of [mutating, at least] element access functions on the same object from different threads! That is, it seems a parallel algorithm is allowed to the moral equivalent of something like this:

template <typename FwdIt>
void use_iterator(FwdIt it) {
auto f0 = std::async([&]{ ++it; return true; });
auto f1 = std::async([&]{ ++it; return true; });
f0.get();
f1.get();
}

Of course, this use is silly and I don't think any parallel implementation of an algorithm would do something like this. However, I don't see it prohibited. Since the element access functions are required to not cause data races it seems the iterators would need to synchronise their state which is almost certainly not intended.

Is there somewhere a guarantee that the element access functions are invoked only on different objects from different threads or when invoked in an interleaved manner? ...or this lack of guarantee a defect which needs to be addressed?

[Jens Maurer]

Hm... We have 25.2.5p2

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

For the functors (e.g. for_each), we say they will be applied
only once (for instance), so we're probably good.

For the iterators (which are also element access functions),
we're less clear, it seems.

Jens

[dietma...@gmail.com]

Sure - the behavior of the algorithms is required to be the same. There are, however, assumption made by the algorithms about the element access functions to achieve the same behavior. Notably that the element access functions are free of data races and do not introduce dead-lock. To implement these guarantees efficiently I think it is necessary that algorithms are constrained in how they can use the passed objects. In particular, I think there needs to be a guarantee that parallel algorithms do not access non-const element access functions on the same object from different threads. Considering the vectorization example I think the algorithms may need to be even further constrained but I don't even know how these constraints would need to be expressed.

The specification in this area seems to be written along the lines of "everybody knows what is meant here". Although I agree with the general sentiment, I think it is necessary to formulate both how users are constrained with respect to the customization points as well as how algorithms are contrained on how these are used. Especially the latter is entirely lacking. Neither the user of the parallel algorithms will be entirely free on what can be used with these algorithms nor will the implementer of the algorithms be entirely free on how the entities passed are used.