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

Author: Marco Poletti poletti.marco@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);