[PPL-devel] [GIT] ppl/ppl(pip): Optimized some computation in helper function column_lower().

[Enea Zaffanella]

Module: ppl/ppl
Branch: pip
Commit: cd6b0004b5f79b0eeba6f21f58f5158cbbaab6b8
URL:    http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=cd6b0004b5f79b0eeba6f21f58f5158cbbaab6b8

Author: Enea Zaffanella <zaffanella at cs.unipr.it>
Date:   Sat Jan 30 23:23:24 2010 +0100

Optimized some computation in helper function column_lower().

---

 src/PIP_Tree.cc |   69 +++++++++++++++++++++++++++++++++++-------------------
 1 files changed, 45 insertions(+), 24 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index cb85de7..7d6781b 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -99,9 +99,9 @@ negate_assign(Row& x, const Row& y, Coefficient_traits::const_reference sc) {
 
 // Update given context matrix using local artificials
 dimension_type
-update_context(Matrix &context,
-               const PIP_Tree_Node::Artificial_Parameter_Sequence &ap) {
-  dimension_type ap_size = ap.size();
+update_context(Matrix& context,
+               const PIP_Tree_Node::Artificial_Parameter_Sequence& ap) {
+  const dimension_type ap_size = ap.size();
   if (ap_size > 0)
     context.add_zero_columns(ap_size);
   return ap_size;
@@ -109,14 +109,15 @@ update_context(Matrix &context,
 
 // Update given context matrix and parameter set using local artificials
 void
-update_context(Variables_Set &params, Matrix &context,
-                   const PIP_Tree_Node::Artificial_Parameter_Sequence &ap,
-                   dimension_type &space_dimension) {
-  dimension_type ap_size = update_context(context, ap);
-  if (ap_size > 0) {
-    for (dimension_type i = 0; i < ap_size; ++i)
-      params.insert(space_dimension++);
-  }
+update_context(Variables_Set& params, Matrix& context,
+               const PIP_Tree_Node::Artificial_Parameter_Sequence& ap,
+               dimension_type& space_dimension) {
+  const dimension_type ap_size = update_context(context, ap);
+  // Update parameters.
+  for (dimension_type i = 0; i < ap_size; ++i)
+    params.insert(space_dimension + i);
+  // Update space dimension.
+  space_dimension += ap_size;
 }
 
 /* Compares two columns lexicographically in revised simplex tableau
@@ -129,38 +130,58 @@ column_lower(const Matrix& tableau,
              const std::vector<dimension_type>& mapping,
              const std::vector<bool>& basis,
              const Row& pivot_a,
-             dimension_type ja,
+             const dimension_type ja,
              const Row& pivot_b,
-             dimension_type jb,
+             const dimension_type jb,
              Coefficient_traits::const_reference cst_a = -1,
              Coefficient_traits::const_reference cst_b = -1) {
-  PPL_DIRTY_TEMP_COEFFICIENT(cij_a);
-  PPL_DIRTY_TEMP_COEFFICIENT(cij_b);
   const Coefficient& sij_a = pivot_a[ja];
   const Coefficient& sij_b = pivot_b[jb];
   PPL_ASSERT(sij_a > 0);
   PPL_ASSERT(sij_b > 0);
+
+  PPL_DIRTY_TEMP_COEFFICIENT(lhs_coeff);
+  PPL_DIRTY_TEMP_COEFFICIENT(rhs_coeff);
+  lhs_coeff = cst_a * sij_b;
+  rhs_coeff = cst_b * sij_a;
+
   if (ja == jb) {
     // Same column: just compare the ratios.
     // This works since all columns are lexico-positive.
-    return cst_a * sij_b > cst_b * sij_a;
+    // return cst_a * sij_b > cst_b * sij_a;
+    return lhs_coeff > rhs_coeff;
   }
 
+  PPL_DIRTY_TEMP_COEFFICIENT(cij_a);
+  PPL_DIRTY_TEMP_COEFFICIENT(cij_b);
+  PPL_DIRTY_TEMP_COEFFICIENT(lhs);
+  PPL_DIRTY_TEMP_COEFFICIENT(rhs);
+  const dimension_type num_vars = mapping.size();
   dimension_type k = 0;
-  dimension_type num_vars = mapping.size();
   do {
-    dimension_type mk = mapping[k];
+    const dimension_type mk = mapping[k];
     if (basis[k]) {
       // Reconstitute the identity submatrix part of tableau.
-      cij_a = (mk==ja) ? 1 : 0;
-      cij_b = (mk==jb) ? 1 : 0;
+      cij_a = (mk == ja) ? 1 : 0;
+      cij_b = (mk == jb) ? 1 : 0;
     } else {
-      cij_a = tableau[mk][ja];
-      cij_b = tableau[mk][jb];
+      const Row& t_mk = tableau[mk];
+      cij_a = t_mk[ja];
+      cij_b = t_mk[jb];
     }
     ++k;
-  } while (k < num_vars && cij_a * cst_a * sij_b == cij_b * cst_b * sij_a);
-  return k < num_vars && cij_a * cst_a * sij_b > cij_b * cst_b * sij_a;
+    // Optimizing computation of while guard (and return value):
+    // (k < num_vars && cij_a * cst_a * sij_b == cij_b * cst_b * sij_a)
+    if (k == num_vars)
+      return false;
+    lhs = cij_a * lhs_coeff;
+    rhs = cij_b * rhs_coeff;
+  } while (lhs == rhs);
+
+  // Optimizing computation of return value:
+  // return k < num_vars && cij_a * cst_a * sij_b > cij_b * cst_b * sij_a;
+  assert(k < num_vars);
+  return lhs > rhs;
 }
 
 /* Find the column j in revised simplex tableau such as