2538. [parallel.ts] Requirements on data race behavior of iterators and swap should be clarified

Section: 99 [parallel.ts::parallel.alg.general.exec] Status: NAD Submitter: Robert Geva Opened: 2015-09-22 Last modified: 2015-10-21

Priority: Not Prioritized

View all issues with NAD status.

Discussion:

Addresses: parallel.ts

Parallel algorithms as of N4352 in general need to assume that iterator operations and swap have the expected data race behavior. For example, sort would not work if the exchange operation were thread-unsafe and, for example, always updated a single unprotected global counter, independent of the objects being swapped. A parallel sort has to be able to assume that disjoint pairs of objects can be swapped concurrently, i.e. that elemental functions have the same sort of thread-safety behavior that we generally promise for the standard library versions. I don't see that assumption stated anywhere.

We should then probably also be clearer that the 99 [parallel.ts::parallel.alg.general.exec] ordering rules are further constrained by algorithm correctness requirements, and by the requirement not to introduce data races when elemental functions satisfy their thread-safety expectations.

It's tempting to generally add basic thread-safety requirements to various library requirements clauses. But that adds backwards compatibility issues for single-threaded code.

Most probably this applies to other operations as well. We do state in [parallel.alg.general.user]:

Function objects passed into parallel algorithms as objects of type BinaryPredicate, Compare, and BinaryOperation shall not directly or indirectly modify objects via their arguments.

But that only seems to cover the easy cases.

Proposed resolution: