From a34d6343a758f651064d81abb1534971fa4170e7 Mon Sep 17 00:00:00 2001 From: Thomas Rodgers Date: Fri, 19 Apr 2019 22:44:11 +0000 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): dispatch 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-SVN: r270463 --- libstdc++-v3/ChangeLog | 17 ++++++ libstdc++-v3/include/pstl/algorithm_impl.h | 57 +++++++++++++++++++ .../include/pstl/glue_algorithm_impl.h | 2 +- 3 files changed, 75 insertions(+), 1 deletion(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index fb35a14e1a9..ce726599d0e 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,20 @@ +2019-04-19 Thomas Rodgers + + 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): dispatch to __parallel_or for + parallel execution policies. + * include/pstl/glue_algorithm_impl.h + (std::equal): dispatch to "4 iterator" version of + __internal::__pattern_equal(). + 2019-04-17 Jonathan Wakely PR libstdc++/90105 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 +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 +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 +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 +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 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.30.2