This is an automated email from the ASF dual-hosted git repository. mboehm7 pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/systemml.git
The following commit(s) were added to refs/heads/master by this push: new 75648fe [SYSTEMDS-209] Performance sparse matrix-colvector cell-wise multiply 75648fe is described below commit 75648fe8a3817a4971480b09cce3ae0d694c7d06 Author: Matthias Boehm <mboe...@gmail.com> AuthorDate: Tue May 26 20:15:24 2020 +0200 [SYSTEMDS-209] Performance sparse matrix-colvector cell-wise multiply While working on the new builtin function for connected components and ultra-sparse graphs, we found that 'rowMaxs(G * t(c))' performed orders of magnitude better than the semantically equivalent 't(colMaxs(G * c))'. The reason was a missing handling of strict sparse-safe operations for matrix-colvector operations, while this was already handled for matrix-rowvector operations. In detail, we performed unnecessary operations in the number of cells instead of in the number of non-zeros leading to worse asymptotic behavior. With the simple fix of this patch, now we have very similar performance. For example, on a scenario of performing 100 times G*c where X is a 10Kx10K, sparsity=0.0001 matrix, total execution time (for 100 operations) improved from 4.2s to 167ms. --- docs/Tasks.txt | 1 + .../apache/sysds/runtime/matrix/data/LibMatrixBincell.java | 12 +++++------- 2 files changed, 6 insertions(+), 7 deletions(-) diff --git a/docs/Tasks.txt b/docs/Tasks.txt index 3c9782f..081a44b 100644 --- a/docs/Tasks.txt +++ b/docs/Tasks.txt @@ -171,6 +171,7 @@ SYSTEMDS-200 Various Fixes * 206 Fix codegen outer template compilation (tsmm) OK * 207 Fix builtin function call hoisting from expressions OK * 208 Fix bufferpool leak (live var analysis and createvar) OK + * 209 Fix performance sparse M-CV elementwise multiply OK SYSTEMDS-210 Extended lists Operations * 211 Cbind and Rbind over lists of matrices OK diff --git a/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixBincell.java b/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixBincell.java index 44d6f6a..34464a6 100644 --- a/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixBincell.java +++ b/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixBincell.java @@ -393,10 +393,9 @@ public class LibMatrixBincell int alen = a.size(i); int[] aix = a.indexes(i); double[] avals = a.values(i); - for( int j=apos; j<apos+alen; j++ ) - { + for( int j=apos; j<apos+alen; j++ ) { //empty left - for( int k = lastIx+1; k<aix[j]; k++ ){ + for( int k = lastIx+1; !skipEmpty&&k<aix[j]; k++ ){ double v = op.fn.execute( 0, v2 ); ret.appendValue(i, k, v); } @@ -408,7 +407,7 @@ public class LibMatrixBincell } //empty left - for( int k = lastIx+1; k<clen; k++ ){ + for( int k = lastIx+1; !skipEmpty&&k<clen; k++ ){ double v = op.fn.execute( 0, v2 ); ret.appendValue(i, k, v); } @@ -429,8 +428,7 @@ public class LibMatrixBincell int alen = a.size(i); int[] aix = a.indexes(i); double[] avals = a.values(i); - for( int j=apos; j<apos+alen; j++ ) - { + for( int j=apos; j<apos+alen; j++ ) { //empty left for( int k=lastIx+1; !skipEmpty&&k<aix[j]; k++ ){ double v2 = m2.quickGetValue(0, k); @@ -440,7 +438,7 @@ public class LibMatrixBincell //actual value double v2 = m2.quickGetValue(0, aix[j]); double v = op.fn.execute( avals[j], v2 ); - ret.appendValue(i, aix[j], v); + ret.appendValue(i, aix[j], v); lastIx = aix[j]; } }