[PPL-devel] [GIT] ppl/ppl(pip): Further optimization to helper function column_lower().

[Enea Zaffanella]

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

Author: Enea Zaffanella <zaffanella at cs.unipr.it>
Date:   Sun Jan 31 16:19:41 2010 +0100

Further optimization to helper function column_lower().

---

 src/PIP_Tree.cc |   55 ++++++++++++++++++++++++++++++++++---------------------
 1 files changed, 34 insertions(+), 21 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 8a3fad3..a7c173b 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -152,36 +152,49 @@ column_lower(const Matrix& tableau,
     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;
-  do {
+  // While loop guard is: (k < num_rows && lhs == rhs).
+  // Return value is false, if k >= num_rows; lhs < rhs, otherwise.
+  // Try to optimize the computation of lhs and rhs.
+  while (true) {
     const dimension_type mk = mapping[k];
-    if (basis[k]) {
+    const bool in_base = basis[k];
+    if (++k >= num_vars)
+      return false;
+    if (in_base) {
       // Reconstitute the identity submatrix part of tableau.
-      cij_a = (mk == ja) ? 1 : 0;
-      cij_b = (mk == jb) ? 1 : 0;
+      if (mk == ja) {
+        // Optimizing for: lhs == lhs_coeff && rhs == 0;
+        if (lhs_coeff == 0)
+          continue;
+        else
+          return lhs_coeff > 0;
+      }
+      if (mk == jb) {
+        // Optimizing for: lhs == 0 && rhs == rhs_coeff;
+        if (rhs_coeff == 0)
+          continue;
+        else
+          return 0 > rhs_coeff;
+      }
+      // Optimizing for: lhs == 0 && rhs == 0;
+      continue;
     } else {
+      // Not in base.
       const Row& t_mk = tableau[mk];
-      cij_a = t_mk[ja];
-      cij_b = t_mk[jb];
+      lhs = lhs_coeff * t_mk[ja];
+      rhs = rhs_coeff * t_mk[jb];
+      if (lhs == rhs)
+        continue;
+      else
+        return lhs > rhs;
     }
-    ++k;
-    // 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;
+  }
+  // This point should be unreachable.
+  throw std::runtime_error("PPL internal error");
 }
 
 /* Find the column j in revised simplex tableau such as