[PPL-devel] [GIT] ppl/ppl(sparse_matrices): CO_Tree: optimize further lower_bound() for the DFS layout.

[Marco Poletti]

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

Author: Marco Poletti <poletti.marco at gmail.com>
Date:   Sun May  9 12:42:47 2010 +0200

CO_Tree: optimize further lower_bound() for the DFS layout.

---

 src/CO_Tree.inlines.hh |   88 ++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 86 insertions(+), 2 deletions(-)

diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh
index f91f8ac..391894e 100644
--- a/src/CO_Tree.inlines.hh
+++ b/src/CO_Tree.inlines.hh
@@ -366,7 +366,49 @@ CO_Tree::lower_bound(inorder_iterator& itr, dimension_type key) {
     return;
 
   dimension_type low_index = itr.i;
-  dimension_type high_index = reserved_size;
+  dimension_type high_index;
+
+  // Logarithmic search of an interval in which the key will be searched.
+  // Near (and small) intervals are tried first, to exploit the caches.
+  {
+    dimension_type hop = 1;
+    dimension_type last_low_index = low_index;
+
+    while (1) {
+
+      if (low_index > reserved_size)
+        low_index = reserved_size + 1;
+      else
+        while (indexes[low_index] == unused_index)
+          ++low_index;
+
+      PPL_ASSERT(indexes[low_index] != unused_index);
+
+      if (low_index > reserved_size) {
+        PPL_ASSERT(low_index <= reserved_size + 1);
+        high_index = low_index - 1;
+        low_index = last_low_index;
+        break;
+      }
+
+      if (indexes[low_index] == key) {
+        itr.i = low_index;
+        return;
+      }
+
+      if (indexes[low_index] > key) {
+        high_index = low_index - 1;
+        low_index = last_low_index;
+        break;
+      }
+
+      PPL_ASSERT(indexes[low_index] < key);
+
+      last_low_index = low_index;
+      low_index += hop;
+      hop *= 2;
+    }
+  }
 
   PPL_ASSERT(low_index > 0);
 
@@ -461,7 +503,49 @@ CO_Tree::lower_bound(inorder_const_iterator& itr, dimension_type key) const {
     return;
 
   dimension_type low_index = itr.i;
-  dimension_type high_index = reserved_size;
+  dimension_type high_index;
+
+  // Logarithmic search of an interval in which the key will be searched.
+  // Near (and small) intervals are tried first, to exploit the caches.
+  {
+    dimension_type hop = 1;
+    dimension_type last_low_index = low_index;
+
+    while (1) {
+
+      if (low_index > reserved_size)
+        low_index = reserved_size + 1;
+      else
+        while (indexes[low_index] == unused_index)
+          ++low_index;
+
+      PPL_ASSERT(indexes[low_index] != unused_index);
+
+      if (low_index > reserved_size) {
+        PPL_ASSERT(low_index <= reserved_size + 1);
+        high_index = low_index - 1;
+        low_index = last_low_index;
+        break;
+      }
+
+      if (indexes[low_index] == key) {
+        itr.i = low_index;
+        return;
+      }
+
+      if (indexes[low_index] > key) {
+        high_index = low_index - 1;
+        low_index = last_low_index;
+        break;
+      }
+
+      PPL_ASSERT(indexes[low_index] < key);
+
+      last_low_index = low_index;
+      low_index += hop;
+      hop *= 2;
+    }
+  }
 
   PPL_ASSERT(low_index > 0);