- PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: work when Coefficient_traits:: const_reference is just Coefficient, losing some performance when it's not.
by Marco Poletti 05 Sep '10

05 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: 4cfaaa1c287951c2ca45afd5126b762fb0d8faf0 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4cfaaa1c2879… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 5 08:53:03 2010 +0200 MIP_Problem: work when Coefficient_traits::const_reference is just Coefficient, losing some performance when it's not. --- src/MIP_Problem.cc | 22 +++++++++++----------- 1 files changed, 11 insertions(+), 11 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 15e7639..3d94007 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1089,14 +1089,14 @@ PPL::MIP_Problem::steepest_edge_exact_entering_index() const { // Compute the lcm of all the coefficients of variables in base. PPL_DIRTY_TEMP_COEFFICIENT(lcm_basis); lcm_basis = 1; - std::vector<const Coefficient*> tableau_base(tableau_num_rows); + std::vector<Coefficient> tableau_base(tableau_num_rows); for (dimension_type i = tableau_num_rows; i-- > 0; ) { - tableau_base[i] = &(tableau[i].get(base[i])); - lcm_assign(lcm_basis, lcm_basis, *(tableau_base[i])); + tableau_base[i] = tableau[i].get(base[i]); + lcm_assign(lcm_basis, lcm_basis, tableau_base[i]); } // Compute normalization factors. for (dimension_type i = tableau_num_rows; i-- > 0; ) - exact_div_assign(norm_factor[i], lcm_basis, *(tableau_base[i])); + exact_div_assign(norm_factor[i], lcm_basis, tableau_base[i]); // Compute the square of `lcm_basis', exploiting the fact that // `lcm_basis' will no longer be needed. lcm_basis *= lcm_basis; @@ -1471,8 +1471,8 @@ PPL::MIP_Problem // These pointers are used instead of references in the following loop, to // improve performance. const matrix_type::row_type* t_e = &(tableau[exiting_base_index]); - const Coefficient* t_e0 = &(t_e->get(0)); - const Coefficient* t_ee = &(t_e->get(entering_var_index)); + Coefficient t_e0 = t_e->get(0); + Coefficient t_ee = t_e->get(entering_var_index); for (dimension_type i = exiting_base_index + 1; i < tableau_num_rows; ++i) { const matrix_type::row_type& t_i = tableau[i]; Coefficient_traits::const_reference t_ie = t_i.get(entering_var_index); @@ -1480,9 +1480,9 @@ PPL::MIP_Problem const int t_ie_sign = sgn(t_ie); if (t_ie_sign != 0 && t_ie_sign == sgn(t_ib)) { WEIGHT_BEGIN(); - lcm_assign(lcm, *t_ee, t_ie); - exact_div_assign(current_min, lcm, *t_ee); - current_min *= *t_e0; + lcm_assign(lcm, t_ee, t_ie); + exact_div_assign(current_min, lcm, t_ee); + current_min *= t_e0; abs_assign(current_min); exact_div_assign(challenger, lcm, t_ie); challenger *= t_i.get(0); @@ -1493,8 +1493,8 @@ PPL::MIP_Problem || (sign == 0 && base[i] < base[exiting_base_index])) { exiting_base_index = i; t_e = &(tableau[exiting_base_index]); - t_e0 = &(t_e->get(0)); - t_ee = &(t_e->get(entering_var_index)); + t_e0 = t_e->get(0); + t_ee = t_e->get(entering_var_index); } WEIGHT_ADD(1044); }

1 0

[GIT] ppl/ppl(master): New commits
by Roberto Bagnara 04 Sep '10

04 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=11b0496ec14e… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 09:11:09 2010 +0200 CO_Tree: work even when data_type_const_reference is `data_type' instead of `const data_type&'. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=07022f13eecb… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 09:03:34 2010 +0200 CO_Tree: add dfs_index() methods. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d7c2c2f24f8b… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 08:31:12 2010 +0200 CO_Tree: add data_type_const_reference typedef and use it instead of const data_type&. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=dd779428e8d3… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 08:30:36 2010 +0200 Sparse_Row: use Coefficient_traits::const_reference instead of const Coefficient&. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d8d3dcc07bfd… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 08:30:23 2010 +0200 Dense_Row: use Coefficient_traits::const_reference instead of const Coefficient&. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=99c695c0bb08… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 08:30:06 2010 +0200 PIP_Tree: use Coefficient_traits::const_reference instead of const Coefficient&. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6b408bba2a53… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 08:29:49 2010 +0200 PIP_Problem: use Coefficient_traits::const_reference instead of const Coefficient&. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0111dca863d1… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 08:29:37 2010 +0200 MIP_Problem: use Coefficient_traits::const_reference instead of const Coefficient&.

1 0

[GIT] ppl/ppl(sparse_matrices): New commits
by Roberto Bagnara 04 Sep '10

04 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=11b0496ec14e… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 09:11:09 2010 +0200 CO_Tree: work even when data_type_const_reference is `data_type' instead of `const data_type&'. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=07022f13eecb… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 09:03:34 2010 +0200 CO_Tree: add dfs_index() methods. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d7c2c2f24f8b… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 08:31:12 2010 +0200 CO_Tree: add data_type_const_reference typedef and use it instead of const data_type&. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=dd779428e8d3… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 08:30:36 2010 +0200 Sparse_Row: use Coefficient_traits::const_reference instead of const Coefficient&. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d8d3dcc07bfd… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 08:30:23 2010 +0200 Dense_Row: use Coefficient_traits::const_reference instead of const Coefficient&. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=99c695c0bb08… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 08:30:06 2010 +0200 PIP_Tree: use Coefficient_traits::const_reference instead of const Coefficient&. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6b408bba2a53… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 08:29:49 2010 +0200 PIP_Problem: use Coefficient_traits::const_reference instead of const Coefficient&. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0111dca863d1… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 4 08:29:37 2010 +0200 MIP_Problem: use Coefficient_traits::const_reference instead of const Coefficient&.

1 0

[GIT] ppl/ppl(master): CO_Tree: fix compilation when Coefficient_traits:: const_reference is not `const Coefficient&'.
by Marco Poletti 03 Sep '10

03 Sep '10

Module: ppl/ppl Branch: master Commit: ebfce787809a33b59085a46cd478618fe73d505f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ebfce787809a… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 3 21:07:03 2010 +0200 CO_Tree: fix compilation when Coefficient_traits::const_reference is not `const Coefficient&'. --- src/CO_Tree.defs.hh | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index a3f1f91..95332f1 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -389,7 +389,7 @@ public: data_type& operator*(); //! Returns the current element. - const data_type& operator*() const; + Coefficient_traits::const_reference operator*() const; //! Returns the index of the element pointed to by \c *this. /*! @@ -1376,7 +1376,7 @@ public: data_type& operator*(); //! Returns the key and value of the current node. - const data_type& operator*() const; + Coefficient_traits::const_reference operator*() const; //! Returns a reference to the index of the element pointed to by \c *this. /*!

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: fix compilation when Coefficient_traits:: const_reference is not `const Coefficient&'.
by Marco Poletti 03 Sep '10

03 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: ebfce787809a33b59085a46cd478618fe73d505f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ebfce787809a… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 3 21:07:03 2010 +0200 CO_Tree: fix compilation when Coefficient_traits::const_reference is not `const Coefficient&'. --- src/CO_Tree.defs.hh | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index a3f1f91..95332f1 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -389,7 +389,7 @@ public: data_type& operator*(); //! Returns the current element. - const data_type& operator*() const; + Coefficient_traits::const_reference operator*() const; //! Returns the index of the element pointed to by \c *this. /*! @@ -1376,7 +1376,7 @@ public: data_type& operator*(); //! Returns the key and value of the current node. - const data_type& operator*() const; + Coefficient_traits::const_reference operator*() const; //! Returns a reference to the index of the element pointed to by \c *this. /*!

1 0

[GIT] ppl/ppl(sparse_matrices): New commits
by Roberto Bagnara 03 Sep '10

03 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c82df3eac8ce… Merge: 7d4b9abcd12085a554123d1dda6efc7d09037896 93f86477c1ef5185b4ff8981d5c92edef1ae29f0 Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 3 20:30:02 2010 +0200 Merge branch 'master' of ssh://git.cs.unipr.it/git/ppl/ppl URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7d4b9abcd120… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 3 20:29:20 2010 +0200 CO_Tree, Sparse_Row, Dense_Row: access the index and the value of element pointed to by an iterator using itr.index() and *itr instead of itr->first and itr->second. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a293f2ccd692… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 3 19:01:29 2010 +0200 CO_Tree::tree_iterator: rename index() method into dfs_index(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=93f86477c1ef… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Fri Sep 3 16:22:26 2010 +0200 Expected results updated. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=cbfe295dbb84… Merge: 0f64d29af1f3bb4cf83826095a606cf78d5d7353 14c85a1607cf3ccfbf016ae5ea808dafffa37d04 Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 3 16:19:40 2010 +0200 Merge branch 'sparse_matrices' URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0f64d29af1f3… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Fri Sep 3 15:55:06 2010 +0200 Updated expected results. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4bc6dff62fbd… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Fri Sep 3 15:29:25 2010 +0200 Version number fixed. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=533049e561be… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Fri Sep 3 15:07:16 2010 +0200 Revised Marco Poletti's entry. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=5347e4de5077… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Fri Sep 3 15:04:17 2010 +0200 By default, use sparse matrices both for MIP_Problem and PIP_Problem. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=5e070dcef884… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Fri Sep 3 15:03:04 2010 +0200 Slight improvement to the selection mechanism for sparse and dense matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=13b9bc2bf0c0… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Fri Sep 3 14:42:22 2010 +0200 Version number bumped.

1 0

[GIT] ppl/ppl(master): Merge branch 'master' of ssh://git.cs.unipr.it/git/ ppl/ppl
by Marco Poletti 03 Sep '10

03 Sep '10

Module: ppl/ppl Branch: master Commit: c82df3eac8ceb982b0be3cd90fe8806e55d1f92c URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c82df3eac8ce… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 3 20:30:02 2010 +0200 Merge branch 'master' of ssh://git.cs.unipr.it/git/ppl/ppl ---

1 0

[GIT] ppl/ppl(master): CO_Tree, Sparse_Row, Dense_Row: access the index and the value of element pointed to by an iterator using itr .index() and *itr instead of itr->first and itr->second.
by Marco Poletti 03 Sep '10

03 Sep '10

Module: ppl/ppl Branch: master Commit: 7d4b9abcd12085a554123d1dda6efc7d09037896 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7d4b9abcd120… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 3 20:29:20 2010 +0200 CO_Tree, Sparse_Row, Dense_Row: access the index and the value of element pointed to by an iterator using itr.index() and *itr instead of itr->first and itr->second. --- src/CO_Tree.cc | 100 ++++++++-------- src/CO_Tree.defs.hh | 204 +++++----------------------------- src/CO_Tree.inlines.hh | 161 +++++++-------------------- src/Dense_Row.defs.hh | 80 +++++--------- src/Dense_Row.inlines.hh | 73 +++---------- src/MIP_Problem.cc | 42 ++++---- src/PIP_Problem.cc | 4 +- src/PIP_Tree.cc | 222 ++++++++++++++++++------------------ src/Sparse_Row.cc | 32 +++--- src/Sparse_Row.inlines.hh | 30 +++--- src/Sparse_Row.templates.hh | 56 +++++----- tests/CO_Tree/cotree1.cc | 52 +++++----- tests/Sparse_Matrix/sparserow1.cc | 40 ++++---- 13 files changed, 403 insertions(+), 693 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=7d4b9abc…

1 0

[GIT] ppl/ppl(master): CO_Tree::tree_iterator: rename index() method into dfs_index().
by Marco Poletti 03 Sep '10

03 Sep '10

Module: ppl/ppl Branch: master Commit: a293f2ccd692a879441dd9ddb18a8da695a795e5 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a293f2ccd692… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 3 19:01:29 2010 +0200 CO_Tree::tree_iterator: rename index() method into dfs_index(). --- src/CO_Tree.cc | 7 ++++--- src/CO_Tree.defs.hh | 2 +- src/CO_Tree.inlines.hh | 6 +++--- 3 files changed, 8 insertions(+), 7 deletions(-) diff --git a/src/CO_Tree.cc b/src/CO_Tree.cc index d4b9123..754176f 100644 --- a/src/CO_Tree.cc +++ b/src/CO_Tree.cc @@ -791,14 +791,15 @@ PPL::CO_Tree::rebalance(tree_iterator itr, dimension_type key, // Step 1: compact elements of this subtree in the rightmost end, from right // to left. - dimension_type last_index_in_subtree = itr.index() + itr.get_offset() - 1; + dimension_type last_index_in_subtree + = itr.dfs_index() + itr.get_offset() - 1; dimension_type first_unused = compact_elements_in_the_rightmost_end(last_index_in_subtree, subtree_size, key, value, !deleting); // Step 2: redistribute the elements, from left to right. - redistribute_elements_in_subtree(itr.index(), subtree_size, + redistribute_elements_in_subtree(itr.dfs_index(), subtree_size, first_unused + 1, key, value, first_unused != last_index_in_subtree - subtree_size); @@ -1104,7 +1105,7 @@ PPL::CO_Tree::count_used_in_subtree(tree_iterator itr) { dimension_type n = 0; const dimension_type k = itr.get_offset(); - const dimension_type root_index = itr.index(); + const dimension_type root_index = itr.dfs_index(); // The complete subtree rooted at itr has 2*k - 1 nodes. diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index 3341b64..1501c77 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -1546,7 +1546,7 @@ public: \brief Returns the index of the current node in the DFS layout of the complete tree. */ - dimension_type index() const; + dimension_type dfs_index() const; /*! \brief Returns 2^h, with h the height of the current node in the tree, diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh index ce20bb6..91114b3 100644 --- a/src/CO_Tree.inlines.hh +++ b/src/CO_Tree.inlines.hh @@ -540,8 +540,8 @@ CO_Tree::iterator::swap(iterator& itr) { inline CO_Tree::iterator& CO_Tree::iterator::operator=(const tree_iterator& itr) { - current_index = &(itr.tree.indexes[itr.index()]); - current_data = &(itr.tree.data[itr.index()]); + current_index = &(itr.tree.indexes[itr.dfs_index()]); + current_data = &(itr.tree.data[itr.dfs_index()]); #if PPL_CO_TREE_EXTRA_DEBUG tree = &(itr.tree); #endif @@ -850,7 +850,7 @@ CO_Tree::tree_iterator::operator->() const { } inline dimension_type -CO_Tree::tree_iterator::index() const { +CO_Tree::tree_iterator::dfs_index() const { return i; }

1 0

[GIT] ppl/ppl(master): Expected results updated.
by Roberto Bagnara 03 Sep '10

03 Sep '10

Module: ppl/ppl Branch: master Commit: 93f86477c1ef5185b4ff8981d5c92edef1ae29f0 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=93f86477c1ef… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Fri Sep 3 16:22:26 2010 +0200 Expected results updated. --- demos/ppl_lpsol/expected_int16_a | 92 ++++++++++++------------------ demos/ppl_lpsol/expected_int32_a | 118 +++++++++++++------------------------- demos/ppl_lpsol/expected_int64_a | 34 ++++++----- demos/ppl_lpsol/expected_int8_a | 54 ++++++------------ 4 files changed, 111 insertions(+), 187 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=93f86477…

1 0