[PPL-devel] [GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: add an optimized version of add_mul_assign_row() for sparse backends with slow insertions.

[Marco Poletti]

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

Author: Marco Poletti <poletti.marco at gmail.com>
Date:   Mon Mar 22 21:14:00 2010 +0100

PIP_Tree.cc: add an optimized version of add_mul_assign_row() for sparse backends with slow insertions.

---

 src/PIP_Tree.cc |   73 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 73 insertions(+), 0 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 2cd3578..f55a4e7 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -42,6 +42,8 @@ mod_assign(Coefficient& z,
     z += y;
 }
 
+#ifndef PPL_SPARSE_BACKEND_SLOW_INSERTIONS
+
 // Compute x += c * y
 inline void
 add_mul_assign_row(PIP_Tree_Node::matrix_row_reference_type x,
@@ -127,6 +129,77 @@ add_mul_assign_row(PIP_Tree_Node::matrix_row_reference_type x,
   }
 }
 
+#else // !defined(PPL_SPARSE_BACKEND_SLOW_INSERTIONS)
+
+// Compute x += c * y
+inline void
+add_mul_assign_row(PIP_Tree_Node::matrix_row_reference_type x,
+                   Coefficient_traits::const_reference c,
+                   PIP_Tree_Node::matrix_row_const_reference_type y) {
+  PIP_Tree_Node::matrix_row_copy_type row(x.size());
+  PIP_Tree_Node::matrix_row_copy_iterator itr = row.end();
+  PIP_Tree_Node::matrix_row_const_iterator i = x.begin();
+  PIP_Tree_Node::matrix_row_const_iterator i_end = x.end();
+  PIP_Tree_Node::matrix_const_row_const_iterator j = y.begin();
+  PIP_Tree_Node::matrix_const_row_const_iterator j_end = y.end();
+  if (i == i_end && j == j_end)
+    return;
+  if (j == j_end
+      || (i != i_end && (*i).first < (*j).first)) {
+    itr = row.find_create(*i);
+    ++i;
+  } else
+      if (i == i_end
+          || (j != j_end && (*i).first < (*j).first)) {
+        itr = row.find_create(*j);
+        (*itr).second *= c;
+        ++j;
+      } else {
+        PPL_ASSERT(i != i_end);
+        PPL_ASSERT(j != j_end);
+        PPL_ASSERT((*i).first == (*j).first);
+        itr = row.find_create(*j);
+        (*itr).second *= c;
+        (*itr).second += (*i).second;
+        ++i;
+        ++j;
+      }
+  PPL_ASSERT(itr != row.end());
+  while (i != i_end && j != j_end) {
+    if ((*i).first < (*j).first) {
+      itr = row.find_create(*i,itr);
+      ++i;
+    } else {
+      if ((*i).first > (*j).first) {
+        itr = row.find_create(*j,itr);
+        (*itr).second *= c;
+        ++j;
+      } else {
+        PPL_ASSERT((*i).first == (*j).first);
+        itr = row.find_create(*j,itr);
+        (*itr).second *= c;
+        (*itr).second += (*i).second;
+        ++i;
+        ++j;
+      }
+    }
+  }
+  while (i != i_end) {
+    itr = row.find_create(*i,itr);
+    ++i;
+  }
+  PPL_ASSERT(i == i_end);
+  while (j != j_end) {
+    itr = row.find_create(*j,itr);
+    (*itr).second *= c;
+    ++j;
+  }
+  PPL_ASSERT(j == j_end);
+  std::swap(row,x);
+}
+
+#endif // !defined(PPL_SPARSE_BACKEND_SLOW_INSERTIONS)
+
 // Compute x -= y
 inline void
 sub_assign(PIP_Tree_Node::matrix_row_reference_type x,