Module: ppl/ppl Branch: master Commit: 96804c70b4db623d36eff204053761203529a84e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=96804c70b4db6...

Author: Marco Poletti poletti.marco@gmail.com Date: Thu Feb 17 12:07:39 2011 +0100

PIP_Solution_Node: improve the performance of solve().

---

src/PIP_Tree.cc | 20 +++++++++++++++----- 1 files changed, 15 insertions(+), 5 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index c9fe387..416abad 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -2602,6 +2602,10 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, Row& s_i = tableau.s[i]; PPL_DIRTY_TEMP_COEFFICIENT(s_i_pj); s_i_pj = s_i.get(pj); + + if (s_i_pj == 0) + continue; + Row::iterator itr = s_i.end(); for (Row::const_iterator j = s_pivot.begin(), j_end = s_pivot.end(); j != j_end; ++j) { @@ -2634,7 +2638,17 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, for (dimension_type i = num_rows; i-- > 0; ) { Row& s_i = tableau.s[i]; Row& t_i = tableau.t[i]; - Coefficient s_i_pj = s_i.get(pj); + + if (s_i.get(pj) == 0) + continue; + + // NOTE: For sparse rows, the non-const operator[] ensures that + // the element is actually stored in the row. At this point, however, + // it can't be zero, so it is already stored in the row. + // NOTE: This is a Coefficient& instead of a + // Coefficient_traits::const_reference, because scale() may silently + // modify it. + Coefficient& s_i_pj = s_i[pj]; Row::iterator k = t_i.end(); for (Row::const_iterator j = t_pivot.begin(), j_end = t_pivot.end(); j != j_end; ++j) { @@ -2647,10 +2661,6 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, gcd_assign(gcd, product, s_pivot_pj); exact_div_assign(scale_factor, s_pivot_pj, gcd); tableau.scale(scale_factor); - // s_i[pj] has been modified by scale(), so s_i_pj must be - // updated. - s_i_pj *= scale_factor; - PPL_ASSERT(s_i.get(pj) == s_i_pj); product *= scale_factor; } PPL_ASSERT(product % s_pivot_pj == 0);