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

409

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?

426

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

466

Can you please put your changes through clang-format?

[MikeDvorskiy]

include/pstl/internal/algorithm_impl.h

409

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.

426

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

466

Of course

[ldionne]

include/pstl/internal/algorithm_impl.h

409

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, 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 !brick_equal(__i, __j, __first2 + (__i - __first1), __first2 + (__j - __first1), __p,
+                                    __is_vector);
+            });
+    });
+}
+#endif
+
+//------------------------------------------------------------------------
+// equal version for sequences with equal lenght
+//------------------------------------------------------------------------
+
+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,
             _BinaryPredicate __p, /* is_vector = */ std::true_type) noexcept
if (__last - __first == __s_last - __s_first)
                                                    __pred, __is_vector, std::true_type());
         return __res ? __first : __last;
     }
     else
     {
         return except_handler([&]() {
             return internal::parallel_find(
                 std::forward<_ExecutionPolicy>(__exec), __first, __last,
-                [__last, __s_first, __s_last, __pred, __is_vector](_ForwardIterator1 __i,
-                                                                   _ForwardIterator1 __j) {
+                [__last, __s_first, __s_last, __pred, __is_vector](_ForwardIterator1 __i, _ForwardIterator1 __j) {
                     return internal::find_subrange(__i, __j, __last, __s_first, __s_last, __pred, false, __is_vector);
                 },
                 std::greater<typename std::iterator_traits<_ForwardIterator1>::difference_type>(), /*is_first=*/false);
         });
     }
 }
 #endif
 
struct _PartitionRange
         _ForwardIterator __pivot;
         _ForwardIterator __end;
     };
 
     return except_handler([&]() {
         _PartitionRange __init{__last, __last, __last};
 
         // lambda for merging two partitioned ranges to one partitioned range
-        auto __reductor = [&__exec, __is_vector](_PartitionRange __val1,
-                                                 _PartitionRange __val2) -> _PartitionRange {
+        auto __reductor = [&__exec, __is_vector](_PartitionRange __val1, _PartitionRange __val2) -> _PartitionRange {
             auto __size1 = __val1.__end - __val1.__pivot;
             auto __size2 = __val2.__pivot - __val2.__begin;
             auto __new_begin = __val2.__begin - (__val1.__end - __val1.__begin);
 
             // if all elements in left range satisfy pred then we can move new pivot to pivot of right range
             if (__val1.__end == __val1.__pivot)
             {
                 return {__new_begin, __val2.__pivot, __val2.__end};
return except_handler([&]() {
                     std::forward<_ExecutionPolicy>(__exec), __val1.__pivot, __val1.__pivot + __size2,
                     [__val1, __val2, __is_vector](_ForwardIterator __i, _ForwardIterator __j) {
                         brick_swap_ranges(__i, __j, __val2.__begin + (__i - __val1.__pivot), __is_vector);
                     });
                 return {__new_begin, __val1.__pivot + __size2, __val2.__end};
             }
         };
 
-        _PartitionRange __result = par_backend::parallel_reduce(
-            std::forward<_ExecutionPolicy>(__exec), __first, __last, __init,
+        _PartitionRange __result =
+            par_backend::parallel_reduce(std::forward<_ExecutionPolicy>(__exec), __first, __last, __init,
                                          [__pred, __is_vector, __reductor](_ForwardIterator __i, _ForwardIterator __j,
                                                                            _PartitionRange __value) -> _PartitionRange {
                                              //1. serial partition
                                              _ForwardIterator __pivot = brick_partition(__i, __j, __pred, __is_vector);
 
                                              // 2. merging of two ranges (left and right respectively)
                                              return __reductor(__value, {__i, __pivot, __j});
                                          },
                                          __reductor);
         return __result.__pivot;
     });
 }
 #endif
 
 //------------------------------------------------------------------------
 // stable_partition
 //------------------------------------------------------------------------
struct _PartitionRange
         _BidirectionalIterator __pivot;
         _BidirectionalIterator __end;
     };
 
     return except_handler([&]() {
         _PartitionRange __init{__last, __last, __last};
 
         // lambda for merging two partitioned ranges to one partitioned range
-        auto __reductor = [__is_vector](_PartitionRange __val1,
-                                        _PartitionRange __val2) -> _PartitionRange {
+        auto __reductor = [__is_vector](_PartitionRange __val1, _PartitionRange __val2) -> _PartitionRange {
             auto __size1 = __val1.__end - __val1.__pivot;
             auto __new_begin = __val2.__begin - (__val1.__end - __val1.__begin);
 
             // if all elements in left range satisfy pred then we can move new pivot to pivot of right range
             if (__val1.__end == __val1.__pivot)
             {
                 return {__new_begin, __val2.__pivot, __val2.__end};
             }

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, __pstl::internal::pstl_equal());
+    return equal(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2,
+                 __pstl::internal::pstl_equal());
 }
 
 // [alg.move]
 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
 __pstl::internal::enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
 move(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __d_first)
 {
     using namespace __pstl;