This is an archive of the discontinued LLVM Phabricator instance.

[libc++][PSTL] Parallelize random_access_iterator
ClosedPublic

Authored by gonzalobg on Jul 2 2023, 9:42 AM.

Details

Reviewers
ldionne
philnik
Group Reviewers
Restricted Project
Commits
rG0e2de665f34f: [libc++][PSTL] Parallelize random_access_iterator
Summary

P2408 requires this for C++23, but implementing it in C++20 is safe
because the only code impacted would be code that violated a
precondition of the parallel algorithm. It was P2408 intent to
enable implementations to backport this to C++20.

Closes #63447 .

Diff Detail

Event Timeline

gonzalobg created this revision.Jul 2 2023, 9:42 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 2 2023, 9:42 AM
gonzalobg requested review of this revision.Jul 2 2023, 9:42 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 2 2023, 9:42 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript

Could you upload the patch with context (i.e. use arc or add -U9999 when generating the patch)?

It feels a bit wrong to me that we check for random_access_iterator in a classic algorithm, but I guess that is fine. Do all Cpp17RandomAccessIterators meet the random_access_iterator requirements? If yes, I'd just go with using either __has_random_access_iterator or random_access_iterator. We'd probably want to diagnose iterators which advertise themselves as such while not actually being random_access_iterators if we go that route.

libcxx/include/__algorithm/pstl_traits.h
26 ↗(On Diff #536608)

This isn't actually pstl-specific, so IMO this should live in iterator_traits or something like that.

gonzalobg updated this revision to Diff 540982.Jul 17 2023, 6:00 AM
  • Generated with -U9999
  • Moved utility to __iterator/concepts.h (requires random_access_iterator concept)
  • Removed pstl_traits.h file
philnik accepted this revision.Jul 17 2023, 9:01 AM

Thanks for the patch! LGTM.

This revision is now accepted and ready to land.Jul 17 2023, 9:01 AM

Please make sure the CI is run and green before landing.

ldionne added inline comments.Jul 17 2023, 4:29 PM
libcxx/include/__algorithm/pstl_any_all_none_of.h
16

Why is this include changed, since we didn't touch the contents of the file? Was the include unnecessary in the first place?

libcxx/include/__algorithm/pstl_find.h
18

Same comment.

libcxx/include/__algorithm/pstl_transform.h
15

Same comment.

libcxx/include/__iterator/concepts.h
290

(not attached to the diff) Can you folks think of a way to test this? I can't, but asking just in case.

philnik added inline comments.Jul 17 2023, 5:21 PM
libcxx/include/__iterator/concepts.h
290

We already test with C++20 iterators, which should be good enough I think. Performance can only be tested through benchmarks anyways, so I think that's out of scope for this, since we don't have any PSTL benchmarks yet. (Reminds me that we should log the result of our benchmarks...)

gonzalobg added inline comments.Jul 18 2023, 3:29 AM
libcxx/include/__iterator/concepts.h
290

(not attached to the diff) Can you folks think of a way to test this? I can't, but asking just in case.

I don't know how to test this (I thought quite a bit about it, but benchmarks are the only way I have to test this right now).

If someone figures out a way to test this without requiring benchmarks, that would be helpful for libstdc++ as well (I've sent a similar patch there).

gonzalobg updated this revision to Diff 541430.Jul 18 2023, 3:31 AM

Remove unnecessary iterator/iterator_traits.h and iterator/concepts.h includes.

gonzalobg updated this revision to Diff 541435.Jul 18 2023, 3:52 AM

Forgot to remove header from one file.

Can you rebase this onto main? The diff fails to apply in the CI.

gonzalobg updated this revision to Diff 542071.Jul 19 2023, 9:27 AM

Rebased on top of main.

gonzalobg updated this revision to Diff 543970.Jul 25 2023, 7:40 AM

Re-add iterator_traits to some files (required for modules).

gonzalobg updated this revision to Diff 543974.Jul 25 2023, 7:44 AM

Re-add missing module files.

@ldionne @philnik I've fixed all failures except for the current three. Can it be that they are caused by something that's not in my PR ?

@ldionne @philnik I've fixed all failures except for the current three. Can it be that they are caused by something that's not in my PR ?

It looks like the last build is green. Can you rebase before landing to make sure the CI is really green?

Rebased on main.

Name: Gonzalo Brito Gadeschi
Email: gonzalob@nvidia.com

gonzalobg updated this revision to Diff 546350.Aug 2 2023, 1:19 AM

Rebased one last time.

gonzalobg updated this revision to Diff 546796.Aug 3 2023, 4:08 AM

Fix tests after rebase.

This revision was landed with ongoing or failed builds.Aug 7 2023, 8:58 AM
This revision was automatically updated to reflect the committed changes.