Skip to content

P3179 R7 C++ parallel range algorithms #1815

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
dhollman opened this issue Mar 17, 2024 · 18 comments
Open

P3179 R7 C++ parallel range algorithms #1815

dhollman opened this issue Mar 17, 2024 · 18 comments
Labels
B2 - improvement Bucket 2 as described by P0592: bug fixes, performance improvements, integration fixes for/between e C++26 Targeted at C++26 IS Ship vehicle: IS LWG Library lwg-pending LWG Chair needs to disposition size - medium paper size estimate
Milestone

Comments

@dhollman
Copy link
Collaborator

P3179RO C++ parallel range algorithms (Ruslan Arutyunyan,
Alexey Kukanov)

@dhollman dhollman added SG9 Ranges SG C++26 Targeted at C++26 SG1 Concurrency size - medium paper size estimate labels Mar 17, 2024
@foonathan
Copy link
Member

SG9 discussed it in Tokyo on Wednesday: https://wiki.edg.com/bin/view/Wg21tokyo2024/NotesSG9P3179R0

Poll: std::ranges::for_each[_n] (non-execution policy) returns the iterator and the function object, as you could accumulate state in the function object. The version of std::ranges::for_each[_n] with an execution policy should not return the function object (you can't accumulate state in there and for consistency with the non-range parallel version).

SF F N A SA
2 4 2 0 0

Attendance: 8
Author: N
Outcome: Strong consensus in favor.

Poll: std::ranges::for_each[_n] with execution policy should return the computed end iterator.

SF F N A SA
4 2 2 0 0

Attendance: 9
Author: N
Outcome: Strong consensus in favor.

Poll: All other std::ranges algorithms with execution policy should return the same result type as the std::ranges version without execution policy.

Unanimous consent.
Attendance: 9

Poll: Like the C++17 parallel algorithms, the std::ranges parallel version should also allow forward iterators, not just random access iterators. This means that the implementation might need to silently fallback to serial code, but can parallelize some special cases of non-random access iterators that would be prohibited otherwise.

SF F N A SA
3 2 3 1 1

Attendance: 10
Author: N, I see the value for both directions.
Outcome: Weak consensus in favor.
SA: This is user-hostile and something we already warn against. We shouldn't standardize something we warn against.

Poll: The std::ranges parallel algorithms should require that the function objects passed as arguments have a const-qualified operator().

SF F N A SA
0 7 2 0 0

Attendance: 10
Author: F
Outcome: Strong consensus in favor.
Abstain: I would like field experience before deciding.

The author will incorporate feedback and come back with a new revision. There were also concerned raised about the explosion of algorithm variants when this and a potential future paper proposing sender/receiver based async algorithms are both added. A joint session with SG1 and SG9 and potentially LEWG as a whole is probably necessary to address those concerns.

@foonathan foonathan added the needs-revision Paper needs changes before it can proceed label Mar 22, 2024
@wg21bot
Copy link
Collaborator

wg21bot commented Apr 17, 2024

P3179R0 C++ parallel range algorithms (Ruslan Arutyunyan, Alexey Kukanov)

@wg21bot wg21bot removed the needs-revision Paper needs changes before it can proceed label Apr 17, 2024
@wg21bot wg21bot added this to the 2024-telecon milestone Apr 17, 2024
@wg21bot
Copy link
Collaborator

wg21bot commented May 22, 2024

P3179R1 C++ parallel range algorithms (Ruslan Arutyunyan, Alexey Kukanov)

@wg21bot wg21bot changed the title P3179 R0 C++ parallel range algorithms P3179 R1 C++ parallel range algorithms May 22, 2024
@inbal2l inbal2l added the IS Ship vehicle: IS label May 22, 2024
@inbal2l
Copy link
Collaborator

inbal2l commented May 22, 2024

@dhollman @foonathan @ogiroux - do you think you could have a joint session for this in St. Louis?
Or does it require more time in SG9 before that?

@ogiroux
Copy link
Collaborator

ogiroux commented Jun 28, 2024

SG1/SG9 in St Louis

Continue work on P3179R2 for IS'26 with these notes:

  1. RandomAccess for inputs and outputs
  2. Iterators for outputs
  3. We believe the overloads are worth it
    SF F N A SA
    7 4 2 1 0
    A: it's probably worth waiting a bit to unify with the S&R updates

@wg21bot
Copy link
Collaborator

wg21bot commented Jul 16, 2024

P3179R2 C++ parallel range algorithms (Ruslan Arutyunyan, Alexey Kukanov, Bryce Adelstein Lelbach)

@wg21bot wg21bot changed the title P3179 R1 C++ parallel range algorithms P3179 R2 C++ parallel range algorithms Jul 16, 2024
@wg21bot
Copy link
Collaborator

wg21bot commented Oct 17, 2024

P3179R3 C++ parallel range algorithms (Ruslan Arutyunyan, Alexey Kukanov, Bryce Adelstein Lelbach)

@wg21bot wg21bot changed the title P3179 R2 C++ parallel range algorithms P3179 R3 C++ parallel range algorithms Oct 17, 2024
@ogiroux ogiroux removed the SG1 Concurrency label Nov 19, 2024
@ogiroux
Copy link
Collaborator

ogiroux commented Nov 19, 2024

Forward P3179R3 to LEWG with the following notes:

  1. The intention is that algorithms call begin/end only once, in serial code
    (we do not think any new words are needed)
  2. The intention is that mismatch, transform and equal assume the unsized range
    is at least as large as the sized one (UB / precondition) or require && sized
    SF F N A SA
    4 8 0 0 0
    Unanimous consent

@dhollman
Copy link
Collaborator Author

SG9 in Wrocław

SG9 discussed this paper in Wrocław. We took the following polls:


Change mismatch and equal to require sized_range for both inputs ("&& instead of ||").

SF F N A SA
4 3 1 0 0

Attendance: 11
Authors: SF, F

Consensus


Change transform to require sized_range for both inputs ("&& instead of ||"), with the plan to relax these constraints once we have a way to statically detect infinite ranges.

SF F N A SA
3 3 0 1 1

Consensus
Authors: F, SA


We also provided the following advice to the authors:

Authors will exhaustively list the algorithms that are being given execution policy overloads (and those in ranges that are being excluded). Add these lists to the paper with a brief justification. Also verify that the list of "|| constraints" we discussed is exhaustive.

Make a change to nothrow-random-access-iterator to subsume nothrow-bidirectional-iterator and add the latter with the help of a wording expert.

@dhollman
Copy link
Collaborator Author

Also in Wrocław, SG9 took the following poll related to this paper, as part of the discussion of P3490R0:


We want to remove the "legacy" overload that includes only an iterator as output for convenience, because we know it's unsafe.

SF F N A SA
4 4 0 0 0

Authors: F
Attendance: 11

Strong Consensus


Forward P3179R3 with the changes in P3490R0 (as updated above) to LEWG for inclusion in C++26 with these changes polled above.

SF F N A SA
4 5 0 0 0

Authors: SF, F
Attendance: 11

Strong Consensus

@wg21bot
Copy link
Collaborator

wg21bot commented Dec 18, 2024

P3179R4 C++ parallel range algorithms (Ruslan Arutyunyan, Alexey Kukanov, Bryce Adelstein Lelbach)

@wg21bot wg21bot modified the milestones: 2024-telecon, 2025-telecon Dec 18, 2024
@wg21bot wg21bot changed the title P3179 R3 C++ parallel range algorithms P3179 R4 C++ parallel range algorithms Dec 18, 2024
@wg21bot
Copy link
Collaborator

wg21bot commented Jan 14, 2025

P3179R5 C++ parallel range algorithms (Ruslan Arutyunyan, Alexey Kukanov, Bryce Adelstein Lelbach)

@wg21bot wg21bot changed the title P3179 R4 C++ parallel range algorithms P3179 R5 C++ parallel range algorithms Jan 14, 2025
@inbal2l inbal2l added LEWG Library Evolution ready-for-library-evolution-meeting-review This paper needs to be discussed at a Library Evolution meeting and removed SG9 Ranges SG labels Jan 14, 2025
@inbal2l
Copy link
Collaborator

inbal2l commented Feb 9, 2025

P3179R6 C++ parallel range algorithms (Ruslan Arutyunyan, Alexey Kukanov, Bryce Adelstein Lelbach)

@inbal2l inbal2l changed the title P3179 R5 C++ parallel range algorithms P3179 R6 C++ parallel range algorithms Feb 9, 2025
@bstamour bstamour moved this to In Progress in 2025 Hagenberg LWG Schedule Feb 14, 2025
@bstamour
Copy link
Collaborator

bstamour commented Feb 14, 2025

LWG looked at R6 Friday morning in Hagenberg.

minutes: https://wiki.edg.com/bin/view/Wg21hagenberg2025/LWGFridayLateMorning

@inbal2l
Copy link
Collaborator

inbal2l commented Feb 27, 2025

(Out of order)

2025-02-10 Library Evolution Hagenberg Meeting

P3179R6: C++ parallel range algorithms

2025-02-10 Library Evolution Hagenberg Minutes

Champion: Ruslan Arutyunyan
Chair: Inbal Levi / Andreas Weis
Minute Taker: Bronek Kozicki

Summary

POLL: In: “copy_if” and similar algorithms modify the behaviour into: return the first element which wasn’t copied which comply with the predicate or sentinel.

SF F N A SA
11 12 1 0 0

Attendance: 29 (IP) + 4 (R)
Author's Position: F
Outcome: Strong consensus in favor

POLL: Apply the design and wording changes described above and forward P3179R7 including following algorithms: “contains”, “for_each”, “for_each_n”, “copy”, “copy_n”, “copy_if”, “rotate_copy”, “reverse_copy”, “partition_copy”, “merge”, “set_union” and algorithms with the similar pattern and forward the paper to LWG for C++26.

SF F N A SA
11 9 2 0 0

Attendance: 30 (IP) + 6 (R)
Author's Position: SFx3
Outcome: Strong Consensus in favor.

Next Steps

Apply design (+ wording) changes for: "copy_if", publish new revision, and forward P3179R7 to LWG for C++26.

@inbal2l inbal2l added LWG Library lwg-pending LWG Chair needs to disposition and removed LEWG Library Evolution ready-for-library-evolution-meeting-review This paper needs to be discussed at a Library Evolution meeting labels Feb 27, 2025
@inbal2l inbal2l added the B2 - improvement Bucket 2 as described by P0592: bug fixes, performance improvements, integration fixes for/between e label Mar 18, 2025
@wg21bot wg21bot changed the title P3179 R6 C++ parallel range algorithms P3179 R5 C++ parallel range algorithms Mar 19, 2025
@wg21bot wg21bot changed the title P3179 R5 C++ parallel range algorithms P3179 R6 C++ parallel range algorithms Mar 19, 2025
@wg21bot
Copy link
Collaborator

wg21bot commented Mar 19, 2025

P3179R7 C++ parallel range algorithms (Ruslan Arutyunyan, Alexey Kukanov, Bryce Adelstein Lelbach)

@wg21bot wg21bot changed the title P3179 R6 C++ parallel range algorithms P3179 R7 C++ parallel range algorithms Mar 19, 2025
@bstamour
Copy link
Collaborator

bstamour commented Mar 28, 2025

LWG reviewed R7 on 2025-03-28.

Meeting minutes: https://wiki.edg.com/bin/view/Wg21telecons2025/P3179-20250328

@bstamour
Copy link
Collaborator

bstamour commented Apr 4, 2025

LWG reviewed R8 on 2025-04-04.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
B2 - improvement Bucket 2 as described by P0592: bug fixes, performance improvements, integration fixes for/between e C++26 Targeted at C++26 IS Ship vehicle: IS LWG Library lwg-pending LWG Chair needs to disposition size - medium paper size estimate
Projects
Status: In Progress
Status: No status
Development

No branches or pull requests

6 participants