[PPL-devel] [GIT] ppl/ppl(sparse_matrices): Unlimited_Sparse_Row_Std_Vector_Backend: add and use sequential_search_treshold.

[Marco Poletti]

Module: ppl/ppl
Branch: sparse_matrices
Commit: f3957a85aeb8243fe82d015780a17d7601126865
URL:    http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f3957a85aeb8243fe82d015780a17d7601126865

Author: Marco Poletti <poletti.marco at gmail.com>
Date:   Wed Mar 24 16:24:38 2010 +0100

Unlimited_Sparse_Row_Std_Vector_Backend: add and use sequential_search_treshold.

---

 ...Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh |    5 +++++
 ...imited_Sparse_Row_Std_Vector_Backend.inlines.hh |   18 ++++++++++++++++++
 2 files changed, 23 insertions(+), 0 deletions(-)

diff --git a/src/Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh b/src/Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh
index a479672..370feba 100644
--- a/src/Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh
+++ b/src/Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh
@@ -57,6 +57,11 @@ private:
   Unlimited_Sparse_Row_Std_Vector_Backend::key_value_comparison<Compare>
   key_value_compare(const Compare& comp);
 
+  //! This is the number of sequential comparisons after which binary search
+  //! is performed. This affects performance, but not correctness.
+  //! Some methods do one more comparison.
+  static const dimension_type sequential_search_treshold = 3;
+
 public:
   //! Needed to satisfy the backend requirements.
   //! This is not a typedef to allow overloading of methods with both types.
diff --git a/src/Unlimited_Sparse_Row_Std_Vector_Backend.inlines.hh b/src/Unlimited_Sparse_Row_Std_Vector_Backend.inlines.hh
index c7c8776..02f3696 100644
--- a/src/Unlimited_Sparse_Row_Std_Vector_Backend.inlines.hh
+++ b/src/Unlimited_Sparse_Row_Std_Vector_Backend.inlines.hh
@@ -143,6 +143,12 @@ inline Unlimited_Sparse_Row_Std_Vector_Backend::dangerous_iterator
 Unlimited_Sparse_Row_Std_Vector_Backend
 ::lower_bound_dangerous(const dimension_type k, dangerous_iterator itr) {
   PPL_ASSERT(itr == end_dangerous() || (*itr).first <= k);
+  for (dimension_type i = sequential_search_treshold; i-- > 0; ) {
+    if (itr == end_dangerous() || (*itr).first >= k)
+      return itr;
+    ++itr;
+  }
+  // Now perform binary search.
   return std::lower_bound(itr, end_dangerous(), k,
                           value_key_compare(std::less<dimension_type>()));
 }
@@ -162,6 +168,12 @@ inline Unlimited_Sparse_Row_Std_Vector_Backend::iterator
 Unlimited_Sparse_Row_Std_Vector_Backend
 ::lower_bound(const dimension_type k, iterator itr) {
   PPL_ASSERT(itr == end() || (*itr).first <= k);
+  for (dimension_type i = sequential_search_treshold; i-- > 0; ) {
+    if (itr == end() || (*itr).first >= k)
+      return itr;
+    ++itr;
+  }
+  // Now perform binary search.
   return std::lower_bound(itr, end(), k,
                           value_key_compare(std::less<dimension_type>()));
 }
@@ -181,6 +193,12 @@ inline Unlimited_Sparse_Row_Std_Vector_Backend::const_iterator
 Unlimited_Sparse_Row_Std_Vector_Backend
 ::lower_bound(const dimension_type k, const_iterator itr1) const {
   PPL_ASSERT(itr1 == end() || (*itr1).first <= k);
+  for (dimension_type i = sequential_search_treshold; i-- > 0; ) {
+    if (itr1 == end() || (*itr1).first >= k)
+      return itr1;
+    ++itr1;
+  }
+  // Now perform binary search.
   return std::lower_bound(itr1, end(), k,
                           value_key_compare(std::less<dimension_type>()));
 }