re PR libstdc++/42712 (search_n/iterator.cc times out in parallel-mode)

2010-01-19  Johannes Singler  <singler@kit.edu>

        PR libstdc++/42712
        * include/parallel/settings.h (_Settings): Add search_minimal_n.
        * include/parallel/algo.h (__search_switch):
        Add serial fallback for too small inputs.
        (__search_n_switch): Likewise.  Call serial fallback on higher level
        to gain special treatment for __count 0 or 1.
        * testsuite/25_algorithms/search_n/iterator.cc:
        Reenable full test depth for parallel mode.

From-SVN: r156036

4 files changed, 29 insertions, 13 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 934e65c..9830eb2 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,14 @@
+2010-01-19  Johannes Singler  <singler@kit.edu>
+
+	PR libstdc++/42712
+	* include/parallel/settings.h (_Settings): Add search_minimal_n.
+	* include/parallel/algo.h (__search_switch):
+	Add serial fallback for too small inputs.
+	(__search_n_switch): Likewise.  Call serial fallback on higher level
+	to gain special treatment for __count 0 or 1.
+	* testsuite/25_algorithms/search_n/iterator.cc:
+	Reenable full test depth for parallel mode.
+
 2010-01-18  Daniel Frey  <d.frey@gmx.de>
 
 	* include/std/functional (_Bind<_Functor(_Bound_args...)>::
diff --git a/libstdc++-v3/include/parallel/algo.h b/libstdc++-v3/include/parallel/algo.h
index 04953e81..43f0826 100644
--- a/libstdc++-v3/include/parallel/algo.h
+++ b/libstdc++-v3/include/parallel/algo.h
@@ -1043,7 +1043,9 @@ namespace __parallel
       typedef std::iterator_traits<_RAIter2> _Iterator2Traits;
       typedef typename _Iterator2Traits::value_type _ValueType2;
 
-      if (_GLIBCXX_PARALLEL_CONDITION(true))
+      if (_GLIBCXX_PARALLEL_CONDITION(
+                static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
+            >= __gnu_parallel::_Settings::get().search_minimal_n))
         return __gnu_parallel::
           __search_template(
             __begin1, __end1, __begin2, __end2,
@@ -1097,7 +1099,9 @@ namespace __parallel
                   _BinaryPredicate __pred,
                   random_access_iterator_tag, random_access_iterator_tag)
     {
-      if (_GLIBCXX_PARALLEL_CONDITION(true))
+      if (_GLIBCXX_PARALLEL_CONDITION(
+                static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
+            >= __gnu_parallel::_Settings::get().search_minimal_n))
         return __gnu_parallel::__search_template(__begin1, __end1,
                                                __begin2, __end2, __pred);
       else
@@ -1168,15 +1172,17 @@ namespace __parallel
                       const _Tp& __val, _BinaryPredicate __binary_pred,
                       random_access_iterator_tag)
     {
-      if (_GLIBCXX_PARALLEL_CONDITION(true))
+      if (_GLIBCXX_PARALLEL_CONDITION(
+                static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
+            >= __gnu_parallel::_Settings::get().search_minimal_n))
         {
           __gnu_parallel::_PseudoSequence<_Tp, _Integer> __ps(__val, __count);
           return __gnu_parallel::__search_template(
                    __begin, __end, __ps.begin(), __ps.end(), __binary_pred);
         }
       else
-        return std::__search_n(__begin, __end, __count, __val,
-                               __binary_pred, random_access_iterator_tag());
+        return _GLIBCXX_STD_P::search_n(__begin, __end, __count, __val,
+                                        __binary_pred);
     }
 
   // Sequential fallback for input iterator case.
@@ -1186,8 +1192,8 @@ namespace __parallel
     __search_n_switch(_FIterator __begin, _FIterator __end, _Integer __count,
                       const _Tp& __val, _BinaryPredicate __binary_pred,
                       _IteratorTag)
-    { return __search_n(__begin, __end, __count, __val, __binary_pred,
-                        _IteratorTag()); }
+    { return _GLIBCXX_STD_P::search_n(__begin, __end, __count, __val,
+                                      __binary_pred); }
 
   // Public interface.
   template<typename _FIterator, typename _Integer, typename _Tp,
diff --git a/libstdc++-v3/include/parallel/settings.h b/libstdc++-v3/include/parallel/settings.h
index e83ecc5..3b326ff 100644
--- a/libstdc++-v3/include/parallel/settings.h
+++ b/libstdc++-v3/include/parallel/settings.h
@@ -269,6 +269,9 @@ namespace __gnu_parallel
     /// The number of stolen ranges in load-balanced quicksort.
     _SequenceIndex              qsb_steals;
 
+    /// Minimal input size for search and search_n.
+    _SequenceIndex              search_minimal_n;
+
     /// Get the global settings.
     _GLIBCXX_CONST static const _Settings&
     get() throw();
@@ -327,7 +330,8 @@ namespace __gnu_parallel
             L2_cache_size(256 << 10),
             TLB_size(128),
             cache_line_size(64),
-            qsb_steals(0)
+            qsb_steals(0),
+            search_minimal_n(1000)
     { }
   };
 }
diff --git a/libstdc++-v3/testsuite/25_algorithms/search_n/iterator.cc b/libstdc++-v3/testsuite/25_algorithms/search_n/iterator.cc
index 4a506b5..d7be297 100644
--- a/libstdc++-v3/testsuite/25_algorithms/search_n/iterator.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/search_n/iterator.cc
@@ -25,11 +25,6 @@
 #include <testsuite_hooks.h>
 #include <testsuite_iterators.h>
 
-// XXX FIXME: why parallel-mode is so slow?
-#if !defined(TEST_DEPTH) && defined(_GLIBCXX_PARALLEL)
-#define TEST_DEPTH 10
-#endif
-
 #ifndef TEST_DEPTH
 #define TEST_DEPTH 14
 #endif