Module: ppl/ppl Branch: pip Commit: be3472f9d7b15cb7b31834a6f4e23a6fdd8bcf68 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=be3472f9d7b15... Author: Enea Zaffanella <zaffanella@cs.unipr.it> Date: Fri Feb 5 15:59:56 2010 +0100 Add new friend function add_mul_assign() for Linear_Expression. Used new function to optimize a couple of computations in PIP_Tree.cc. --- src/Linear_Expression.cc | 19 ++++++++++++++++++ src/Linear_Expression.defs.hh | 10 +++++++++ src/PIP_Tree.cc | 42 ++++++++++++++++++++++++++-------------- 3 files changed, 56 insertions(+), 15 deletions(-) diff --git a/src/Linear_Expression.cc b/src/Linear_Expression.cc index 4ffc709..f7d50a3 100644 --- a/src/Linear_Expression.cc +++ b/src/Linear_Expression.cc @@ -354,6 +354,25 @@ PPL::operator*=(Linear_Expression& e, Coefficient_traits::const_reference n) { return e; } +/*! \relates Parma_Polyhedra_Library::Linear_Expression */ +PPL::Linear_Expression& +PPL::add_mul_assign(Linear_Expression& e, + Coefficient_traits::const_reference n, + const Variable v) { + const dimension_type v_space_dim = v.space_dimension(); + if (v_space_dim > Linear_Expression::max_space_dimension()) + throw std::length_error("Linear_Expression& " + "PPL::add_mul_assign(e, n, v):\n" + "v exceeds the maximum allowed space dimension."); + const dimension_type e_size = e.size(); + if (e_size <= v_space_dim) { + Linear_Expression new_e(e, v_space_dim+1); + e.swap(new_e); + } + e[v_space_dim] += n; + return e; +} + bool PPL::Linear_Expression::OK() const { return Linear_Row::OK(); diff --git a/src/Linear_Expression.defs.hh b/src/Linear_Expression.defs.hh index 2367c94..b4ce1e0 100644 --- a/src/Linear_Expression.defs.hh +++ b/src/Linear_Expression.defs.hh @@ -166,6 +166,12 @@ operator-=(Linear_Expression& e, Coefficient_traits::const_reference n); Linear_Expression& operator*=(Linear_Expression& e, Coefficient_traits::const_reference n); +//! Returns the linear expression \p e + \p n * \p v and assigns it to \p e. +/*! \relates Linear_Expression */ +Linear_Expression& +add_mul_assign(Linear_Expression& e, + Coefficient_traits::const_reference n, Variable v); + namespace IO_Operators { //! Output operator. @@ -451,6 +457,10 @@ private: friend Linear_Expression& operator*=(Linear_Expression& e, Coefficient_traits::const_reference n); + friend Linear_Expression& + add_mul_assign(Linear_Expression& e, + Coefficient_traits::const_reference n, Variable v); + friend std::ostream& Parma_Polyhedra_Library::IO_Operators ::operator<<(std::ostream& s, const Linear_Expression& e); diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index c007c25..cb62db1 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -518,15 +518,21 @@ PIP_Tree_Node::OK() const { void PIP_Tree_Node ::add_constraint(const Row& row, const Variables_Set& parameters) { - const Variables_Set::const_iterator p_begin = parameters.begin(); - const Variables_Set::const_iterator p_end = parameters.end(); - PPL_ASSERT(static_cast<dimension_type>(std::distance(p_begin, p_end)) + 1 - == row.size()); - // FIXME: optimize the computation of expr. + const dimension_type num_params = parameters.size(); + PPL_ASSERT(num_params + 1 == row.size()); + + // Compute the expression for the parameter constraint. Linear_Expression expr = Linear_Expression(row[0]); - dimension_type j = 1; - for (Variables_Set::const_iterator pj = p_begin; pj != p_end; ++pj, ++j) - expr += row[j] * Variable(*pj); + // NOTE: iterating downward on parameters to avoid reallocations. + Variables_Set::const_reverse_iterator p_j = parameters.rbegin(); + // NOTE: index j spans [1..num_params] downwards. + for (dimension_type j = num_params; j > 0; --j) { + add_mul_assign(expr, row[j], Variable(*p_j)); + // Move to previous parameter. + ++p_j; + } + + // Add the parameter constraint. constraints_.insert(expr >= 0); } @@ -1723,8 +1729,6 @@ PIP_Solution_Node::solve(const PIP_Problem& problem, } // Compute columns t[*][j] : - // t[i][j] -= t[i][pj] * t_pivot[j] / s_pivot_pj; - // ENEA: FIXME: according to code below, this comment should read: // t[i][j] -= s[i][pj] * t_pivot[j] / s_pivot_pj; for (dimension_type j = num_params; j-- > 0; ) { const Coefficient& t_pivot_j = t_pivot[j]; @@ -2094,6 +2098,7 @@ PIP_Solution_Node::generate_cut(const dimension_type index, const Coefficient& den = tableau.get_denominator(); PPL_DIRTY_TEMP_COEFFICIENT(mod); + PPL_DIRTY_TEMP_COEFFICIENT(coeff); #ifdef NOISY_PIP std::cout << "Row " << index << " contains non-integer coefficients. " @@ -2125,15 +2130,22 @@ PIP_Solution_Node::generate_cut(const dimension_type index, mod_assign(mod, row_t[0], den); Linear_Expression expr; if (mod != 0) { + // Optimizing computation: expr += (den - mod); expr += den; expr -= mod; } - Variables_Set::const_iterator p = parameters.begin(); - for (dimension_type j = 1; j < num_params; ++j, ++p) { + // NOTE: iterating downwards on parameters to avoid reallocations. + Variables_Set::const_reverse_iterator p_j = parameters.rbegin(); + // NOTE: index j spans [1..num_params-1] downwards. + for (dimension_type j = num_params; j-- > 1; ) { mod_assign(mod, row_t[j], den); - // FIXME: find a way to optimize the following. - if (mod != 0) - expr += (den - mod) * Variable(*p); + if (mod != 0) { + // Optimizing computation: expr += (den - mod) * Variable(*p_j); + coeff = den - mod; + add_mul_assign(expr, coeff, Variable(*p_j)); + } + // Mode to previous parameter. + ++p_j; } // Generate new artificial parameter. Artificial_Parameter ap(expr, den);