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 <[email protected]>
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];
}
}
