This is an automated email from the ASF dual-hosted git repository.
mboehm7 pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/systemds.git
The following commit(s) were added to refs/heads/main by this push:
new d7267058f8 [MINOR] Improved code coverage and fixes sparsity estimators
d7267058f8 is described below
commit d7267058f8226035858327057655a3417c94d0dd
Author: Matthias Boehm <[email protected]>
AuthorDate: Mon Nov 25 12:09:33 2024 +0100
[MINOR] Improved code coverage and fixes sparsity estimators
---
.../apache/sysds/hops/estim/EstimationUtils.java | 4 +-
.../apache/sysds/hops/estim/EstimatorBitsetMM.java | 18 +++-
.../test/component/estim/SelfProductTest.java | 107 ++++++++++++---------
.../component/estim/SquaredProductChainTest.java | 11 +++
4 files changed, 91 insertions(+), 49 deletions(-)
diff --git a/src/main/java/org/apache/sysds/hops/estim/EstimationUtils.java
b/src/main/java/org/apache/sysds/hops/estim/EstimationUtils.java
index 2cdb46b912..eeca0f115f 100644
--- a/src/main/java/org/apache/sysds/hops/estim/EstimationUtils.java
+++ b/src/main/java/org/apache/sysds/hops/estim/EstimationUtils.java
@@ -94,8 +94,8 @@ public abstract class EstimationUtils
double[] avals = a.values(i);
int aix = a.pos(i);
Arrays.fill(tmp, 0); //reset
- for( int k=aix; k<aix+n; k++ ) {
- double aval = avals[k];
+ for( int k=0; k<n; k++ ) {
+ double aval = avals[aix+k];
if( aval == 0 ) continue;
double[] bvals = a.values(k);
int bix = a.pos(k);
diff --git a/src/main/java/org/apache/sysds/hops/estim/EstimatorBitsetMM.java
b/src/main/java/org/apache/sysds/hops/estim/EstimatorBitsetMM.java
index 8917b03304..ec257553e7 100644
--- a/src/main/java/org/apache/sysds/hops/estim/EstimatorBitsetMM.java
+++ b/src/main/java/org/apache/sysds/hops/estim/EstimatorBitsetMM.java
@@ -45,6 +45,16 @@ import java.util.stream.IntStream;
*/
public class EstimatorBitsetMM extends SparsityEstimator
{
+ private final int _type;
+
+ public EstimatorBitsetMM() {
+ this(-1);
+ }
+
+ public EstimatorBitsetMM(int type) {
+ _type = type;
+ }
+
@Override
public DataCharacteristics estim(MMNode root) {
BitsetMatrix m1Map = getCachedSynopsis(root.getLeft());
@@ -205,14 +215,14 @@ public class EstimatorBitsetMM extends SparsityEstimator
//protected abstract BitsetMatrix reshape(int rows, int cols,
boolean byrow);
}
- public static BitsetMatrix createBitset(int m, int n) {
- return (long)m*n < Integer.MAX_VALUE ?
+ public BitsetMatrix createBitset(int m, int n) {
+ return ((long)m*n < Integer.MAX_VALUE && _type != 2) ?
new BitsetMatrix1(m, n) : //linearized long array
new BitsetMatrix2(m, n); //bitset per row
}
- public static BitsetMatrix createBitset(MatrixBlock in) {
- return in.getLength() < Integer.MAX_VALUE ?
+ public BitsetMatrix createBitset(MatrixBlock in) {
+ return (in.getLength() < Integer.MAX_VALUE && _type != 2) ?
new BitsetMatrix1(in) : //linearized long array
new BitsetMatrix2(in); //bitset per row
}
diff --git
a/src/test/java/org/apache/sysds/test/component/estim/SelfProductTest.java
b/src/test/java/org/apache/sysds/test/component/estim/SelfProductTest.java
index 7167dc2226..dd827f4990 100644
--- a/src/test/java/org/apache/sysds/test/component/estim/SelfProductTest.java
+++ b/src/test/java/org/apache/sysds/test/component/estim/SelfProductTest.java
@@ -26,8 +26,10 @@ import org.apache.sysds.hops.estim.EstimatorBasicAvg;
import org.apache.sysds.hops.estim.EstimatorBasicWorst;
import org.apache.sysds.hops.estim.EstimatorBitsetMM;
import org.apache.sysds.hops.estim.EstimatorDensityMap;
+import org.apache.sysds.hops.estim.EstimatorLayeredGraph;
import org.apache.sysds.hops.estim.EstimatorMatrixHistogram;
import org.apache.sysds.hops.estim.EstimatorSample;
+import org.apache.sysds.hops.estim.EstimatorSampleRa;
import org.apache.sysds.hops.estim.SparsityEstimator;
import org.apache.sysds.runtime.instructions.InstructionUtils;
import org.apache.sysds.runtime.matrix.data.MatrixBlock;
@@ -37,8 +39,10 @@ import org.apache.sysds.test.TestUtils;
public class SelfProductTest extends AutomatedTestBase
{
private final static int m = 2500;
- private final static double sparsity1 = 0.0001;
- private final static double sparsity2 = 0.000001;
+ private final static double sparsity0 = 0.5;
+ private final static double sparsity1 = 0.1;
+ private final static double sparsity2 = 0.0001;
+ private final static double sparsity3 = 0.000001;
private final static double eps1 = 0.05;
private final static double eps2 = 1e-4;
private final static double eps3 = 0;
@@ -50,97 +54,114 @@ public class SelfProductTest extends AutomatedTestBase
}
@Test
- public void testBasicAvgCase1() {
- runSparsityEstimateTest(new EstimatorBasicAvg(), m, sparsity1);
- }
-
- @Test
- public void testBasicAvgCase2() {
+ public void testBasicAvgCase() {
+ runSparsityEstimateTest(new EstimatorBasicAvg(), m/4,
sparsity0);
+ runSparsityEstimateTest(new EstimatorBasicAvg(), m/2,
sparsity1);
runSparsityEstimateTest(new EstimatorBasicAvg(), m, sparsity2);
+ runSparsityEstimateTest(new EstimatorBasicAvg(), m, sparsity3);
}
@Test
- public void testDensityMapCase1() {
- runSparsityEstimateTest(new EstimatorDensityMap(), m,
sparsity1);
- }
-
- @Test
- public void testDensityMapCase2() {
+ public void testDensityMapCase() {
+ runSparsityEstimateTest(new EstimatorDensityMap(), m/4,
sparsity0);
+ runSparsityEstimateTest(new EstimatorDensityMap(), m/2,
sparsity1);
runSparsityEstimateTest(new EstimatorDensityMap(), m,
sparsity2);
+ runSparsityEstimateTest(new EstimatorDensityMap(), m,
sparsity3);
}
@Test
- public void testDensityMap7Case1() {
- runSparsityEstimateTest(new EstimatorDensityMap(7), m,
sparsity1);
- }
-
- @Test
- public void testDensityMap7Case2() {
+ public void testDensityMap7Case() {
+ runSparsityEstimateTest(new EstimatorDensityMap(7), m/4,
sparsity0);
+ runSparsityEstimateTest(new EstimatorDensityMap(7), m/2,
sparsity1);
runSparsityEstimateTest(new EstimatorDensityMap(7), m,
sparsity2);
+ runSparsityEstimateTest(new EstimatorDensityMap(7), m,
sparsity3);
}
@Test
- public void testBitsetMatrixCase1() {
- runSparsityEstimateTest(new EstimatorBitsetMM(), m, sparsity1);
+ public void testBitsetMatrixCase() {
+ runSparsityEstimateTest(new EstimatorBitsetMM(), m/4,
sparsity0);
+ runSparsityEstimateTest(new EstimatorBitsetMM(), m/2,
sparsity1);
+ runSparsityEstimateTest(new EstimatorBitsetMM(), m, sparsity2);
+ runSparsityEstimateTest(new EstimatorBitsetMM(), m, sparsity3);
}
@Test
- public void testBitsetMatrixCase2() {
- runSparsityEstimateTest(new EstimatorBitsetMM(), m, sparsity2);
+ public void testBitset2MatrixCase() {
+ runSparsityEstimateTest(new EstimatorBitsetMM(2), m/4,
sparsity0);
+ runSparsityEstimateTest(new EstimatorBitsetMM(2), m/2,
sparsity1);
+ runSparsityEstimateTest(new EstimatorBitsetMM(2), m, sparsity2);
+ runSparsityEstimateTest(new EstimatorBitsetMM(2), m, sparsity3);
}
@Test
- public void testMatrixHistogramCase1() {
- runSparsityEstimateTest(new EstimatorMatrixHistogram(false), m,
sparsity1);
+ public void testMatrixHistogramCase() {
+ runSparsityEstimateTest(new EstimatorMatrixHistogram(false),
m/4, sparsity0);
+ runSparsityEstimateTest(new EstimatorMatrixHistogram(false),
m/2, sparsity1);
+ runSparsityEstimateTest(new EstimatorMatrixHistogram(false), m,
sparsity2);
+ runSparsityEstimateTest(new EstimatorMatrixHistogram(false), m,
sparsity3);
}
@Test
- public void testMatrixHistogramCase2() {
- runSparsityEstimateTest(new EstimatorMatrixHistogram(false), m,
sparsity2);
+ public void testMatrixHistogramExceptCase() {
+ runSparsityEstimateTest(new EstimatorMatrixHistogram(true),
m/4, sparsity0);
+ runSparsityEstimateTest(new EstimatorMatrixHistogram(true),
m/2, sparsity1);
+ runSparsityEstimateTest(new EstimatorMatrixHistogram(true), m,
sparsity2);
+ runSparsityEstimateTest(new EstimatorMatrixHistogram(true), m,
sparsity3);
}
@Test
- public void testMatrixHistogramExceptCase1() {
- runSparsityEstimateTest(new EstimatorMatrixHistogram(true), m,
sparsity1);
+ public void testSamplingDefCase() {
+ runSparsityEstimateTest(new EstimatorSample(), m, sparsity2);
+ runSparsityEstimateTest(new EstimatorSample(), m, sparsity3);
}
@Test
- public void testMatrixHistogramExceptCase2() {
- runSparsityEstimateTest(new EstimatorMatrixHistogram(true), m,
sparsity2);
+ public void testSampling20Case() {
+ runSparsityEstimateTest(new EstimatorSample(0.2), m, sparsity2);
+ runSparsityEstimateTest(new EstimatorSample(0.2), m, sparsity3);
}
@Test
- public void testSamplingDefCase1() {
- runSparsityEstimateTest(new EstimatorSample(), m, sparsity1);
+ public void testSamplingRaDefCase() {
+ runSparsityEstimateTest(new EstimatorSampleRa(), m/4,
sparsity0);
+ runSparsityEstimateTest(new EstimatorSampleRa(), m, sparsity2);
+ runSparsityEstimateTest(new EstimatorSampleRa(), m, sparsity3);
}
@Test
- public void testSamplingDefCase2() {
- runSparsityEstimateTest(new EstimatorSample(), m, sparsity2);
+ public void testSamplingRa20Case() {
+ runSparsityEstimateTest(new EstimatorSampleRa(0.2), m/4,
sparsity0);
+ runSparsityEstimateTest(new EstimatorSampleRa(0.2), m,
sparsity2);
+ runSparsityEstimateTest(new EstimatorSampleRa(0.2), m,
sparsity3);
}
@Test
- public void testSampling20Case1() {
- runSparsityEstimateTest(new EstimatorSample(0.2), m, sparsity1);
+ public void testLayeredGraphDefCase() {
+ runSparsityEstimateTest(new EstimatorLayeredGraph(), m,
sparsity2);
+ runSparsityEstimateTest(new EstimatorLayeredGraph(), m,
sparsity3);
}
@Test
- public void testSampling20Case2() {
- runSparsityEstimateTest(new EstimatorSample(0.2), m, sparsity2);
+ public void testLayeredGraph64Case() {
+ runSparsityEstimateTest(new EstimatorLayeredGraph(64), m,
sparsity2);
+ runSparsityEstimateTest(new EstimatorLayeredGraph(64), m,
sparsity3);
}
private static void runSparsityEstimateTest(SparsityEstimator estim,
int n, double sp) {
- MatrixBlock m1 = MatrixBlock.randOperations(m, n, sp, 1, 1,
"uniform", 3);
+ MatrixBlock m1 = MatrixBlock.randOperations(n, n, sp, 1, 1,
"uniform", 3);
MatrixBlock m3 = m1.aggregateBinaryOperations(m1, m1,
new MatrixBlock(),
InstructionUtils.getMatMultOperator(1));
- double spExact = OptimizerUtils.getSparsity(m, m,
+ double spExact1 = OptimizerUtils.getSparsity(n, n,
EstimationUtils.getSelfProductOutputNnz(m1));
+ double spExact2 = sp<0.4 ? OptimizerUtils.getSparsity(n, n,
+ EstimationUtils.getSparseProductOutputNnz(m1, m1)) :
spExact1;
//compare estimated and real sparsity
double est = estim.estim(m1, m1);
TestUtils.compareScalars(est, m3.getSparsity(),
(estim instanceof EstimatorBitsetMM) ? eps3 : //exact
(estim instanceof EstimatorBasicWorst) ? eps1 : eps2);
- TestUtils.compareScalars(m3.getSparsity(), spExact, eps3);
+ TestUtils.compareScalars(m3.getSparsity(), spExact1, eps3);
+ TestUtils.compareScalars(m3.getSparsity(), spExact2, eps3);
}
}
diff --git
a/src/test/java/org/apache/sysds/test/component/estim/SquaredProductChainTest.java
b/src/test/java/org/apache/sysds/test/component/estim/SquaredProductChainTest.java
index 25cd99ecaf..3747ac55f1 100644
---
a/src/test/java/org/apache/sysds/test/component/estim/SquaredProductChainTest.java
+++
b/src/test/java/org/apache/sysds/test/component/estim/SquaredProductChainTest.java
@@ -24,6 +24,7 @@ import org.apache.sysds.hops.estim.EstimatorBasicAvg;
import org.apache.sysds.hops.estim.EstimatorBasicWorst;
import org.apache.sysds.hops.estim.EstimatorBitsetMM;
import org.apache.sysds.hops.estim.EstimatorDensityMap;
+import org.apache.sysds.hops.estim.EstimatorLayeredGraph;
import org.apache.sysds.hops.estim.EstimatorMatrixHistogram;
import org.apache.sysds.hops.estim.MMNode;
import org.apache.sysds.hops.estim.SparsityEstimator;
@@ -126,6 +127,16 @@ public class SquaredProductChainTest extends
AutomatedTestBase
runSparsityEstimateTest(new EstimatorMatrixHistogram(true), m,
k, n, n2, case2);
}
+ @Test
+ public void testLayeredGraphCase1() {
+ runSparsityEstimateTest(new EstimatorLayeredGraph(32), m, k, n,
n2, case1);
+ }
+
+ @Test
+ public void testLayeredGraphCase2() {
+ runSparsityEstimateTest(new EstimatorLayeredGraph(32), m, k, n,
n2, case2);
+ }
+
private static void runSparsityEstimateTest(SparsityEstimator estim,
int m, int k, int n, int n2, double[] sp) {
MatrixBlock m1 = MatrixBlock.randOperations(m, k, sp[0], 1, 1,
"uniform", 1);
MatrixBlock m2 = MatrixBlock.randOperations(k, n, sp[1], 1, 1,
"uniform", 2);
