This is an archive of the discontinued LLVM Phabricator instance.

[libc++][PSTL] Implement std::is_partitioned
ClosedPublic

Authored by philnik on Jun 13 2023, 1:21 PM.

Details

Reviewers
ldionne
Group Reviewers
Restricted Project
Commits
rG3a7876f6e2b0: [libc++][PSTL] Implement std::is_partitioned

Diff Detail

Event Timeline

philnik created this revision.Jun 13 2023, 1:21 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 13 2023, 1:21 PM
philnik requested review of this revision.Jun 13 2023, 1:21 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 13 2023, 1:22 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
philnik updated this revision to Diff 531053.Jun 13 2023, 1:44 PM

Update documentations

philnik updated this revision to Diff 531393.Jun 14 2023, 9:45 AM

Try to fix CI

ldionne requested changes to this revision.Jun 14 2023, 12:39 PM
ldionne added a subscriber: ldionne.
ldionne added inline comments.
libcxx/include/__algorithm/pstl_is_partitioned.h
42

You forgot to pass the policy to the find_if call.

Also, this could be std::none_of(__policy, __g_first, __g_last, __g_pred);.

libcxx/test/std/algorithms/alg.sorting/alg.partitions/pstl.is_partitioned.pass.cpp
28

You're missing a test that is_partition(empty-range) is true.

33

paritioned => partitioned. You probably want to search and replace globally, I can see other instances of this. You also have a few parititoned around.

45

I think this comment is incomplete

This revision now requires changes to proceed.Jun 14 2023, 12:39 PM
philnik updated this revision to Diff 531487.Jun 14 2023, 1:33 PM
philnik marked 4 inline comments as done.

Address comments

libcxx/test/std/algorithms/alg.sorting/alg.partitions/pstl.is_partitioned.pass.cpp
45

This is the empty range test.

ldionne accepted this revision.Jun 15 2023, 9:41 AM

LGTM w/ fix and test

libcxx/include/__algorithm/pstl_is_partitioned.h
42–43

Technically, I think we could implement it this way instead:

__g_first = std::find_if_not(__policy, __g_first, __g_last, __g_pred);
if (__g_first == __g_last)
  return true;
++__g_first;
return std::none_of(__policy, __g_first, __g_last, __g_pred);

This way, we avoid running the predicate twice on the first element that doesn't satisfy the predicate (which we do right now). This also mirrors what we do for the serial version of the algorithm. If you agree, I think it might be useful to add a test for this. In particular, we could have a libc++ specific test that ensures that we satisfy this complexity guarantee (from the serial version):

At most std::distance(first, last) applications of p.

Could you also take a look at whether this is tested in the serial version, where that's definitely a requirement?

This revision is now accepted and ready to land.Jun 15 2023, 9:41 AM
This revision was automatically updated to reflect the committed changes.
philnik marked an inline comment as done.