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

Author: Marco Poletti poletti.marco@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,