Page MenuHomePhabricator

The other fix for equal algo
ClosedPublic

Authored by MikeDvorskiy on Mar 26 2019, 4:13 AM.

Details

Summary
  1. "serial execution instead of execution with a policy". Fixed.
  2. Got rid of the overheads connected with usage of std::distance for "forward" iterators. In that case we had N additional steps - an iterator seeking. Actually std::equal serial version (C++17 library) does it.

Diff Detail

Repository
rPSTL pstl

Event Timeline

MikeDvorskiy created this revision.Mar 26 2019, 4:13 AM
ldionne requested changes to this revision.Mar 26 2019, 6:34 AM
ldionne added inline comments.
include/pstl/internal/algorithm_impl.h
411

This can also be called as std::equal(first1, last1, first2, last2, pred). Is there any reason why we don't assume the presence of the usual std::equal?

428

This is all something that the serial std::equal does, and I'm uncomfortable with duplicating this logic here.

468

Can you please put your changes through clang-format?

This revision now requires changes to proceed.Mar 26 2019, 6:34 AM
MikeDvorskiy marked 3 inline comments as done.Mar 26 2019, 6:54 AM
MikeDvorskiy added inline comments.
include/pstl/internal/algorithm_impl.h
411
std::equal(first1, last1, first2, last2...

supported since C++14... Parallel STL open source version has min requirement C++11.

Actually, we can add a macro __PSTL_EQUAL_ALGO_VERSION_2_PRESENT
and re-call std::equal or our own serial implementation.

428

Hm... I've had a look.
std::equal really does it. So, OK, I' ll remove this duplicated logic.

468

Of course

ldionne added inline comments.Mar 26 2019, 6:58 AM
include/pstl/internal/algorithm_impl.h
411

The parallel algorithms are a C++17 addition, and as such they can require C++17 support.

  1. Usage of std::equal with "4 iterators" (due to it is available in C++ standard library since C++14)
  2. Clang formatted
ldionne accepted this revision.Mar 27 2019, 9:09 AM
This revision is now accepted and ready to land.Mar 27 2019, 9:09 AM

Can you please rebase on top of latest master? This doesn't apply cleanly anymore since the uglification patches.

MikeDvorskiy edited the summary of this revision. (Show Details)

Rebased on top of latest master (+ uglification)

The lost "__" has been returned.

ldionne requested changes to this revision.Apr 3 2019, 7:51 AM

This doesn't compile. Please run the tests.

This revision now requires changes to proceed.Apr 3 2019, 7:51 AM

+ compilation fixes (lost "__").

Actually, I have not yet got "Restructure test suite to follow libc++ standard layout" changes in my local repo because there are some problems with starting our test via make files on the restructured nested test folders..

But, my old "test_algo" with the "HEAD" of the master is passed.

The tests you must run when contributing to this repository are the CMake ones. ninja -C <build-dir> check-pstl should pass.

The tests you must run when contributing to this repository are the CMake ones. ninja -C <build-dir> check-pstl should pass.

To clarify -- it's entirely fine to have internal tests for your internal "fork" of PSTL and to run them. However, when contributing to the upstream repo, we expect the upstream tests to be passing.

We have the same situation for libc++ and libc++abi, where some vendors may have custom tests internally and they keep them passing. But when contributing upstream, they make sure that check-cxx is passing.

Currently I get:

<...>/llvm/pstl/include/pstl/internal/algorithm_impl.h:414:12: error: no matching function for call to 'equal'
    return std::equal(__first1, __last1, __first2, __last2, __p);
           ^~~~~~~~~~
<...>/llvm/pstl/include/pstl/internal/algorithm_impl.h:436:24: note: in instantiation of function template specialization '__pstl::__internal::__brick_equal<std::__1::__wrap_iter<int *>, std::__1::__wrap_iter<int *>, TestUtils::NonConstAdapter<std::__1::equal_to<int> > >' requested here
    return __internal::__brick_equal(__first1, __last1, __first2, __last2, __p, __is_vector);
                       ^
<...>/llvm/pstl/include/pstl/internal/glue_algorithm_impl.h:749:24: note: in instantiation of function template specialization '__pstl::__internal::__pattern_equal<const __pstl::execution::v1::sequenced_policy &, std::__1::__wrap_iter<int *>, std::__1::__wrap_iter<int *>, TestUtils::NonConstAdapter<std::__1::equal_to<int> >, std::__1::integral_constant<bool, false> >' requested here
    return __internal::__pattern_equal(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __p,

etc...

Louis,
regarding

..no matching function for call to 'equal' return std::equal(first1, last1, first2, last2, __p);

Do you have an option ?

-std=c++17

We discussed it, that std::equal with "4 iterators" version supported since C++17 only.

ldionne accepted this revision.Apr 3 2019, 10:16 AM

Louis,
regarding

..no matching function for call to 'equal' return std::equal(first1, last1, first2, last2, __p);

Do you have an option ?

-std=c++17

We discussed it, that std::equal with "4 iterators" version supported since C++17 only.

Yes, that was it. See r357609. But my point about running the upstream tests still stands.

This revision is now accepted and ready to land.Apr 3 2019, 10:16 AM
This revision was automatically updated to reflect the committed changes.

Of course. I will configure "ninja" for running the upstream test.

rodgert added a comment.EditedApr 4 2019, 12:36 PM

Of course. I will configure "ninja" for running the upstream test.

You don't strictly need ninja (ninja is awesome though), just CMake and make.

I typically create a parallel build tree, with build subdirs per working branch, e.g.

src/oss/pstl/master
src/oss/pstl/build/master

Given that, cd into build/master and -

cmake ../../master
make pstl-build-tests
make test