Repository: systemml Updated Branches: refs/heads/master dac22aae7 -> 54dbe9bb2
[SYSTEMML-2462] Fix correctness/performance in-place sparse binary ops This patch fixes result correctness issues (or alternatively index-out-of-bounds exceptions) on in-place sparse binary operations with left-hand-side inputs in CSR (as produced by special operations or dense to sparse conversion). This implementation assumed the lhs in MCSR and hence fails on row merging with CSR and COO. We now ensure that the in-place target is in MCSR. Furthermore, this also fixes a couple of performance issues due to unnecessary copies, unnecessary truncation, and potential gaps after zero introducing operations. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/54dbe9bb Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/54dbe9bb Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/54dbe9bb Branch: refs/heads/master Commit: 54dbe9bb26df16164a1c2ca4d0d5877e4fb95deb Parents: dac22aa Author: Matthias Boehm <[email protected]> Authored: Sat Jul 21 20:10:30 2018 -0700 Committer: Matthias Boehm <[email protected]> Committed: Sat Jul 21 20:10:30 2018 -0700 ---------------------------------------------------------------------- .../runtime/matrix/data/LibMatrixBincell.java | 108 +++++++++---------- 1 file changed, 50 insertions(+), 58 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/54dbe9bb/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java index ba431de..387182f 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java @@ -34,7 +34,6 @@ import org.apache.sysml.runtime.functionobjects.MinusMultiply; import org.apache.sysml.runtime.functionobjects.Multiply; import org.apache.sysml.runtime.functionobjects.Multiply2; import org.apache.sysml.runtime.functionobjects.NotEquals; -import org.apache.sysml.runtime.functionobjects.Or; import org.apache.sysml.runtime.functionobjects.Plus; import org.apache.sysml.runtime.functionobjects.PlusMultiply; import org.apache.sysml.runtime.functionobjects.Power2; @@ -47,16 +46,11 @@ import org.apache.sysml.runtime.util.SortUtils; import org.apache.sysml.runtime.util.UtilFunctions; /** - * MB: * Library for binary cellwise operations (incl arithmetic, relational, etc). Currently, * we don't have dedicated support for the individual operations but for categories of * operations and combinations of dense/sparse and MM/MV. Safe/unsafe refer to sparse-safe * and sparse-unsafe operations. - * * - * - * TODO: custom operator implementations in order to turn unnecessarily sparse-unsafe - * operations into sparse safe (e.g., relational operations) */ public class LibMatrixBincell { @@ -1114,74 +1108,54 @@ public class LibMatrixBincell } private static void safeBinaryInPlaceSparse(MatrixBlock m1ret, MatrixBlock m2, BinaryOperator op) { - if(m1ret.sparseBlock!=null) + //allocation and preparation (note: for correctness and performance, this + //implementation requires the lhs in MCSR and hence we explicitly convert) + if( m1ret.sparseBlock!=null ) m1ret.allocateSparseRowsBlock(false); - if(m2.sparseBlock!=null) + if( !(m1ret.sparseBlock instanceof SparseBlockMCSR) ) + m1ret.sparseBlock = SparseBlockFactory.copySparseBlock( + SparseBlock.Type.MCSR, m1ret.sparseBlock, false); + if( m2.sparseBlock!=null ) m2.allocateSparseRowsBlock(false); SparseBlock c = m1ret.sparseBlock; SparseBlock b = m2.sparseBlock; - final int rlen = m1ret.rlen; final int clen = m1ret.clen; - if( c!=null && b!=null ) - { - for(int r=0; r<rlen; r++) - { - if(c.isEmpty(r) && b.isEmpty(r)) continue; - + if( c!=null && b!=null ) { + for(int r=0; r<rlen; r++) { + if(c.isEmpty(r) && b.isEmpty(r)) + continue; if( b.isEmpty(r) ) { - int apos = c.pos(r); - int alen = c.size(r); - double[] values=c.values(r); - for(int i=apos; i<apos+alen; i++) - values[i]=op.fn.execute(values[i], 0); + zeroRightForSparseBinary(op, r, m1ret); + } + else if( c.isEmpty(r) ) { + appendRightForSparseBinary(op, b.values(r), b.indexes(r), b.pos(r), b.size(r), r, m1ret); } else { + //this approach w/ single copy only works with the MCSR format int estimateSize = Math.min(clen, (!c.isEmpty(r) ? c.size(r) : 0) + (!b.isEmpty(r) ? b.size(r) : 0)); - SparseRow thisRow = c.get(r); - c.set(r, new SparseRowVector(estimateSize, clen), false); - - if(thisRow!=null) { - m1ret.nonZeros-=thisRow.size(); - mergeForSparseBinary(op, thisRow.values(), thisRow.indexes(), 0, - thisRow.size(), b.values(r), b.indexes(r), b.pos(r), b.size(r), r, m1ret); - } - else { - appendRightForSparseBinary(op, b.values(r), b.indexes(r), b.pos(r), b.size(r), 0, r, m1ret); - } + SparseRow old = c.get(r); + c.set(r, new SparseRowVector(estimateSize), false); + m1ret.nonZeros -= old.size(); + mergeForSparseBinary(op, old.values(), old.indexes(), 0, + old.size(), b.values(r), b.indexes(r), b.pos(r), b.size(r), r, m1ret); } } } - else if( c == null ) { + else if( c == null ) { //lhs empty m1ret.sparseBlock = SparseBlockFactory.createSparseBlock(rlen); - for(int r=0; r<rlen; r++) { - if( !b.isEmpty(r) ) { - SparseRow tmp = new SparseRowVector( b.size(r), clen ); - appendRightForSparseBinary(op, b.values(r), b.indexes(r), b.pos(r), b.size(r), 0, r, m1ret); - m1ret.sparseBlock.set(r, tmp, false); - } + for( int r=0; r<rlen; r++) { + if( b.isEmpty(r) ) continue; + appendRightForSparseBinary(op, b.values(r), + b.indexes(r), b.pos(r), b.size(r), r, m1ret); } } - else //that.sparseRows==null - { - if( !(op.fn instanceof Plus || op.fn instanceof Minus || op.fn instanceof Or) ) { - for(int r=0; r<rlen; r++){ - if( !c.isEmpty(r) ) - { - SparseRow tmp = c.get(r); - int alen = tmp.size(); - double[] avals = tmp.values(); - for( int j=0; j<alen; j++ ) - avals[j] = op.fn.execute(avals[j], 0); - tmp.compact(); //handle removed entries (e.g., mult, and) - c.set(r, tmp, false); - - //NOTE: for left in-place, we cannot use append because it would create duplicates - //appendLeftForSparseBinary(op, arow.getValueContainer(), arow.getIndexContainer(), arow.size(), 0, r, m1ret); - } - } + else { //rhs empty + for(int r=0; r<rlen; r++) { + if( c.isEmpty(r) ) continue; + zeroRightForSparseBinary(op, r, m1ret); } } @@ -1354,11 +1328,29 @@ public class LibMatrixBincell } } + private static void appendRightForSparseBinary(BinaryOperator op, double[] vals, int[] ix, int pos, int size, int r, MatrixBlock ret) { + appendRightForSparseBinary(op, vals, ix, pos, size, 0, r, ret); + } + private static void appendRightForSparseBinary(BinaryOperator op, double[] values2, int[] cols2, int pos2, int size2, - int pos, int resultRow, MatrixBlock result) { + int pos, int r, MatrixBlock result) { for( int j=pos2+pos; j<pos2+size2; j++ ) { double v = op.fn.execute(0, values2[j]); - result.appendValue(resultRow, cols2[j], v); + result.appendValue(r, cols2[j], v); } } + + private static void zeroRightForSparseBinary(BinaryOperator op, int r, MatrixBlock ret) { + if( op.fn instanceof Plus || op.fn instanceof Minus ) + return; + SparseBlock c = ret.sparseBlock; + int apos = c.pos(r); + int alen = c.size(r); + double[] values = c.values(r); + boolean zero = false; + for(int i=apos; i<apos+alen; i++) + zero |= ((values[i] = op.fn.execute(values[i], 0)) == 0); + if( zero ) + c.compact(r); + } }
