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 69ae571988 [SYSTEMDS-3552] Cleanup and perf tests DCSR sparse block
69ae571988 is described below
commit 69ae5719883ae47ab2b6da704ca255737533655d
Author: Jaybit0 <[email protected]>
AuthorDate: Tue Jan 23 18:12:09 2024 +0100
[SYSTEMDS-3552] Cleanup and perf tests DCSR sparse block
Closes #1989.
---
docs/performance/SparseFormats.md | 73 +++++++
.../apache/sysds/runtime/data/SparseBlockCOO.java | 15 ++
.../apache/sysds/runtime/data/SparseBlockCSR.java | 15 ++
.../apache/sysds/runtime/data/SparseBlockDCSR.java | 23 ++-
.../apache/sysds/runtime/data/SparseBlockMCSR.java | 29 ++-
.../java/org/apache/sysds/performance/Main.java | 134 +++++++++++++
.../performance/matrix/MatrixMulPerformance.java | 195 ++++++++++++++++++
.../sysds/performance/matrix/MatrixStorage.java | 219 +++++++++++++++++++++
8 files changed, 698 insertions(+), 5 deletions(-)
diff --git a/docs/performance/SparseFormats.md
b/docs/performance/SparseFormats.md
new file mode 100644
index 0000000000..bf81b9019f
--- /dev/null
+++ b/docs/performance/SparseFormats.md
@@ -0,0 +1,73 @@
+<!--
+{% comment %}
+Licensed to the Apache Software Foundation (ASF) under one or more
+contributor license agreements. See the NOTICE file distributed with
+this work for additional information regarding copyright ownership.
+The ASF licenses this file to you under the Apache License, Version 2.0
+(the "License"); you may not use this file except in compliance with
+the License. You may obtain a copy of the License at
+
+http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+{% endcomment %}
+-->
+
+# Sparse block performance comparison
+
+This file contains a short evaluation of different sparse blocks. We included
one dense block (DenseBlockFP64) as a baseline.
+
+## Execution time
+We measured the performance of two matrices being multiplied, both of the
corresponding block type.
+Before each measurement, we performed `30` warmup runs (performing `30` matrix
multiplications to random matrices without measuring).
+Then, we measured the delta nanos of the operation below `100` times and took
the average.
+For this, we selected a block size of `1024x1024`.
+
+```java
+MatrixBlock m3 = m1.aggregateBinaryOperations(m1, m2,
+ new MatrixBlock(), InstructionUtils.getMatMultOperator(1));
+```
+
+
+
+## Storage
+
+The image below shows the memory consumption of each block type for different
sparsities. This was evaluated using blocks with 1024 rows and 1024 columns.
+
+
+
+We also evaluated on different matrix shapes by fixing the number of rows and
manipulating the number of columns.
+These tests were repeated for different sparsities.
+
+
+
+
+
+
+
+
+
+
+
+To get more meaningful results, the next evaluation fixes the number of
entries in a matrix to `1024x1024` and adapts the column-to-row `ratio` (and
vice versa) accordingly.
+We define the ratio as `cl = (1 + ratio) * rl` if `ratio >= 0`, otherwise as
`rl = (1 - ratio) * cl`.
+If we have for example a `ratio=1`, this means that there are twice as many
columns as rows. If the `ratio=-1`, this means that there are twice as many
rows as columns.
+Each test with a specific `ratio` was repeated `10` times with different
random matrices and we took the average memory consumption.
+The images below show our results for different sparsities.
+
+
+
+
+
+
+
+
+
+
+
+
+
\ No newline at end of file
diff --git a/src/main/java/org/apache/sysds/runtime/data/SparseBlockCOO.java
b/src/main/java/org/apache/sysds/runtime/data/SparseBlockCOO.java
index aea34f955b..124c942122 100644
--- a/src/main/java/org/apache/sysds/runtime/data/SparseBlockCOO.java
+++ b/src/main/java/org/apache/sysds/runtime/data/SparseBlockCOO.java
@@ -157,6 +157,21 @@ public class SparseBlockCOO extends SparseBlock
//robustness for long overflows
return (long) Math.min(size, Long.MAX_VALUE);
}
+
+ /**
+ * Computes the exact size in memory of the materialized block
+ * @return the exact size in memory
+ */
+ public long getExactSizeInMemory() {
+ //32B overhead per array, int/int/double arr in nnz
+ double size = 16 + 8; //object + 2 int fields
+ size += MemoryEstimates.intArrayCost(_rindexes.length);
//rindexes array (row indexes)
+ size += MemoryEstimates.intArrayCost(_cindexes.length);
//cindexes array (column indexes)
+ size += MemoryEstimates.doubleArrayCost(_values.length);
//values array (non-zero values)
+
+ //robustness for long overflows
+ return (long) Math.min(size, Long.MAX_VALUE);
+ }
///////////////////
//SparseBlock implementation
diff --git a/src/main/java/org/apache/sysds/runtime/data/SparseBlockCSR.java
b/src/main/java/org/apache/sysds/runtime/data/SparseBlockCSR.java
index 30ea45c80d..0aff4e08bb 100644
--- a/src/main/java/org/apache/sysds/runtime/data/SparseBlockCSR.java
+++ b/src/main/java/org/apache/sysds/runtime/data/SparseBlockCSR.java
@@ -283,6 +283,21 @@ public class SparseBlockCSR extends SparseBlock
//robustness for long overflows
return (long) Math.min(size, Long.MAX_VALUE);
}
+
+ /**
+ * Computes the exact size in memory of the materialized block
+ * @return the exact size in memory
+ */
+ public long getExactSizeInMemory() {
+ //32B overhead per array, int arr in nrows, int/double arr in
nnz
+ double size = 16 + 4 + 4;
//object + int field + padding
+ size += MemoryEstimates.intArrayCost(_ptr.length); //ptr
array (row pointers)
+ size += MemoryEstimates.intArrayCost(_indexes.length);
//indexes array (column indexes)
+ size += MemoryEstimates.doubleArrayCost(_values.length);
//values array (non-zero values)
+
+ //robustness for long overflows
+ return (long) Math.min(size, Long.MAX_VALUE);
+ }
/**
diff --git a/src/main/java/org/apache/sysds/runtime/data/SparseBlockDCSR.java
b/src/main/java/org/apache/sysds/runtime/data/SparseBlockDCSR.java
index fd187f3064..447781a520 100644
--- a/src/main/java/org/apache/sysds/runtime/data/SparseBlockDCSR.java
+++ b/src/main/java/org/apache/sysds/runtime/data/SparseBlockDCSR.java
@@ -168,10 +168,10 @@ public class SparseBlockDCSR extends SparseBlock
double lnnz = Math.max(INIT_CAPACITY,
Math.ceil(sparsity*nrows*ncols));
//32B overhead per array, int arr in nrows, int/double arr in
nnz
- double size = 16;
// Memory overhead of the object
- size += 4 + 4 + 4 + 4;
// 3x int field + 0 (padding not necessary)
- size += MemoryEstimates.intArrayCost(nrows); //
rowidx array (row indices)
- size += MemoryEstimates.intArrayCost(nrows+1); // rowptr array
(row pointers)
+ double size = 16; // Memory
overhead of the object
+ size += 4 + 4 + 4 + 4; // 3x int
field + 0 (padding not necessary)
+ size += MemoryEstimates.intArrayCost(nrows); // rowidx
array (row indices)
+ size += MemoryEstimates.intArrayCost(nrows+1); // rowptr
array (row pointers)
size += MemoryEstimates.intArrayCost((long) lnnz); // colidx
array (column indexes)
size += MemoryEstimates.doubleArrayCost((long) lnnz);// values
array (non-zero values)
@@ -179,6 +179,21 @@ public class SparseBlockDCSR extends SparseBlock
return (long) Math.min(size, Long.MAX_VALUE);
}
+ /**
+ * Computes the exact size in memory of the materialized block
+ * @return the exact size in memory
+ */
+ public long getExactSizeInMemory() {
+ double size = 16;
+ size += 4 + 4 + 4 + 4;
+ size += MemoryEstimates.intArrayCost(_rowidx.length);
+ size += MemoryEstimates.intArrayCost(_rowptr.length);
+ size += MemoryEstimates.intArrayCost(_colidx.length);
+ size += MemoryEstimates.doubleArrayCost(_values.length);
+
+ return (long) Math.min(size, Long.MAX_VALUE);
+ }
+
///////////////////
//SparseBlock implementation
diff --git a/src/main/java/org/apache/sysds/runtime/data/SparseBlockMCSR.java
b/src/main/java/org/apache/sysds/runtime/data/SparseBlockMCSR.java
index c7e79b8dbc..f6fa157448 100644
--- a/src/main/java/org/apache/sysds/runtime/data/SparseBlockMCSR.java
+++ b/src/main/java/org/apache/sysds/runtime/data/SparseBlockMCSR.java
@@ -124,7 +124,7 @@ public class SparseBlockMCSR extends SparseBlock
double size = 16; //object
size += MemoryEstimates.objectArrayCost(nrows); //references
long sparseRowSize = 16; // object
- sparseRowSize += 4*4; // 3 integers + padding
+ sparseRowSize += 2*4; // 2 integers + padding
sparseRowSize += MemoryEstimates.intArrayCost(0);
sparseRowSize += MemoryEstimates.doubleArrayCost(0);
sparseRowSize += 12*Math.max(1, cnnz); //avoid bias by down
cast for ultra-sparse
@@ -134,6 +134,33 @@ public class SparseBlockMCSR extends SparseBlock
return (long) Math.min(size, Long.MAX_VALUE);
}
+ /**
+ * Computes the exact size in memory of the materialized block
+ * @return the exact size in memory
+ */
+ public long getExactSizeInMemory() {
+ double size = 16; //object
+ size += MemoryEstimates.objectArrayCost(_rows.length);
//references
+
+ for (SparseRow sr : _rows) {
+ if (sr == null)
+ continue;
+ long sparseRowSize = 16; // object
+ if( sr instanceof SparseRowScalar )
+ sparseRowSize += 12;
+ else { //SparseRowVector
+ sparseRowSize += 2*4; // 2 integers
+ sparseRowSize +=
MemoryEstimates.intArrayCost(0);
+ sparseRowSize +=
MemoryEstimates.doubleArrayCost(0);
+ sparseRowSize +=
12*((SparseRowVector)sr).capacity();
+ }
+ size += sparseRowSize; //sparse rows
+ }
+
+ // robustness for long overflows
+ return (long) Math.min(size, Long.MAX_VALUE);
+ }
+
///////////////////
//SparseBlock implementation
diff --git a/src/test/java/org/apache/sysds/performance/Main.java
b/src/test/java/org/apache/sysds/performance/Main.java
index 185a43e2c3..2fed0d7144 100644
--- a/src/test/java/org/apache/sysds/performance/Main.java
+++ b/src/test/java/org/apache/sysds/performance/Main.java
@@ -30,6 +30,9 @@ import
org.apache.sysds.performance.generators.FrameTransformFile;
import org.apache.sysds.performance.generators.GenMatrices;
import org.apache.sysds.performance.generators.IGenerate;
import org.apache.sysds.performance.generators.MatrixFile;
+import org.apache.sysds.performance.matrix.MatrixMulPerformance;
+import org.apache.sysds.performance.matrix.MatrixStorage;
+import org.apache.sysds.runtime.data.SparseBlock;
import org.apache.sysds.runtime.frame.data.FrameBlock;
import org.apache.sysds.runtime.matrix.data.MatrixBlock;
import org.apache.sysds.runtime.util.CommonThreadPool;
@@ -100,6 +103,18 @@ public class Main {
case 16:
run16(args);
break;
+ case 1000:
+ run1000(args);
+ break;
+ case 1001:
+ run1001(args);
+ break;
+ case 1002:
+ run1002(args);
+ break;
+ case 1003:
+ run1003(args);
+ break;
default:
break;
}
@@ -185,6 +200,125 @@ public class Main {
System.out.println(mb);
}
+ private static void run1000(String[] args) {
+ MatrixMulPerformance perf;
+ if (args.length < 3) {
+ perf = new MatrixMulPerformance();
+ } else {
+ // ... <rl> <cl> [resolution] [maxSparsity]
[resolution] [warmupRuns] [repetitions]
+ int rl = Integer.parseInt(args[1]);
+ int cl = Integer.parseInt(args[2]);
+ int resolution = 18;
+ float maxSparsity = .4f;
+ int warmupRuns = 30;
+ int repetitions = 100;
+
+ if (args.length > 3)
+ resolution = Integer.parseInt(args[3]);
+ if (args.length > 4)
+ maxSparsity = Float.parseFloat(args[4]);
+ if (args.length > 5)
+ warmupRuns = Integer.parseInt(args[5]);
+ if (args.length > 6)
+ repetitions = Integer.parseInt(args[6]);
+
+ perf = new MatrixMulPerformance(rl, cl, warmupRuns,
repetitions, resolution, maxSparsity, 2f);
+ }
+
+ perf.testSparseFormat(null, null);
+ perf.testSparseFormat(SparseBlock.Type.MCSR,
SparseBlock.Type.MCSR);
+ perf.testSparseFormat(SparseBlock.Type.CSR,
SparseBlock.Type.CSR);
+ perf.testSparseFormat(SparseBlock.Type.COO,
SparseBlock.Type.COO);
+ perf.testSparseFormat(SparseBlock.Type.DCSR,
SparseBlock.Type.DCSR);
+ }
+
+ private static void run1001(String[] args) {
+ // ... [rl] [cl] [repetitions] [resolution] [maxSparsity]
+ MatrixStorage ms;
+ int rl = 1024;
+ int cl = 1024;
+ int repetitions = 10;
+ int resolution = 18;
+ float maxSparsity = 0.4f;
+
+ if (args.length > 1)
+ rl = Integer.parseInt(args[1]);
+ if (args.length > 2)
+ cl = Integer.parseInt(args[2]);
+ if (args.length > 3)
+ repetitions = Integer.parseInt(args[3]);
+ if (args.length > 4)
+ resolution = Integer.parseInt(args[4]);
+ if (args.length > 5)
+ maxSparsity = Float.parseFloat(args[5]);
+
+ ms = new MatrixStorage(resolution, 2f, maxSparsity);
+
+ ms.testSparseFormat(null, rl, cl, repetitions);
+ ms.testSparseFormat(SparseBlock.Type.MCSR, rl, cl, repetitions);
+ ms.testSparseFormat(SparseBlock.Type.CSR, rl, cl, repetitions);
+ ms.testSparseFormat(SparseBlock.Type.COO, rl, cl, repetitions);
+ ms.testSparseFormat(SparseBlock.Type.DCSR, rl, cl, repetitions);
+ }
+
+ private static void run1002(String[] args) {
+ // ... [sparsity] [rl] [minCl] [maxCl] [resolution]
[repetitions]
+ MatrixStorage ms = new MatrixStorage();
+ float sparsity = 0.1f;
+ int rl = 1024;
+ int minCl = 50;
+ int maxCl = 2048;
+ int resolution = 21;
+ int repetitions = 10;
+
+ if (args.length > 1)
+ sparsity = Float.parseFloat(args[1]);
+ if (args.length > 2)
+ rl = Integer.parseInt(args[2]);
+ if (args.length > 3)
+ minCl = Integer.parseInt(args[3]);
+ if (args.length > 4)
+ maxCl = Integer.parseInt(args[4]);
+ if (args.length > 5)
+ resolution = Integer.parseInt(args[5]);
+ if (args.length > 6)
+ repetitions = Integer.parseInt(args[6]);
+
+ ms.testChangingDims(null, sparsity, rl, minCl, maxCl,
resolution, repetitions);
+ ms.testChangingDims(SparseBlock.Type.MCSR, sparsity, rl, minCl,
maxCl, resolution, repetitions);
+ ms.testChangingDims(SparseBlock.Type.CSR, sparsity, rl, minCl,
maxCl, resolution, repetitions);
+ ms.testChangingDims(SparseBlock.Type.COO, sparsity, rl, minCl,
maxCl, resolution, repetitions);
+ ms.testChangingDims(SparseBlock.Type.DCSR, sparsity, rl, minCl,
maxCl, resolution, repetitions);
+ }
+
+ private static void run1003(String[] args) {
+ // ... [sparsity] [resolution] [repetitions] [maxRowColRatio]
[numMatrixEntries]
+ MatrixStorage ms = new MatrixStorage();
+
+ float sparsity = 0.1f;
+ int resolution = 21;
+ int repetitions = 10;
+ float maxRowColRatio = 10f;
+ int numEntries = 1024 * 1024;
+
+ if (args.length > 1)
+ sparsity = Float.parseFloat(args[1]);
+ if (args.length > 2)
+ resolution = Integer.parseInt(args[2]);
+ if (args.length > 3)
+ repetitions = Integer.parseInt(args[3]);
+ if (args.length > 4)
+ maxRowColRatio = Float.parseFloat(args[4]);
+ if (args.length > 5)
+ numEntries = Integer.parseInt(args[5]);
+
+ ms.testBalancedDims(null, sparsity, numEntries, resolution,
maxRowColRatio, repetitions);
+ ms.testBalancedDims(SparseBlock.Type.MCSR, sparsity,
numEntries, resolution, maxRowColRatio, repetitions);
+ ms.testBalancedDims(SparseBlock.Type.CSR, sparsity, numEntries,
resolution, maxRowColRatio, repetitions);
+ ms.testBalancedDims(SparseBlock.Type.COO, sparsity, numEntries,
resolution, maxRowColRatio, repetitions);
+ ms.testBalancedDims(SparseBlock.Type.DCSR, sparsity,
numEntries, resolution, maxRowColRatio, repetitions);
+ }
+
public static void main(String[] args) {
try {
exec(Integer.parseInt(args[0]), args);
diff --git
a/src/test/java/org/apache/sysds/performance/matrix/MatrixMulPerformance.java
b/src/test/java/org/apache/sysds/performance/matrix/MatrixMulPerformance.java
new file mode 100644
index 0000000000..05b91d0ebe
--- /dev/null
+++
b/src/test/java/org/apache/sysds/performance/matrix/MatrixMulPerformance.java
@@ -0,0 +1,195 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.performance.matrix;
+
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.data.SparseBlockCOO;
+import org.apache.sysds.runtime.data.SparseBlockCSR;
+import org.apache.sysds.runtime.data.SparseBlockDCSR;
+import org.apache.sysds.runtime.data.SparseBlockMCSR;
+import org.apache.sysds.runtime.instructions.InstructionUtils;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.util.DataConverter;
+import org.apache.sysds.test.TestUtils;
+
+import java.util.Arrays;
+
+public class MatrixMulPerformance {
+
+ private final int _rl;
+ private final int _cl;
+
+ private final int warmupRuns;
+ private final int repetitions;
+ private final int resolution;
+ private final float resolutionDivisor;
+ private final float maxSparsity;
+
+ public MatrixMulPerformance() {
+ this(1024, 1024, 15, 50, 18, .4f, 2f);
+ }
+
+ public MatrixMulPerformance(int rl, int cl, int warmupRuns, int
repetitions,
+ int resolution, float maxSparsity, float stepDivisor)
+ {
+ _rl = rl;
+ _cl = cl;
+ this.warmupRuns = warmupRuns;
+ this.repetitions = repetitions;
+ this.resolution = resolution;
+ this.resolutionDivisor = stepDivisor;
+ this.maxSparsity = maxSparsity;
+ }
+
+ private float[] sparsityProvider() {
+ float[] sparsities = new float[resolution];
+ float currentValue = maxSparsity;
+
+ for (int i = 0; i < resolution; i++) {
+ sparsities[i] = currentValue;
+ currentValue /= resolutionDivisor;
+ }
+
+ return sparsities;
+ }
+
+ private static String printAsPythonList(float[] list) {
+ StringBuilder sb = new StringBuilder();
+ sb.append("[");
+
+ for (float el : list)
+ sb.append(el + ",");
+
+ if (list.length > 0)
+ sb.deleteCharAt(sb.length() - 1);
+
+ sb.append("]");
+ return sb.toString();
+ }
+
+ private static String printAsPythonList(double[] list) {
+ StringBuilder sb = new StringBuilder();
+ sb.append("[");
+
+ for (double el : list)
+ sb.append(el + ",");
+
+ if (list.length > 0)
+ sb.deleteCharAt(sb.length() - 1);
+
+ sb.append("]");
+ return sb.toString();
+ }
+
+ public void testSparseFormat(SparseBlock.Type btype1, SparseBlock.Type
btype2) {
+ float[] sparsities = this.sparsityProvider();
+ double[] avgNanosPerSparsity = new double[sparsities.length];
+ long[] results = new long[repetitions];
+ for (int sparsityIndex = 0; sparsityIndex < sparsities.length;
sparsityIndex++) {
+ // Warmup the JVM
+ for (int i = 0; i < warmupRuns; i++)
+ runSparsityEstimateTest(btype1, btype2,
sparsities[sparsityIndex]);
+
+ for (int i = 0; i < repetitions; i++)
+ results[i] = runSparsityEstimateTest(btype1,
btype2, sparsities[sparsityIndex]);
+
+ avgNanosPerSparsity[sparsityIndex] =
Arrays.stream(results).average().getAsDouble();
+ }
+
+ System.out.println("sparsities" + (btype1 == null ? "Dense" :
btype1.name()) + " = " + printAsPythonList(sparsities));
+ System.out.println("avgNanos" + (btype2 == null ? "Dense" :
btype2.name()) + " = " + printAsPythonList(avgNanosPerSparsity));
+ }
+
+ private long runSparsityEstimateTest(SparseBlock.Type btype1,
SparseBlock.Type btype2, float sparsity) {
+ double[][] A = TestUtils.generateTestMatrix(_rl, _cl, -10, 10,
sparsity, 7654321);
+ double[][] B = TestUtils.generateTestMatrix(_rl, _cl, -10, 10,
sparsity, 7654322);
+
+ MatrixBlock mbtmp1 = DataConverter.convertToMatrixBlock(A);
+ MatrixBlock mbtmp2 = DataConverter.convertToMatrixBlock(B);
+
+ MatrixBlock m1;
+ MatrixBlock m2;
+
+ if (btype1 == null && btype2 == null) {
+ if (mbtmp1.isInSparseFormat())
+ mbtmp1.sparseToDense();
+ if (mbtmp2.isInSparseFormat())
+ mbtmp2.sparseToDense();
+
+ m1 = mbtmp1;
+ m2 = mbtmp2;
+ } else {
+ // Ensure that these are sparse blocks
+ if (!mbtmp1.isInSparseFormat())
+ mbtmp1.denseToSparse(true);
+ if (!mbtmp2.isInSparseFormat())
+ mbtmp2.denseToSparse(true);
+
+ SparseBlock srtmp1 = mbtmp1.getSparseBlock();
+ SparseBlock srtmp2 = mbtmp2.getSparseBlock();
+ SparseBlock sblock1;
+ SparseBlock sblock2;
+
+ switch (btype1) {
+ case MCSR:
+ sblock1 = new SparseBlockMCSR(srtmp1);
+ break;
+ case CSR:
+ sblock1 = new SparseBlockCSR(srtmp1);
+ break;
+ case COO:
+ sblock1 = new SparseBlockCOO(srtmp1);
+ break;
+ case DCSR:
+ sblock1 = new SparseBlockDCSR(srtmp1);
+ break;
+ default:
+ throw new
IllegalArgumentException("Unknown sparse block type");
+ }
+
+ switch (btype2) {
+ case MCSR:
+ sblock2 = new SparseBlockMCSR(srtmp2);
+ break;
+ case CSR:
+ sblock2 = new SparseBlockCSR(srtmp2);
+ break;
+ case COO:
+ sblock2 = new SparseBlockCOO(srtmp2);
+ break;
+ case DCSR:
+ sblock2 = new SparseBlockDCSR(srtmp2);
+ break;
+ default:
+ throw new
IllegalArgumentException("Unknown sparse block type");
+ }
+
+ m1 = new MatrixBlock(_rl, _cl, sblock1.size(), sblock1);
+ m2 = new MatrixBlock(_rl, _cl, sblock2.size(), sblock2);
+ }
+
+ long nanos = System.nanoTime();
+
+ MatrixBlock m3 = m1.aggregateBinaryOperations(m1, m2,
InstructionUtils.getMatMultOperator(1));
+ m3.sum(); // forced execution
+
+ return System.nanoTime() - nanos;
+ }
+}
diff --git
a/src/test/java/org/apache/sysds/performance/matrix/MatrixStorage.java
b/src/test/java/org/apache/sysds/performance/matrix/MatrixStorage.java
new file mode 100644
index 0000000000..1a911fed7b
--- /dev/null
+++ b/src/test/java/org/apache/sysds/performance/matrix/MatrixStorage.java
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.performance.matrix;
+
+import org.apache.sysds.runtime.data.DenseBlockFP64;
+import org.apache.sysds.runtime.data.SparseBlock;
+import org.apache.sysds.runtime.data.SparseBlockCOO;
+import org.apache.sysds.runtime.data.SparseBlockCSR;
+import org.apache.sysds.runtime.data.SparseBlockDCSR;
+import org.apache.sysds.runtime.data.SparseBlockMCSR;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.util.DataConverter;
+import org.apache.sysds.test.TestUtils;
+
+public class MatrixStorage {
+
+ private final int resolution;
+ private final float resolutionDivisor;
+ private final float maxSparsity;
+
+ public MatrixStorage() {
+ this(18, 2f, .2f);
+ }
+
+ public MatrixStorage(int resolution, float resolutionDivisor, float
maxSparsity) {
+ this.resolution = resolution;
+ this.resolutionDivisor = resolutionDivisor;
+ this.maxSparsity = maxSparsity;
+ }
+
+ private float[] sparsityProvider() {
+ float[] sparsities = new float[resolution];
+ float currentValue = maxSparsity;
+
+ for (int i = 0; i < resolution; i++) {
+ sparsities[i] = currentValue;
+ currentValue /= resolutionDivisor;
+ }
+
+ return sparsities;
+ }
+
+ private int[][] dimsProvider(int rl, int maxCl, int minCl, int
resolution) {
+ int[][] dims = new int[2][resolution];
+ for (int i = 0; i < resolution; i++) {
+ dims[0][i] = rl;
+ dims[1][i] = (int)(minCl + i *
((maxCl-minCl)/((float)resolution-1)));
+ }
+
+ return dims;
+ }
+
+ int[][] balancedDimsProvider(int numEntries, float[] ratio, float qMax)
{
+ int resolution = ratio.length;
+ int[][] dims = new int[2][resolution];
+
+ for (int i = 0; i < resolution; i++) {
+ ratio[i] = -qMax + 2 * qMax * (i /
((float)resolution-1));
+ if (ratio[i] < 0) {
+ // Then columns are bigger than rows
+ // r * c = numEntries
+ // r = (1 + abs(ratio[i])) * c
+ // => numEntries = (1 + abs(ratio[i])) * c^2
+ // => c = sqrt(numEntries / (1 + abs(ratio[i])))
+ dims[1][i] =
Math.round((float)Math.sqrt(numEntries / (1 - ratio[i])));
+ dims[0][i] = Math.round(numEntries /
(float)dims[1][i]);
+ } else {
+ dims[0][i] =
Math.round((float)Math.sqrt(numEntries / (1 + ratio[i])));
+ dims[1][i] = Math.round(numEntries /
(float)dims[0][i]);
+ }
+ }
+
+ return dims;
+ }
+
+ private static String printAsPythonList(float[] list) {
+ StringBuilder sb = new StringBuilder();
+ sb.append("[");
+
+ for (float el : list)
+ sb.append(el + ",");
+
+ if (list.length > 0)
+ sb.deleteCharAt(sb.length() - 1);
+
+ sb.append("]");
+ return sb.toString();
+ }
+
+ private static String printAsPythonList(int[] list) {
+ StringBuilder sb = new StringBuilder();
+ sb.append("[");
+
+ for (long el : list)
+ sb.append(el + ",");
+
+ if (list.length > 0)
+ sb.deleteCharAt(sb.length() - 1);
+
+ sb.append("]");
+ return sb.toString();
+ }
+
+ private static String printAsPythonList(long[] list) {
+ StringBuilder sb = new StringBuilder();
+ sb.append("[");
+
+ for (long el : list)
+ sb.append(el + ",");
+
+ if (list.length > 0)
+ sb.deleteCharAt(sb.length() - 1);
+
+ sb.append("]");
+ return sb.toString();
+ }
+
+ public void testSparseFormat(SparseBlock.Type btype, int rl, int cl,
int repetitions) {
+ float[] sparsities = sparsityProvider();
+ long[][] results = new long[repetitions][sparsities.length];
+
+ for (int repetition = 0; repetition < repetitions; repetition++)
+ for (int sparsityIndex = 0; sparsityIndex <
sparsities.length; sparsityIndex++)
+ results[repetition][sparsityIndex] =
evaluateMemoryConsumption(btype, sparsities[sparsityIndex], rl, cl);
+
+
+ System.out.println("sparsities" + (btype == null ? "Dense" :
btype.name()) + " = " + printAsPythonList(sparsities));
+ System.out.println("memory" + (btype == null ? "Dense" :
btype.name()) + " = " + printAsPythonList(buildAverage(results)));
+ }
+
+ public void testChangingDims(SparseBlock.Type btype, double sparsity,
int rl, int minCl, int maxCl, int resolution, int repetitions) {
+ int[][] dims = dimsProvider(rl, minCl, maxCl, resolution);
+ long[][] results = new long[repetitions][resolution];
+
+ for (int repetition = 0; repetition < repetitions; repetition++)
+ for (int dimIndex = 0; dimIndex < resolution;
dimIndex++)
+ results[repetition][dimIndex] =
evaluateMemoryConsumption(btype, sparsity, dims[0][dimIndex],
dims[1][dimIndex]);
+
+
+ System.out.println("dims" + (btype == null ? "Dense" :
btype.name()) + " = " + printAsPythonList(dims[1]));
+ System.out.println("dimMemory" + (btype == null ? "Dense" :
btype.name()) + " = " + printAsPythonList(buildAverage(results)));
+ }
+
+ public void testBalancedDims(SparseBlock.Type btype, double sparsity,
int numEntries, int resolution, float qMax /*The maximum / minimum row-column
ratio*/, int repetitions) {
+ float[] ratios = new float[resolution];
+ int[][] dims = balancedDimsProvider(numEntries, ratios, qMax);
+ long[][] results = new long[repetitions][resolution];
+
+ for (int repetition = 0; repetition < repetitions; repetition++)
+ for (int ratioIndex = 0; ratioIndex < resolution;
ratioIndex++)
+ results[repetition][ratioIndex] =
evaluateMemoryConsumption(btype, sparsity, dims[0][ratioIndex],
dims[1][ratioIndex]);
+
+ System.out.println("ratio" + (btype == null ? "Dense" :
btype.name()) + " = " + printAsPythonList(ratios) + "");
+ System.out.println("ratioMemory" + (btype == null ? "Dense" :
btype.name()) + " = " + printAsPythonList(buildAverage(results)) + "");
+ }
+
+ private long[] buildAverage(long[][] results) {
+ long[] mResults = new long[results[0].length];
+ for (int i = 0; i < results[0].length; i++) {
+ for (int j = 0; j < results.length; j++)
+ mResults[i] += results[j][i];
+ mResults[i] /= results.length;
+ }
+
+ return mResults;
+ }
+
+ private long evaluateMemoryConsumption(SparseBlock.Type btype, double
sparsity, int rl, int cl) {
+ try
+ {
+ if (btype == null)
+ return Math.min(Long.MAX_VALUE, (long)
DenseBlockFP64.estimateMemory(rl, cl));
+
+ double[][] A = TestUtils.generateTestMatrix(rl, cl,
-10, 10, sparsity, 7654321);
+
+ MatrixBlock mbtmp =
DataConverter.convertToMatrixBlock(A);
+
+ if (!mbtmp.isInSparseFormat())
+ mbtmp.denseToSparse(true);
+
+ SparseBlock srtmp = mbtmp.getSparseBlock();
+ switch (btype) {
+ case MCSR:
+ SparseBlockMCSR mcsr = new
SparseBlockMCSR(srtmp);
+ return mcsr.getExactSizeInMemory();
+ case CSR:
+ SparseBlockCSR csr = new
SparseBlockCSR(srtmp);
+ return csr.getExactSizeInMemory();
+ case COO:
+ SparseBlockCOO coo = new
SparseBlockCOO(srtmp);
+ return coo.getExactSizeInMemory();
+ case DCSR:
+ SparseBlockDCSR dcsr = new
SparseBlockDCSR(srtmp);
+ return dcsr.getExactSizeInMemory();
+ }
+ } catch(Exception ex) {
+ ex.printStackTrace();
+ throw new RuntimeException(ex);
+ }
+ throw new IllegalArgumentException();
+ }
+}
