- PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(sparse_matrices): CO_Tree: optimize further lower_bound() for the DFS layout.
by Marco Poletti 09 May '10

09 May '10

Module: ppl/ppl Branch: sparse_matrices Commit: 4f4c3d79d1458b66d21c2cf5041c1ad7cc28ffd9 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4f4c3d79d145… Author: Marco Poletti <poletti.marco(a)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);

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: optimize go_down_searching_key() for the DFS layout.
by Marco Poletti 09 May '10

09 May '10

Module: ppl/ppl Branch: sparse_matrices Commit: 633bb9f9ad12fb4995c3dee47e111bfd09c02b4f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=633bb9f9ad12… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat May 8 18:35:00 2010 +0200 CO_Tree: optimize go_down_searching_key() for the DFS layout. --- src/CO_Tree.defs.hh | 6 +-- src/CO_Tree.inlines.hh | 132 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 134 insertions(+), 4 deletions(-) diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index 21fcd1e..c185103 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -583,8 +583,7 @@ private: //! The tree the iterator points to. const CO_Tree* tree; - friend dimension_type - CO_Tree::count_used_in_subtree(inorder_const_iterator& itr); + friend class CO_Tree; }; class CO_Tree::inorder_iterator { @@ -743,8 +742,7 @@ private: friend inorder_const_iterator& inorder_const_iterator::operator=(const inorder_iterator&); - friend dimension_type - CO_Tree::count_used_in_subtree(inorder_iterator& itr); + friend class CO_Tree; }; } // namespace Parma_Polyhedra_Library diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh index 8797d65..f91f8ac 100644 --- a/src/CO_Tree.inlines.hh +++ b/src/CO_Tree.inlines.hh @@ -353,7 +353,71 @@ CO_Tree::go_down_searching_key(inorder_const_iterator& itr, inline void CO_Tree::lower_bound(inorder_iterator& itr, dimension_type key) { +#ifdef USE_PPL_CO_TREE_DFS_LAYOUT + PPL_ASSERT(!empty()); + PPL_ASSERT(itr.is_at_end() || itr->first <= key); + + if (itr.is_before_begin()) + ++itr; + + PPL_ASSERT(itr.is_at_end() || itr->first <= key); + + if (itr.is_at_end()) + return; + + dimension_type low_index = itr.i; + dimension_type high_index = reserved_size; + + PPL_ASSERT(low_index > 0); + + while (low_index + 1 < high_index) { + + dimension_type avg = (low_index + high_index) / 2; + dimension_type index = avg; + + while (indexes[index] == unused_index) + ++index; + + if (index > high_index || indexes[index] > key) { + high_index = avg; + } else { + low_index = index; + } + } + + if (low_index == high_index) { + if (indexes[low_index] == unused_index || indexes[low_index] < key) + ++low_index; + while (indexes[low_index] == unused_index) + ++low_index; + + } else { + PPL_ASSERT(low_index + 1 == high_index); + if (indexes[low_index] == unused_index || indexes[low_index] < key) { + ++low_index; + if (indexes[low_index] == unused_index || indexes[low_index] < key) + ++low_index; + } + while (indexes[low_index] == unused_index) + ++low_index; + } + + itr.i = low_index; + +#ifndef NDEBUG + inorder_iterator itr2 = itr; + itr2.get_previous_value(); + PPL_ASSERT(itr2.is_before_begin() || itr2->first < key); + itr2.get_next_value(); + PPL_ASSERT(itr2 == itr); +#endif + + PPL_ASSERT(itr.is_at_end() || itr->first >= key); + +#else // defined(USE_PPL_CO_TREE_DFS_LAYOUT) + PPL_ASSERT(!empty()); + PPL_ASSERT(itr.is_at_end() || itr->first <= key); if (itr->first <= key) while (itr.has_parent() && itr->first < key) itr.get_parent(); @@ -378,11 +442,77 @@ CO_Tree::lower_bound(inorder_iterator& itr, dimension_type key) { itr.get_next_value(); #endif PPL_ASSERT(itr.is_at_end() || itr->first >= key); + +#endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT) } inline void CO_Tree::lower_bound(inorder_const_iterator& itr, dimension_type key) const { +#ifdef USE_PPL_CO_TREE_DFS_LAYOUT + PPL_ASSERT(!empty()); + PPL_ASSERT(itr.is_at_end() || itr->first <= key); + + if (itr.is_before_begin()) + ++itr; + + PPL_ASSERT(itr.is_at_end() || itr->first <= key); + + if (itr.is_at_end()) + return; + + dimension_type low_index = itr.i; + dimension_type high_index = reserved_size; + + PPL_ASSERT(low_index > 0); + + while (low_index + 1 < high_index) { + + dimension_type avg = (low_index + high_index) / 2; + dimension_type index = avg; + + while (indexes[index] == unused_index) + ++index; + + if (index > high_index || indexes[index] > key) { + high_index = avg; + } else { + low_index = index; + } + } + + if (low_index == high_index) { + if (indexes[low_index] == unused_index || indexes[low_index] < key) + ++low_index; + while (indexes[low_index] == unused_index) + ++low_index; + + } else { + PPL_ASSERT(low_index + 1 == high_index); + if (indexes[low_index] == unused_index || indexes[low_index] < key) { + ++low_index; + if (indexes[low_index] == unused_index || indexes[low_index] < key) + ++low_index; + } + while (indexes[low_index] == unused_index) + ++low_index; + } + + itr.i = low_index; + +#ifndef NDEBUG + inorder_const_iterator itr2 = itr; + itr2.get_previous_value(); + PPL_ASSERT(itr2.is_before_begin() || itr2->first < key); + itr2.get_next_value(); + PPL_ASSERT(itr2 == itr); +#endif + + PPL_ASSERT(itr.is_at_end() || itr->first >= key); + +#else // defined(USE_PPL_CO_TREE_DFS_LAYOUT) + PPL_ASSERT(!empty()); + PPL_ASSERT(itr.is_at_end() || itr->first <= key); if (itr->first <= key) while (itr.has_parent() && itr->first < key) itr.get_parent(); @@ -407,6 +537,8 @@ CO_Tree::lower_bound(inorder_const_iterator& itr, dimension_type key) const { itr.get_next_value(); #endif PPL_ASSERT(itr.is_at_end() || itr->first >= key); + +#endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT) } inline void

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: add lower_bound() methods.
by Marco Poletti 09 May '10

09 May '10

Module: ppl/ppl Branch: sparse_matrices Commit: ab2585fce082a05a988ba8b6a4e8e72325a07cf6 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ab2585fce082… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat May 8 17:57:36 2010 +0200 CO_Tree: add lower_bound() methods. --- src/CO_Tree.defs.hh | 10 ++++ src/CO_Tree.inlines.hh | 58 ++++++++++++++++++++++ src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh | 52 +------------------- 3 files changed, 70 insertions(+), 50 deletions(-) diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index d569673..21fcd1e 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -164,6 +164,16 @@ public: void go_down_searching_key(inorder_const_iterator& itr, dimension_type key) const; + //! Searches for an element with key \p key , assuming \p itr->first is less + //! than or equal to \p key . + //! If there is no element with key \p key , itr will be set to end(). + void lower_bound(inorder_iterator& itr, dimension_type key); + + //! Searches for an element with key \p key , assuming \p itr->first is less + //! than or equal to \p key . + //! If there is no element with key \p key , itr will be set to end(). + void lower_bound(inorder_const_iterator& itr, dimension_type key) const; + class inorder_iterator; class inorder_const_iterator; diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh index a3b3347..8797d65 100644 --- a/src/CO_Tree.inlines.hh +++ b/src/CO_Tree.inlines.hh @@ -352,6 +352,64 @@ CO_Tree::go_down_searching_key(inorder_const_iterator& itr, } inline void +CO_Tree::lower_bound(inorder_iterator& itr, dimension_type key) { + PPL_ASSERT(!empty()); + if (itr->first <= key) + while (itr.has_parent() && itr->first < key) + itr.get_parent(); + else + while (itr.has_parent() && itr->first > key) + itr.get_parent(); + + go_down_searching_key(itr, key); + +#ifndef NDEBUG + CO_Tree::inorder_iterator itr2(this); + go_down_searching_key(itr2, key); + PPL_ASSERT(itr == itr2); +#endif + + if (itr->first < key) + itr.get_next_value(); + +#ifndef NDEBUG + itr.get_previous_value(); + PPL_ASSERT(itr.is_before_begin() || itr->first < key); + itr.get_next_value(); +#endif + PPL_ASSERT(itr.is_at_end() || itr->first >= key); +} + +inline void +CO_Tree::lower_bound(inorder_const_iterator& itr, dimension_type key) const { + PPL_ASSERT(!empty()); + if (itr->first <= key) + while (itr.has_parent() && itr->first < key) + itr.get_parent(); + else + while (itr.has_parent() && itr->first > key) + itr.get_parent(); + + go_down_searching_key(itr, key); + +#ifndef NDEBUG + CO_Tree::inorder_const_iterator itr2(this); + go_down_searching_key(itr2, key); + PPL_ASSERT(itr == itr2); +#endif + + if (itr->first < key) + itr.get_next_value(); + +#ifndef NDEBUG + itr.get_previous_value(); + PPL_ASSERT(itr.is_before_begin() || itr->first < key); + itr.get_next_value(); +#endif + PPL_ASSERT(itr.is_at_end() || itr->first >= key); +} + +inline void CO_Tree::move_data_element(data_type& to, data_type& from) { // The following code is equivalent (but slower): // diff --git a/src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh b/src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh index 954e0a6..76d6bdb 100644 --- a/src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh +++ b/src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh @@ -500,62 +500,14 @@ inline void Unlimited_Sparse_Row_Over_CO_Tree ::lower_bound_hint_assign(dimension_type i, CO_Tree::inorder_iterator& itr) { - PPL_ASSERT(!tree.empty()); - if (itr->first <= i) - while (itr.has_parent() && itr->first < i) - itr.get_parent(); - else - while (itr.has_parent() && itr->first > i) - itr.get_parent(); - - tree.go_down_searching_key(itr, i); - -#ifndef NDEBUG - CO_Tree::inorder_iterator itr2(&tree); - tree.go_down_searching_key(itr2, i); - PPL_ASSERT(itr == itr2); -#endif - - if (itr->first < i) - itr.get_next_value(); - -#ifndef NDEBUG - itr.get_previous_value(); - PPL_ASSERT(itr.is_before_begin() || itr->first < i); - itr.get_next_value(); -#endif - PPL_ASSERT(itr.is_at_end() || itr->first >= i); + tree.lower_bound(itr, i); } inline void Unlimited_Sparse_Row_Over_CO_Tree ::lower_bound_hint_assign(dimension_type i, CO_Tree::inorder_const_iterator& itr) const { - PPL_ASSERT(!tree.empty()); - if (itr->first <= i) - while (itr.has_parent() && itr->first < i) - itr.get_parent(); - else - while (itr.has_parent() && itr->first > i) - itr.get_parent(); - - tree.go_down_searching_key(itr, i); - -#ifndef NDEBUG - CO_Tree::inorder_const_iterator itr2(&tree); - tree.go_down_searching_key(itr2, i); - PPL_ASSERT(itr == itr2); -#endif - - if (itr->first < i) - itr.get_next_value(); - -#ifndef NDEBUG - itr.get_previous_value(); - PPL_ASSERT(itr.is_before_begin() || itr->first < i); - itr.get_next_value(); -#endif - PPL_ASSERT(itr.is_at_end() || itr->first >= i); + tree.lower_bound(itr, i); } inline void

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: rename method lower_bound() in go_down_searching_key().
by Marco Poletti 09 May '10

09 May '10

Module: ppl/ppl Branch: sparse_matrices Commit: 891133373e7b91cf0e05b52fb3d8eb673580f27e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=891133373e7b… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat May 8 17:42:15 2010 +0200 CO_Tree: rename method lower_bound() in go_down_searching_key(). --- src/CO_Tree.cc | 8 +- src/CO_Tree.defs.hh | 5 +- src/CO_Tree.inlines.hh | 17 +++--- src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh | 68 +++++++++++----------- 4 files changed, 50 insertions(+), 48 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=89113337…

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: use dimension_type as height_t, because it improves performance.
by Marco Poletti 09 May '10

09 May '10

Module: ppl/ppl Branch: sparse_matrices Commit: 8748f091ff467bb0af823bc8f3526dc3d8f47fc0 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8748f091ff46… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri May 7 22:16:35 2010 +0200 CO_Tree: use dimension_type as height_t, because it improves performance. --- src/CO_Tree.defs.hh | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index 0960519..c39fec9 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -54,7 +54,7 @@ namespace Parma_Polyhedra_Library { class CO_Tree { private: - typedef uint_fast8_t height_t; + typedef dimension_type height_t; public:

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: use height_t instead of dimension_type for node heights and depths.
by Marco Poletti 07 May '10

07 May '10

Module: ppl/ppl Branch: sparse_matrices Commit: 6d75380ef8478339ba0145cae153f096f8111ff0 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6d75380ef847… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri May 7 17:32:36 2010 +0200 CO_Tree: use height_t instead of dimension_type for node heights and depths. --- src/CO_Tree.cc | 18 +++++++++--------- src/CO_Tree.defs.hh | 20 ++++++++++---------- src/CO_Tree.inlines.hh | 14 +++++++------- 3 files changed, 26 insertions(+), 26 deletions(-) diff --git a/src/CO_Tree.cc b/src/CO_Tree.cc index afc2807..d33e9a1 100644 --- a/src/CO_Tree.cc +++ b/src/CO_Tree.cc @@ -165,7 +165,7 @@ PPL::CO_Tree::init(dimension_type reserved_size1) { return; } - dimension_type l = 0; + height_t l = 0; if (reserved_size1 == 0) reserved_size1 = 1; @@ -504,8 +504,8 @@ PPL::CO_Tree::rebalance(inorder_iterator& itr, dimension_type key, PPL_ASSERT(!itr.get_right_child_value()); } #endif - dimension_type itr_depth_minus_1 = itr.depth() - 1; - dimension_type height = max_depth - itr_depth_minus_1; + height_t itr_depth_minus_1 = itr.depth() - 1; + height_t height = max_depth - itr_depth_minus_1; dimension_type subtree_size; const bool deleting = itr->first == unused_index; PPL_ASSERT(deleting || key != unused_index); @@ -641,7 +641,7 @@ PPL::CO_Tree::count_used_in_subtree(inorder_iterator& itr) { dimension_type n = 0; #ifdef USE_PPL_CO_TREE_VEB_LAYOUT - const dimension_type depth = itr.depth(); + const height_t depth = itr.depth(); #ifndef NDEBUG const dimension_type root_index = itr->first; @@ -711,7 +711,7 @@ PPL::CO_Tree::count_used_in_subtree(inorder_const_iterator& itr) { dimension_type n = 0; #ifdef USE_PPL_CO_TREE_VEB_LAYOUT - const dimension_type depth = itr.depth(); + const height_t depth = itr.depth(); #ifndef NDEBUG const dimension_type root_index = itr->first; @@ -833,7 +833,7 @@ PPL::CO_Tree #endif #ifdef USE_PPL_CO_TREE_VEB_LAYOUT - const dimension_type depth = root.depth(); + const height_t depth = root.depth(); #endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT) while (root.get_right_child_value()) @@ -995,7 +995,7 @@ PPL::CO_Tree #ifdef USE_PPL_CO_TREE_VEB_LAYOUT const PPL::CO_Tree::level_data* -PPL::CO_Tree::Level_Data_Cache::get_level_data(dimension_type height) { +PPL::CO_Tree::Level_Data_Cache::get_level_data(height_t height) { PPL_ASSERT(height >= 2); if (cache[height] == NULL) { cache[height] = new level_data[height]; @@ -1007,12 +1007,12 @@ PPL::CO_Tree::Level_Data_Cache::get_level_data(dimension_type height) { void PPL::CO_Tree::Level_Data_Cache ::fill_level_data(level_data* p, - dimension_type min_depth, dimension_type max_depth) { + height_t min_depth, height_t max_depth) { PPL_ASSERT(p != NULL); if (min_depth == max_depth) return; - dimension_type d0 = (min_depth + max_depth) / 2; + height_t d0 = (min_depth + max_depth) / 2; p[d0].depth_of_root_of_top_tree = min_depth; p[d0].bottom_tree_size = ((dimension_type)1 << (max_depth - d0)) - 1; diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index ebbba0f..0960519 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -266,7 +266,7 @@ private: struct level_data { dimension_type bottom_tree_size; dimension_type top_tree_size; - dimension_type depth_of_root_of_top_tree; + height_t depth_of_root_of_top_tree; }; #ifdef USE_PPL_CO_TREE_VEB_LAYOUT @@ -274,14 +274,14 @@ private: public: - static const level_data* get_level_data(dimension_type height); + static const level_data* get_level_data(height_t height); private: - static const dimension_type max_depth = sizeof(dimension_type)*CHAR_BIT; + static const height_t max_depth = sizeof(dimension_type)*CHAR_BIT; - static void fill_level_data(level_data* p, dimension_type min_depth, - dimension_type max_depth); + static void fill_level_data(level_data* p, height_t min_depth, + height_t max_depth); //! cache[0] and cache[1] are not used. //! cache[i] contains NULL if get_level_data(i) has not been called yet, @@ -410,7 +410,7 @@ private: #endif // defined(USE_PPL_CO_TREE_VEB_LAYOUT) //! The depth of the leaves in the static tree. - dimension_type max_depth; + height_t max_depth; //! The vector that contains the keys in the tree. //! If a pair has \p unused_index as first element, it means it is not used. @@ -530,14 +530,14 @@ public: bool is_before_begin() const; //! Returns the depth of the current node. - dimension_type depth() const; + height_t depth() const; const CO_Tree* get_tree() const; private: #ifdef USE_PPL_CO_TREE_VEB_LAYOUT //! The depth of the current node in the vEB layout. - dimension_type d; + height_t d; //! Position of the node in a BFS layout. dimension_type i; @@ -685,7 +685,7 @@ public: bool is_before_begin() const; //! Returns the depth of the current node. - dimension_type depth() const; + height_t depth() const; CO_Tree* get_tree(); @@ -694,7 +694,7 @@ public: private: #ifdef USE_PPL_CO_TREE_VEB_LAYOUT //! The depth of the current node in the vEB layout. - dimension_type d; + height_t d; //! Position of the node in a BFS layout. dimension_type i; diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh index 8de94c1..b27aa3e 100644 --- a/src/CO_Tree.inlines.hh +++ b/src/CO_Tree.inlines.hh @@ -837,7 +837,7 @@ CO_Tree::inorder_iterator::is_before_begin() const { #endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT) } -inline dimension_type +inline CO_Tree::height_t CO_Tree::inorder_iterator::depth() const { PPL_ASSERT(tree != 0); @@ -847,7 +847,7 @@ CO_Tree::inorder_iterator::depth() const { #ifdef USE_PPL_CO_TREE_BFS_LAYOUT dimension_type n = i; - dimension_type d = 0; + height_t d = 0; while (n != 0) { n /= 2; ++d; @@ -857,7 +857,7 @@ CO_Tree::inorder_iterator::depth() const { #ifdef USE_PPL_CO_TREE_DFS_LAYOUT dimension_type n = i; - dimension_type d = 0; + height_t d = 0; while ((n & (dimension_type)0x01U) == 0) { n /= 2; ++d; @@ -1112,7 +1112,7 @@ CO_Tree::inorder_iterator::operator=(const inorder_iterator& itr2) { if (!is_at_end() && !is_before_begin()) { d = itr2.d; i = itr2.i; - for (dimension_type i = 1; i <= itr2.d; ++i) + for (height_t i = 1; i <= itr2.d; ++i) pos[i] = itr2.pos[i]; } #endif // defined(USE_PPL_CO_TREE_VEB_LAYOUT) @@ -1492,7 +1492,7 @@ CO_Tree::inorder_const_iterator::is_before_begin() const { #endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT) } -inline dimension_type +inline CO_Tree::height_t CO_Tree::inorder_const_iterator::depth() const { PPL_ASSERT(tree != 0); PPL_ASSERT(tree->reserved_size != 0); @@ -1503,7 +1503,7 @@ CO_Tree::inorder_const_iterator::depth() const { #ifdef USE_PPL_CO_TREE_BFS_LAYOUT dimension_type n = i; - dimension_type d = 0; + height_t d = 0; while (n != 0) { n /= 2; ++d; @@ -1513,7 +1513,7 @@ CO_Tree::inorder_const_iterator::depth() const { #ifdef USE_PPL_CO_TREE_DFS_LAYOUT dimension_type n = i; - dimension_type d = 0; + height_t d = 0; while ((n & (dimension_type)0x01U) == 0) { n /= 2; ++d;

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: add typedef for height_t.
by Marco Poletti 07 May '10

07 May '10

Module: ppl/ppl Branch: sparse_matrices Commit: dea68ec07cf126b9bb0b4637d8ffc686c81f8f4a URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=dea68ec07cf1… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri May 7 17:31:56 2010 +0200 CO_Tree: add typedef for height_t. --- src/CO_Tree.defs.hh | 4 ++++ 1 files changed, 4 insertions(+), 0 deletions(-) diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index 0c119af..ebbba0f 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -25,6 +25,7 @@ site: http://www.cs.unipr.it/ppl/ . */ #include "Coefficient.defs.hh" #include <vector> +#include <stdint.h> #ifndef USE_PPL_CO_TREE_VEB_LAYOUT #ifndef USE_PPL_CO_TREE_DFS_LAYOUT @@ -52,6 +53,9 @@ namespace Parma_Polyhedra_Library { class CO_Tree { +private: + typedef uint_fast8_t height_t; + public: typedef Coefficient data_type;

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: use CHAR_BITS instead of 8.
by Marco Poletti 07 May '10

07 May '10

Module: ppl/ppl Branch: sparse_matrices Commit: 68725960290e63120fd632ee87c106ad229e081b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=68725960290e… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri May 7 17:08:43 2010 +0200 CO_Tree: use CHAR_BITS instead of 8. --- src/CO_Tree.cc | 6 +++--- src/CO_Tree.defs.hh | 6 +++--- 2 files changed, 6 insertions(+), 6 deletions(-) diff --git a/src/CO_Tree.cc b/src/CO_Tree.cc index 292a7be..afc2807 100644 --- a/src/CO_Tree.cc +++ b/src/CO_Tree.cc @@ -50,7 +50,7 @@ PPL::CO_Tree::CO_Tree(const std::vector<data_type>& v) { } // This is static and with static allocation, to improve performance. - static std::pair<dimension_type,char> stack[5*8*sizeof(dimension_type)]; + static std::pair<dimension_type,char> stack[5*CHAR_BIT*sizeof(dimension_type)]; dimension_type stack_first_empty = 0; // A pair (n, operation) in the stack means: @@ -236,7 +236,7 @@ PPL::CO_Tree::move_data_from(CO_Tree& tree) { PPL_ASSERT(itr->first != unused_index); // This is static and with static allocation, to improve performance. - static std::pair<dimension_type,char> stack[5*8*sizeof(dimension_type)]; + static std::pair<dimension_type,char> stack[5*CHAR_BIT*sizeof(dimension_type)]; dimension_type stack_first_empty = 0; // A pair (n, operation) in the stack means: @@ -905,7 +905,7 @@ PPL::CO_Tree const data_type& value, bool added_key) { // This is static and with static allocation, to improve performance. - static std::pair<dimension_type,char> stack[5*8*sizeof(dimension_type)]; + static std::pair<dimension_type,char> stack[5*CHAR_BIT*sizeof(dimension_type)]; dimension_type stack_first_empty = 0; // A pair (n, operation) in the stack means: diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index 79c7421..0c119af 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -274,7 +274,7 @@ private: private: - static const dimension_type max_depth = sizeof(dimension_type)*8; + static const dimension_type max_depth = sizeof(dimension_type)*CHAR_BIT; static void fill_level_data(level_data* p, dimension_type min_depth, dimension_type max_depth); @@ -542,7 +542,7 @@ private: //! pos[0] is not used. //! pos[j], for j>0, is the position in the vEB layout of the node passed //! at depth j. - dimension_type pos[8*sizeof(dimension_type)]; + dimension_type pos[CHAR_BIT*sizeof(dimension_type)]; #endif // defined(USE_PPL_CO_TREE_VEB_LAYOUT) #ifdef USE_PPL_CO_TREE_BFS_LAYOUT @@ -699,7 +699,7 @@ private: //! pos[0] is not used. //! pos[j], for j>0, is the position in the vEB layout of the node passed //! at depth j. - dimension_type pos[8*sizeof(dimension_type)]; + dimension_type pos[CHAR_BIT*sizeof(dimension_type)]; #endif // defined(USE_PPL_CO_TREE_VEB_LAYOUT) #ifdef USE_PPL_CO_TREE_BFS_LAYOUT

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: use the first element of indexes[] as a marker, speeding up some iterator operations.
by Marco Poletti 07 May '10

07 May '10

Module: ppl/ppl Branch: sparse_matrices Commit: 91cd9a12cacdb355dacdebb1604532378b0672cb URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=91cd9a12cacd… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri May 7 17:00:04 2010 +0200 CO_Tree: use the first element of indexes[] as a marker, speeding up some iterator operations. --- src/CO_Tree.cc | 4 +++- src/CO_Tree.defs.hh | 5 ++--- src/CO_Tree.inlines.hh | 16 ++++++++++------ 3 files changed, 15 insertions(+), 10 deletions(-) diff --git a/src/CO_Tree.cc b/src/CO_Tree.cc index fc73bf9..292a7be 100644 --- a/src/CO_Tree.cc +++ b/src/CO_Tree.cc @@ -189,7 +189,8 @@ PPL::CO_Tree::init(dimension_type reserved_size1) { for (dimension_type i = 1; i <= reserved_size; ++i) new (&(indexes[i])) dimension_type(unused_index); - // This is used as a marker by unordered iterators. + // These are used as markers by iterators. + new (&(indexes[0])) dimension_type(0); new (&(indexes[reserved_size + 1])) dimension_type(0); max_depth = l; @@ -212,6 +213,7 @@ PPL::CO_Tree::destroy() { data[i].~data_type(); indexes[i].~dimension_type(); } + indexes[0].~dimension_type(); indexes[reserved_size + 1].~dimension_type(); // We use malloc()/free() instead of operator new()/operator delete() diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index b81e6a8..79c7421 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -408,11 +408,10 @@ private: //! The depth of the leaves in the static tree. dimension_type max_depth; - // TODO: don't waste the first element. //! The vector that contains the keys in the tree. //! If a pair has \p unused_index as first element, it means it is not used. - //! Its size is reserved_size + 2, because the first element is not used, - //! and the last element is used as marker for unordered iterators. + //! Its size is reserved_size + 2, because the first and the last elements + //! are used as markers for iterators. dimension_type* indexes; //! The vector that contains the data of the keys in the tree. diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh index 59e3dcf..8de94c1 100644 --- a/src/CO_Tree.inlines.hh +++ b/src/CO_Tree.inlines.hh @@ -419,10 +419,12 @@ CO_Tree::rebuild_bigger_tree() { new (&(new_indexes[j])) dimension_type(unused_index); } - // This was used as a marker by unordered iterators. + // These were used as markers by iterators. + indexes[0].~dimension_type(); indexes[reserved_size + 1].~dimension_type(); - // This is used as a marker by unordered iterators. + // These are used as markers by iterators. + new (&(new_indexes[0])) dimension_type(0); new (&(new_indexes[new_reserved_size + 1])) dimension_type(0); free(indexes); @@ -1094,8 +1096,9 @@ CO_Tree::inorder_iterator::get_previous_value() { #ifdef USE_PPL_CO_TREE_DFS_LAYOUT --i; - while (i != 0 && tree->indexes[i] == unused_index) - --i; + if (!tree->empty()) + while (tree->indexes[i] == unused_index) + --i; #endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT) } @@ -1743,8 +1746,9 @@ CO_Tree::inorder_const_iterator::get_previous_value() { #ifdef USE_PPL_CO_TREE_DFS_LAYOUT --i; - while (i != 0 && tree->indexes[i] == unused_index) - --i; + if (!tree->empty()) + while (tree->indexes[i] == unused_index) + --i; #endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT) }

1 0

[GIT] ppl/ppl(sparse_matrices): Removed .orig file, tracked by mistake.
by Marco Poletti 07 May '10

07 May '10

Module: ppl/ppl Branch: sparse_matrices Commit: c59c3e8feef1b203953a6a663f414fb4b12d9d77 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c59c3e8feef1… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri May 7 16:39:27 2010 +0200 Removed .orig file, tracked by mistake. --- src/CO_Tree.inlines.hh.orig | 2033 ------------------------------------------- 1 files changed, 0 insertions(+), 2033 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=c59c3e8f…

1 0