* 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 <trodg...@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