The other fix for equal algo

[MikeDvorskiy]

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.

[ldionne]

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?

[MikeDvorskiy]

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]

include/pstl/internal/algorithm_impl.h

411

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

[MikeDvorskiy]

1. Usage of std::equal with "4 iterators" (due to it is available in C++ standard library since C++14)
2. Clang formatted

[ldionne]

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

[MikeDvorskiy]

Rebased on top of latest master (+ uglification)

[MikeDvorskiy]

The lost "__" has been returned.

[ldionne]

This doesn't compile. Please run the tests.

[MikeDvorskiy]

+ 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.

[ldionne]

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

[ldionne]

In D59813#1453466, @ldionne wrote:

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.

[ldionne]

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...

[MikeDvorskiy]

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]

In D59813#1453536, @MikeDvorskiy wrote:

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.

[MikeDvorskiy]

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

[rodgert]

In D59813#1454566, @MikeDvorskiy wrote:

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

include/pstl/internal/algorithm_impl.h

 #endif
 
 //------------------------------------------------------------------------
 // equal
 //------------------------------------------------------------------------
 
 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
 bool
+__brick_equal(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
+              _ForwardIterator2 __last2, _BinaryPredicate __p, /* IsVector = */ std::false_type) noexcept
+{
+    return std::equal(__first1, __last1, __first2, __last2, __p);
+}
+
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
+bool
+__brick_equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
+              _RandomAccessIterator2 __last2, _BinaryPredicate __p, /* is_vector = */ std::true_type) noexcept
+{
+    if (__last1 - __first1 != __last2 - __first2)
+        return false;
+
+    return __unseq_backend::__simd_first(__first1, __last1 - __first1, __first2,
+                                         __internal::__not_pred<_BinaryPredicate>(__p))
+               .first == __last1;
+}
+
+template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate,
+          class _IsVector>
+bool
+__pattern_equal(_ExecutionPolicy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
+                _ForwardIterator2 __last2, _BinaryPredicate __p, _IsVector __is_vector, /* is_parallel = */
+                std::false_type) noexcept
+{
+    return __internal::__brick_equal(__first1, __last1, __first2, __last2, __p, __is_vector);
+}
+
+#if __PSTL_USE_PAR_POLICIES
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate,
+          class _IsVector>
+bool
+__pattern_equal(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
+                _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __p,
+                _IsVector __is_vector, /*is_parallel=*/std::true_type)
+{
+    if (__last1 - __first1 != __last2 - __first2)
+        return false;
+
+    return __internal::__except_handler([&]() {
+        return !__internal::__parallel_or(
+            std::forward<_ExecutionPolicy>(__exec), __first1, __last1,
+            [__first1, __first2, __p, __is_vector](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
+                return !__internal::__brick_equal(__i, __j, __first2 + (__i - __first1), __first2 + (__j - __first1),
+                                                  __p, __is_vector);
+            });
+    });
+}
+#endif
+
+//------------------------------------------------------------------------
+// equal version for sequences with equal length
+//------------------------------------------------------------------------
+
+template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
+bool
 __brick_equal(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _BinaryPredicate __p,
               /* IsVector = */ std::false_type) noexcept
 {
     return std::equal(__first1, __last1, __first2, __p);
 }
 
 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
 bool
 __brick_equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,

include/pstl/internal/glue_algorithm_impl.h

return std::equal(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2,
                       __pstl::__internal::__pstl_equal());
 }
 
 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
 equal(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
       _ForwardIterator2 __last2, _BinaryPredicate __p)
 {
-    if (std::distance(__first1, __last1) == std::distance(__first2, __last2))
-        return std::equal(__first1, __last1, __first2, __p);
-
-    return false;
+    using namespace __pstl;
+    return __internal::__pattern_equal(
+        std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __p,
+        __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1>(__exec),
+        __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1>(__exec));
 }
 
 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
 equal(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
       _ForwardIterator2 __last2)
 {
     return equal(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2,