This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[PATCH] Improve implementation of parallel equal()
- From: Thomas Rodgers <trodgers at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org, libstdc++ at gcc dot gnu dot org
- Date: Tue, 16 Apr 2019 12:39:40 -0700
- Subject: [PATCH] Improve implementation of parallel equal()
* include/pstl/algorithm_impl.h
(__internal::__brick_equal): use "4 iterator" version of
std::equal().
(__internal::__brick_equal): use simd for random access
iterators on unsequenced execution policies.
(__internal::__pattern_equal): add "4 iterator" version
(__internal::__pattern_equal): dispatch to simd __brick_equal
for vector-only execution policies.
(__internal::__pattern_equal): disptach to __parallel_or for
parallel execution policies.
* include/pstl/glue_algorithm_impl.h
(std::equal): dispatch to "4 iterator" version of
__internal::__pattern_equal().
>From 7a927774dfac3fef6d736cf29671c7d7df38aaed Mon Sep 17 00:00:00 2001
From: Thomas Rodgers <trodgers@redhat.com>
Date: Tue, 16 Apr 2019 12:26:52 -0700
Subject: [PATCH] Improve implementation of parallel equal()
* include/pstl/algorithm_impl.h
(__internal::__brick_equal): use "4 iterator" version of
std::equal().
(__internal::__brick_equal): use simd for random access
iterators on unsequenced execution policies.
(__internal::__pattern_equal): add "4 iterator" version
(__internal::__pattern_equal): dispatch to simd __brick_equal
for vector-only execution policies.
(__internal::__pattern_equal): disptach to __parallel_or for
parallel execution policies.
* include/pstl/glue_algorithm_impl.h
(std::equal): dispatch to "4 iterator" version of
__internal::__pattern_equal().
---
libstdc++-v3/include/pstl/algorithm_impl.h | 57 +++++++++++++++++++
.../include/pstl/glue_algorithm_impl.h | 2 +-
2 files changed, 58 insertions(+), 1 deletion(-)
diff --git a/libstdc++-v3/include/pstl/algorithm_impl.h b/libstdc++-v3/include/pstl/algorithm_impl.h
index d39e99add05..511e688c3f6 100644
--- a/libstdc++-v3/include/pstl/algorithm_impl.h
+++ b/libstdc++-v3/include/pstl/algorithm_impl.h
@@ -404,6 +404,63 @@ __pattern_walk3(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _Ran
// 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,
diff --git a/libstdc++-v3/include/pstl/glue_algorithm_impl.h b/libstdc++-v3/include/pstl/glue_algorithm_impl.h
index 88ce93fca41..db5ef2b76f5 100644
--- a/libstdc++-v3/include/pstl/glue_algorithm_impl.h
+++ b/libstdc++-v3/include/pstl/glue_algorithm_impl.h
@@ -757,7 +757,7 @@ __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,
+ return equal(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2,
__pstl::__internal::__pstl_equal());
}
--
2.20.1