Repository: systemml Updated Branches: refs/heads/master 504617758 -> 82a1d3468
[MINOR] Improved sparsity estimators bitset, densityMap, matrixHistogram This patch makes the following minor efficiency and runtime improvements: (1) For matrix self-products, we now only construct one instead of two sketches as the basis for estimation in order to reduce unnecessary memory and runtime overhead. (2) The matrix histogram, now leverages information about non-zero lhs rows and rhs columns to restrict the areas onto which non-zeros are projected. This technique generally improves accuracy. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/82a1d346 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/82a1d346 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/82a1d346 Branch: refs/heads/master Commit: 82a1d346883d9a86211a728060d059387217f230 Parents: 5046177 Author: Matthias Boehm <[email protected]> Authored: Thu Jul 19 21:04:07 2018 -0700 Committer: Matthias Boehm <[email protected]> Committed: Thu Jul 19 21:04:07 2018 -0700 ---------------------------------------------------------------------- .../java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java | 3 ++- .../java/org/apache/sysml/hops/estim/EstimatorDensityMap.java | 3 ++- .../org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java | 7 +++++-- 3 files changed, 9 insertions(+), 4 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/82a1d346/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java b/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java index 07507ff..98fb950 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java @@ -60,7 +60,8 @@ public class EstimatorBitsetMM extends SparsityEstimator { @Override public double estim(MatrixBlock m1, MatrixBlock m2) { BitsetMatrix m1Map = new BitsetMatrix(m1); - BitsetMatrix m2Map = new BitsetMatrix(m2); + BitsetMatrix m2Map = (m1 == m2) ? //self product + m1Map : new BitsetMatrix(m2); BitsetMatrix outMap = m1Map.matMult(m2Map); return OptimizerUtils.getSparsity( // aggregate output histogram outMap.getNumRows(), outMap.getNumColumns(), outMap.getNonZeros()); http://git-wip-us.apache.org/repos/asf/systemml/blob/82a1d346/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java b/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java index 9d58c3c..b6d8bd4 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java @@ -74,7 +74,8 @@ public class EstimatorDensityMap extends SparsityEstimator @Override public double estim(MatrixBlock m1, MatrixBlock m2) { MatrixBlock m1Map = computeDensityMap(m1); - MatrixBlock m2Map = computeDensityMap(m2); + MatrixBlock m2Map = (m1 == m2) ? //self product + m1Map : computeDensityMap(m2); MatrixBlock outMap = estimIntern(m1Map, m2Map, true, m1.getNumRows(), m1.getNumColumns(), m2.getNumColumns()); return OptimizerUtils.getSparsity( //aggregate output histogram http://git-wip-us.apache.org/repos/asf/systemml/blob/82a1d346/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java b/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java index 555bd3f..daac3df 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java @@ -75,7 +75,8 @@ public class EstimatorMatrixHistogram extends SparsityEstimator @Override public double estim(MatrixBlock m1, MatrixBlock m2) { MatrixHistogram h1 = new MatrixHistogram(m1, _useExcepts); - MatrixHistogram h2 = new MatrixHistogram(m2, _useExcepts); + MatrixHistogram h2 = (m1 == m2) ? //self product + h1 : new MatrixHistogram(m2, _useExcepts); return estimIntern(h1, h2); } @@ -96,7 +97,9 @@ public class EstimatorMatrixHistogram extends SparsityEstimator } //special case, with hybrid exact and approximate output else if(h1.cNnz1e!=null && h2.rNnz1e != null) { - int mnOut = h1.getRows()*h2.getCols(); + //note: normally h1.getRows()*h2.getCols() would define mnOut + //but by leveraging the knowledge of empty rows/cols we do better + int mnOut = h1.rNonEmpty * h2.cNonEmpty; double spOutRest = 0; for( int j=0; j<h1.getCols(); j++ ) { //exact fractions, w/o double counting
