This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
N3671 std::mismatch and std::equals parallel versions
- From: François Dumont <frs dot dumont at gmail dot com>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>
- Date: Mon, 30 Sep 2013 22:09:38 +0200
- Subject: N3671 std::mismatch and std::equals parallel versions
- Authentication-results: sourceware.org; auth=none
Hi
Here is a patch to provide real parallel version of N3671 overloads
of std::mismatch and std::equals. It is similar to what has been done
for previous overloads.
Tested under Linux x86_64 parallel mode.
2013-09-30 François Dumont <fdumont@gcc.gnu.org>
* include/parallel/algobase.h (mismatch, equals): Provide parallel
version for N3671 overloads.
Ok to commit ?
François
Index: include/parallel/algobase.h
===================================================================
--- include/parallel/algobase.h (revision 203039)
+++ include/parallel/algobase.h (working copy)
@@ -94,17 +94,13 @@
inline pair<_IIter1, _IIter2>
mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
{
- typedef std::iterator_traits<_IIter1> _Iterator1Traits;
- typedef std::iterator_traits<_IIter2> _Iterator2Traits;
- typedef typename _Iterator1Traits::value_type _ValueType1;
- typedef typename _Iterator2Traits::value_type _ValueType2;
- typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
- typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
+ typedef __gnu_parallel::_EqualTo<
+ typename std::iterator_traits<_IIter1>::value_type,
+ typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
- typedef __gnu_parallel::_EqualTo<_ValueType1, _ValueType2> _EqualTo;
-
return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(),
- _IteratorCategory1(), _IteratorCategory2());
+ std::__iterator_category(__begin1),
+ std::__iterator_category(__begin2));
}
// Public interface
@@ -113,32 +109,93 @@
mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
_Predicate __pred)
{
- typedef std::iterator_traits<_IIter1> _Iterator1Traits;
- typedef std::iterator_traits<_IIter2> _Iterator2Traits;
- typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
- typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
-
return __mismatch_switch(__begin1, __end1, __begin2, __pred,
- _IteratorCategory1(), _IteratorCategory2());
+ std::__iterator_category(__begin1),
+ std::__iterator_category(__begin2));
}
#if __cplusplus > 201103L
+ // Sequential fallback.
template<typename _InputIterator1, typename _InputIterator2>
inline pair<_InputIterator1, _InputIterator2>
mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
- _InputIterator2 __first2, _InputIterator2 __last2)
+ _InputIterator2 __first2, _InputIterator2 __last2,
+ __gnu_parallel::sequential_tag)
{ return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2); }
+ // Sequential fallback.
template<typename _InputIterator1, typename _InputIterator2,
typename _BinaryPredicate>
inline pair<_InputIterator1, _InputIterator2>
mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
- _BinaryPredicate __binary_pred)
+ _BinaryPredicate __binary_pred,
+ __gnu_parallel::sequential_tag)
{
return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2,
__binary_pred);
}
+
+ // Sequential fallback for input iterator case
+ template<typename _IIter1, typename _IIter2,
+ typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
+ inline pair<_IIter1, _IIter2>
+ __mismatch_switch(_IIter1 __begin1, _IIter1 __end1,
+ _IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
+ _IteratorTag1, _IteratorTag2)
+ {
+ return _GLIBCXX_STD_A::mismatch(__begin1, __end1,
+ __begin2, __end2, __pred);
+ }
+
+ // Parallel mismatch for random access iterators
+ template<typename _RAIter1, typename _RAIter2, typename _Predicate>
+ pair<_RAIter1, _RAIter2>
+ __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1,
+ _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred,
+ random_access_iterator_tag, random_access_iterator_tag)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION(true))
+ {
+ if ((__end2 - __begin2) < (__end1 - __begin1))
+ __end1 = __begin1 + (__end2 - __begin2);
+
+ _RAIter1 __res =
+ __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
+ __gnu_parallel::
+ __mismatch_selector()).first;
+ return make_pair(__res , __begin2 + (__res - __begin1));
+ }
+ else
+ return _GLIBCXX_STD_A::mismatch(__begin1, __end1,
+ __begin2, __end2, __pred);
+ }
+
+ template<typename _IIter1, typename _IIter2>
+ inline pair<_IIter1, _IIter2>
+ mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
+ {
+ typedef __gnu_parallel::_EqualTo<
+ typename std::iterator_traits<_IIter1>::value_type,
+ typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
+
+ return __mismatch_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
+ std::__iterator_category(__begin1),
+ std::__iterator_category(__begin2));
+ }
+
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _BinaryPredicate>
+ inline pair<_InputIterator1, _InputIterator2>
+ mismatch(_InputIterator1 __begin1, _InputIterator1 __end1,
+ _InputIterator2 __begin2, _InputIterator2 __end2,
+ _BinaryPredicate __binary_pred)
+ {
+ return __mismatch_switch(__begin1, __end1, __begin2, __end2,
+ __binary_pred,
+ std::__iterator_category(__begin1),
+ std::__iterator_category(__begin2));
+ }
#endif
// Sequential fallback
@@ -175,19 +232,81 @@
}
#if __cplusplus > 201103L
- template<typename _II1, typename _II2>
+ // Sequential fallback
+ template<typename _IIter1, typename _IIter2>
inline bool
- equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
- { return _GLIBCXX_STD_A::equal(__first1, __last1, __first2, __last2); }
+ equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
+ __gnu_parallel::sequential_tag)
+ {
+ return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
+ }
+ // Sequential fallback
template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
inline bool
- equal(_IIter1 __first1, _IIter1 __last1,
- _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
+ equal(_IIter1 __begin1, _IIter1 __end1,
+ _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred,
+ __gnu_parallel::sequential_tag)
{
- return _GLIBCXX_STD_A::equal(__first1, __last1, __first2, __last2,
+ return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
__binary_pred);
}
+
+ // Sequential fallback for input iterator case
+ template<typename _IIter1, typename _IIter2,
+ typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
+ inline bool
+ __equal_switch(_IIter1 __begin1, _IIter1 __end1,
+ _IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
+ _IteratorTag1, _IteratorTag2)
+ {
+ return _GLIBCXX_STD_A::equal(__begin1, __end1,
+ __begin2, __end2, __pred);
+ }
+
+ // Parallel mismatch for random access iterators
+ template<typename _RAIter1, typename _RAIter2, typename _Predicate>
+ inline bool
+ __equal_switch(_RAIter1 __begin1, _RAIter1 __end1,
+ _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred,
+ random_access_iterator_tag, random_access_iterator_tag)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION(true))
+ {
+ if (std::distance(__begin1, __end1)
+ != std::distance(__begin2, __end2))
+ return false;
+
+ return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __end2,
+ __pred).first == __end1;
+ }
+ else
+ return _GLIBCXX_STD_A::equal(__begin1, __end1,
+ __begin2, __end2, __pred);
+ }
+
+ template<typename _IIter1, typename _IIter2>
+ inline bool
+ equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
+ {
+ typedef __gnu_parallel::_EqualTo<
+ typename std::iterator_traits<_IIter1>::value_type,
+ typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
+
+ return __equal_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
+ std::__iterator_category(__begin1),
+ std::__iterator_category(__begin2));
+ }
+
+ template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
+ inline bool
+ equal(_IIter1 __begin1, _IIter1 __end1,
+ _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred)
+ {
+ return __equal_switch(__begin1, __end1, __begin2, __end2, __binary_pred,
+ std::__iterator_category(__begin1),
+ std::__iterator_category(__begin2));
+ }
#endif
// Sequential fallback