2917. Parallel algorithms cannot easily work with InputIterators

Section: 26 [algorithms], 26.10 [numeric.ops] Status: Resolved Submitter: United States Opened: 2017-02-03 Last modified: 2020-09-06

Priority: Not Prioritized

View other active issues in [algorithms].

View all other issues in [algorithms].

View all issues with Resolved status.

Discussion:

Addresses US 156

Parallel algorithms cannot easily work with InputIterators, as any attempt to partition the work is going to invalidate iterators used by other sub-tasks. While this may work for the sequential execution policy, the goal of that policy is to transparently switch between serial and parallel execution of code without changing semantics, so there should not be a special case extension for this policy. There is a corresponding concern for writing through OutputIterators. Note that the input iterator problem could be mitigated, to some extent, by serially copying/moving data out of the input range and into temporary storage with a more favourable iterator category, and then the work of the algorithm can be parallelized. If this is the design intent, a note to confirm that in the standard would avoid future issues filed in this area. However, the requirement of an algorithm that must copy/move values into intermediate storage may not be the same as those acting immediately on a dereferenced input iterator, and further issues would be likely. It is not clear that anything can be done to improve the serial nature of writing to a simple output iterator though.

Proposed change: All algorithms in the <algorithm> and <numeric> headers that take an execution policy and an InputIterator type should update that iterator to a ForwardIterator, and similarly all such overloads taking an OutputIterator should update that iterator to a ForwardIterator.

(Conversely, if the design intent is confirmed to support input and output iterators, add a note to state that clearly and avoid confusion and more issues by future generations of library implementers.)

[2017-02-13, Alisdair comments]

The pre-Kona mailing has two competing papers that provide wording to address #2917, sequential constraints on parallel algorithms. They should probably be cross-refrenced by the issue:

  1. P0467R1: Iterator Concerns for Parallel Algorithms

  2. P0574R0: Algorithm Complexity Constraints and Parallel Overloads

[2017-03-12, post-Kona]

Resolved by P0467R2.

Proposed resolution: