Repository: systemml Updated Branches: refs/heads/master fc6f89128 -> 41de8dcdc
[SYSTEMML-2486] Performance matrix histogram estimator for dense This patch improves the performance of matrix histogram construction via a special case for fully dense matrices that allow for the construction from meta data without a pass over the input. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/41de8dcd Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/41de8dcd Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/41de8dcd Branch: refs/heads/master Commit: 41de8dcdc621b7dc2c1557aca64095512cdd6cf6 Parents: fc6f891 Author: Matthias Boehm <mboe...@gmail.com> Authored: Sat Oct 13 21:53:59 2018 +0200 Committer: Matthias Boehm <mboe...@gmail.com> Committed: Sat Oct 13 21:53:59 2018 +0200 ---------------------------------------------------------------------- .../org/apache/sysml/hops/estim/EstimatorBitsetMM.java | 6 +++--- .../apache/sysml/hops/estim/EstimatorDensityMap.java | 2 +- .../apache/sysml/hops/estim/EstimatorLayeredGraph.java | 2 +- .../sysml/hops/estim/EstimatorMatrixHistogram.java | 13 ++++++++++--- 4 files changed, 15 insertions(+), 8 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/41de8dcd/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 aacbf29..8802e9c 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java @@ -108,7 +108,7 @@ public class EstimatorBitsetMM extends SparsityEstimator } } - private abstract static class BitsetMatrix { + public abstract static class BitsetMatrix { protected final int _rlen; protected final int _clen; protected long _nonZeros; @@ -207,7 +207,7 @@ public class EstimatorBitsetMM extends SparsityEstimator * not allow for range ORs). However, this implies a maximum size of 16GB. * */ - private static class BitsetMatrix1 extends BitsetMatrix { + public static class BitsetMatrix1 extends BitsetMatrix { //linearized and padded data array in row-major order, where each long //represents 64 boolean values, all rows are aligned at 64 for simple access private final int _rowLen; @@ -407,7 +407,7 @@ public class EstimatorBitsetMM extends SparsityEstimator } @SuppressWarnings("unused") - private static class BitsetMatrix2 extends BitsetMatrix { + public static class BitsetMatrix2 extends BitsetMatrix { private BitSet[] _data; public BitsetMatrix2(int rlen, int clen) { http://git-wip-us.apache.org/repos/asf/systemml/blob/41de8dcd/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 27e6dcf..144f7a7 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java @@ -180,7 +180,7 @@ public class EstimatorDensityMap extends SparsityEstimator m1Map.getNumColumnsOrig(), _b, true); } - private static class DensityMap { + public static class DensityMap { private final MatrixBlock _map; private final int _rlen; private final int _clen; http://git-wip-us.apache.org/repos/asf/systemml/blob/41de8dcd/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java b/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java index fa8adaa..809ac8b 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java @@ -88,7 +88,7 @@ public class EstimatorLayeredGraph extends SparsityEstimator { return leafs; } - private static class LayeredGraph { + public static class LayeredGraph { private final List<Node[]> _nodes; //nodes partitioned by graph level private final int _rounds; //length of propagated r-vectors http://git-wip-us.apache.org/repos/asf/systemml/blob/41de8dcd/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 9f9075d..206c6d5 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java @@ -19,6 +19,7 @@ package org.apache.sysml.hops.estim; +import java.util.Arrays; import java.util.Random; import java.util.stream.IntStream; @@ -195,7 +196,7 @@ public class EstimatorMatrixHistogram extends SparsityEstimator h1.getRows(), h2.getCols(), nnz); } - private static class MatrixHistogram { + public static class MatrixHistogram { // count vectors (the histogram) private final int[] rNnz; //nnz per row private int[] rNnz1e = null; //nnz per row for cols w/ <= 1 non-zeros @@ -218,7 +219,12 @@ public class EstimatorMatrixHistogram extends SparsityEstimator && in.getNumRows() == in.getNumColumns(); // 2) compute basic synopsis details - if( !in.isEmpty() ) { + if( in.getLength() == in.getNonZeros() ) { + //fully dense: constant row/column counts + Arrays.fill(rNnz, n); + Arrays.fill(cNnz, m); + } + else if( !in.isEmpty() ) { if( in.isInSparseFormat() ) { SparseBlock a = in.getSparseBlock(); for( int i=0; i<m; i++ ) { @@ -250,7 +256,8 @@ public class EstimatorMatrixHistogram extends SparsityEstimator rNdiv2 = rSummary[3]; cNdiv2 = cSummary[3]; // 4) compute exception details if necessary (optional) - if( useExcepts & !in.isEmpty() && (rMaxNnz > 1 || cMaxNnz > 1) ) { + if( useExcepts && !in.isEmpty() && (rMaxNnz > 1 || cMaxNnz > 1) + && in.getLength() != in.getNonZeros() ) { //not fully dense rNnz1e = new int[in.getNumRows()]; cNnz1e = new int[in.getNumColumns()];