You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@systemds.apache.org by mb...@apache.org on 2026/09/29 10:34:01 UTC
(systemds) branch main updated: [SYSTEMDS-3547] Extended tensor transposition for sparse inputs
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 91af40100b [SYSTEMDS-3547] Extended tensor transposition for sparse inputs
91af40100b is described below
commit 91af40100b00ef0393701952ca9da9dc19ff16a8
Author: BeceHQ <ch...@gmail.com>
AuthorDate: Tue Sep 29 12:26:52 2026 +0200
[SYSTEMDS-3547] Extended tensor transposition for sparse inputs
Closes #2547.
---
.../sysds/runtime/matrix/data/LibMatrixReorg.java | 482 ++++++------
.../matrix/libMatrixReorg/PermuteTest.java | 869 ++++++++++++++++-----
2 files changed, 901 insertions(+), 450 deletions(-)
diff --git a/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixReorg.java b/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixReorg.java
index 5f47897910..2b5cddd573 100644
--- a/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixReorg.java
+++ b/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixReorg.java
@@ -5004,8 +5004,8 @@ public class LibMatrixReorg {
/**
* Restores SystemDS matrix/tensor metadata after an in-place tensor permutation.
- * @param in matrix/tensor block whose metadata is restored
- * @param finalShape final tensor shape after permutation
+ * @param in matrix/tensor block whose metadata is restored
+ * @param finalShape final tensor shape after permutation
*/
private static void restoreMetadata(MatrixBlock in, int[] finalShape) {
in.setNumRows(finalShape[0]);
@@ -5016,7 +5016,7 @@ public class LibMatrixReorg {
if (in.getDenseBlock() != null)
in.getDenseBlock().setDims(finalShape);
}
-
+
private static long[] getStridesForPermutation(int[] dims) {
long[] strides = new long[dims.length];
long stride = 1;
@@ -5027,23 +5027,33 @@ public class LibMatrixReorg {
return strides;
}
- public static MatrixBlock permute(MatrixBlock in, int[] inDims, int[] perm) {
- return permute(in, inDims, perm, 1);
+ public static MatrixBlock permute(MatrixBlock inData, int[] inDims, int[] perm) {
+ return permute(inData, inDims, perm, 1);
}
- public static MatrixBlock permute(MatrixBlock in, int[] inDims, int[] perm, int k) {
+ public static MatrixBlock permute(MatrixBlock inData, int[] inDims, int[] perm, int k) {
+ //TODO Enable Pointers on first dim
int rank = inDims.length;
- boolean isIdentity = true;
- for( int i = 0; i < rank; i++ ) {
- if( perm[i] != i ) {
- isIdentity = false;
- break;
+ if( perm.length != rank ) {
+ throw new DMLRuntimeException("Permutation array must have the same length as inDims.");
+ }
+
+ boolean[] seen = new boolean[rank];
+ for( int p : perm ) {
+ if( p < 0 || p >= rank || seen[p] ) {
+ throw new IllegalArgumentException("Invalid permutation. Indices might be out of bounds or duplicate dimensions were given.");
}
+ seen[p] = true;
}
- if( isIdentity ) {
- return new MatrixBlock(in);
+ long expectedLength = 1;
+ for( int d : inDims ) {
+ expectedLength *= d;
+ }
+ long actualLength = (long) inData.getNumRows() * inData.getNumColumns();
+ if( expectedLength != actualLength ) {
+ throw new DMLRuntimeException("Dimensions (inDims) do not match the actual number of elements in the matrix.");
}
int[] outDims = new int[rank];
@@ -5056,299 +5066,253 @@ public class LibMatrixReorg {
length *= d;
}
- MatrixBlock out = new MatrixBlock(1, (int)length, false);
- out.allocateDenseBlock();
+ boolean isSparse = inData.isInSparseFormat();
+ MatrixBlock outData = new MatrixBlock(1, (int) length, isSparse);
+
+ if( isSparse ) {
+ int nnz = (int) inData.getNonZeros();
+ SparseBlockCSR csr = new SparseBlockCSR(1, nnz, nnz);
- DenseBlock inDB = in.getDenseBlock();
- DenseBlock outDB = out.getDenseBlock();
+ int[] rptr = csr.rowPointers();
+ rptr[0] = 0;
+ rptr[1] = nnz;
+
+ outData.setSparseBlock(csr);
+ } else {
+ outData.allocateDenseBlock();
+ }
long[] inStrides = getStridesForPermutation(inDims);
long[] outStrides = getStridesForPermutation(outDims);
-
- long[] permutedStrides = new long[rank];
+
+ int[] inversePermute = new int[rank];
for( int i = 0; i < rank; i++ ) {
- permutedStrides[i] = outStrides[perm[i]];
+ inversePermute[perm[i]] = i;
}
- boolean useParallel = (k > 1 || k == -1) && length >= PAR_NUMCELL_THRESHOLD;
- int numThreads = k == -1 ? Runtime.getRuntime().availableProcessors() : k;
-
- if( inDB.numBlocks() == 1 && outDB.numBlocks() == 1 ) {
- double[] inData = inDB.valuesAt(0);
- double[] outData = outDB.valuesAt(0);
-
- if( useParallel && rank > 0 ) {
- permuteSingleBlockParallel(inData, outData, inDims, inStrides,
- permutedStrides, numThreads, length);
- } else {
- permuteSingleBlock(inData, outData, inDims, inStrides,
- permutedStrides, 0, 0, 0);
- }
- } else {
- if( useParallel && rank > 0 ) {
- permuteMultiBlockParallel(inDB, outDB, inDims, inStrides,
- permutedStrides, numThreads, length);
- } else {
- permuteMultiBlock(inDB, outDB, inDims, inStrides,
- permutedStrides, 0, 0L, 0L);
- }
+ long[] permutedOutStrides = new long[rank];
+ for( int i = 0; i < rank; i++ ) {
+ permutedOutStrides[i] = outStrides[inversePermute[i]];
}
- return out;
- }
- private static void permuteSingleBlock(
- double[] inData, double[] outData,
- int[] inDims, long[] inStrides, long[] permutedStrides,
- int dim, int inOffset, int outOffset)
- {
- if( dim == inDims.length - 1 ) {
- int len = inDims[dim];
- int outStride = (int) permutedStrides[dim];
+ int rlen = inData.getNumRows();
+ int numThreads = k == -1 ? InfrastructureAnalyzer.getLocalParallelism() : k;
+ boolean useParallel = (numThreads > 1) && (length >= PAR_NUMCELL_THRESHOLD);
+
+ int[] cnt = null;
+ int[] outIndexes = null;
+ double[] outValues = null;
- if( outStride == 1 ) {
- System.arraycopy(inData, inOffset, outData, outOffset, len);
+ if( isSparse ) {
+ SparseBlockCSR csr = (SparseBlockCSR) outData.getSparseBlock();
+ outIndexes = csr.indexes();
+ outValues = csr.values();
+ }
+
+ if( !useParallel ) {
+ if( isSparse ) {
+ cnt = new int[]{0};
+ permuteSparseKernel(inData, inStrides, permutedOutStrides, 0, rlen, cnt, outIndexes, outValues, 0);
} else {
- transposeRow(inData, outData, inOffset, outOffset, outStride, len);
+ permuteDenseKernel(inData, outData, inStrides, permutedOutStrides, 0, rlen);
}
- return;
+ } else {
+ permuteMultiThreaded(inData, outData, inStrides, permutedOutStrides, rlen, numThreads, outIndexes, outValues);
}
- int dimSize = inDims[dim];
- long inStep = inStrides[dim];
- long outStep = permutedStrides[dim];
-
- final int BLOCK_SIZE = 128;
- for( int bi = 0; bi < dimSize; bi += BLOCK_SIZE ) {
- int bimin = Math.min(bi + BLOCK_SIZE, dimSize);
- for( int i = bi; i < bimin; i++ ) {
- permuteSingleBlock(
- inData, outData, inDims, inStrides, permutedStrides,
- dim + 1,
- inOffset + (int)(i * inStep),
- outOffset + (int)(i * outStep)
- );
- }
+ outData.recomputeNonZeros();
+ if( isSparse ) {
+ outData.sortSparseRows();
}
+ return outData;
}
- private static void permuteSingleBlockParallel(
- double[] inData, double[] outData,
- int[] inDims, long[] inStrides, long[] permutedStrides,
- int k, long totalElements) {
-
- final long elementsPerThread = Math.max(1024, (totalElements + k - 1) / k);
- final int actualThreads = (int) Math.min(k, (totalElements + elementsPerThread - 1) / elementsPerThread);
-
- final ExecutorService pool = CommonThreadPool.get(actualThreads);
+ private static void permuteMultiThreaded(MatrixBlock inData, MatrixBlock outData,
+ long[] inStrides, long[] permutedOutStrides, int rlen, int k,
+ int[] outIndexes, double[] outValues)
+ {
+ ExecutorService pool = CommonThreadPool.get(k);
try {
- final ArrayList<PermuteSingleBlockTask> tasks = new ArrayList<>();
+ ArrayList<PermuteTask> tasks = new ArrayList<>();
+ int blklen = (int) Math.ceil((double) rlen / k);
- for( int t = 0; t < actualThreads; t++ ) {
- final long start = t * elementsPerThread;
- final long end = Math.min(start + elementsPerThread, totalElements);
-
- if( start >= totalElements ) {
- break;
+ int[] cnt = null;
+ SparseBlock inSB = null;
+ int currentOffset = 0;
+
+ if( inData.isInSparseFormat() ) {
+ cnt = new int[k];
+ inSB = inData.getSparseBlock();
+ }
+
+ for( int i = 0; i < k && i * blklen < rlen; i++ ) {
+ int rl = i * blklen;
+ int ru = Math.min((i + 1) * blklen, rlen);
+
+ if( cnt != null && inSB != null ) {
+ cnt[i] = currentOffset;
+ for( int r = rl; r < ru; r++ ) {
+ if( !inSB.isEmpty(r) ) {
+ currentOffset += inSB.size(r);
+ }
+ }
}
-
- tasks.add(new PermuteSingleBlockTask(inData, outData, inDims,
- inStrides, permutedStrides, start, end));
+ tasks.add(new PermuteTask(inData, outData, inStrides, permutedOutStrides, rl, ru,
+ cnt, outIndexes, outValues, i));
}
for( Future<Object> task : pool.invokeAll(tasks) ) {
task.get();
}
- } catch (Exception ex) {
+
+ }
+ catch( Exception ex ) {
throw new DMLRuntimeException(ex);
- } finally {
+ }
+ finally {
pool.shutdown();
}
}
- private static void permuteMultiBlock(
- DenseBlock inDB, DenseBlock outDB,
- int[] inDims, long[] inStrides, long[] permutedStrides,
- int dim, long inOffset, long outOffset) {
-
- if( dim == inDims.length - 1 ) {
- int len = inDims[dim];
- long outStride = permutedStrides[dim];
-
- int inBlockSize = inDB.blockSize();
- int outBlockSize = outDB.blockSize();
-
- for( int i = 0; i < len; i++ ) {
- long currentInAbs = inOffset + i * inStrides[dim];
- long currentOutAbs = outOffset + i * outStride;
-
- int inBlockIdx = (int) (currentInAbs / inBlockSize);
- int inRelIdx = (int) (currentInAbs % inBlockSize);
-
- int outBlockIdx = (int) (currentOutAbs / outBlockSize);
- int outRelIdx = (int) (currentOutAbs % outBlockSize);
-
- double[] inArr = inDB.valuesAt(inBlockIdx);
- double[] outArr = outDB.valuesAt(outBlockIdx);
-
- if( inArr != null && outArr != null &&
- inRelIdx < inArr.length && outRelIdx < outArr.length ) {
- outArr[outRelIdx] = inArr[inRelIdx];
- }
- }
- return;
+ private static class PermuteTask implements Callable<Object> {
+ private final MatrixBlock _inData;
+ private final MatrixBlock _outData;
+ private final long[] _inStrides;
+ private final long[] _permutedOutStrides;
+ private final int _rl;
+ private final int _ru;
+ private final int[] _cnt;
+ private final int[] _outIndexes;
+ private final double[] _outValues;
+ private final int _taskID;
+
+ protected PermuteTask(MatrixBlock inData, MatrixBlock outData, long[] inStrides,
+ long[] permutedOutStrides, int rl, int ru,
+ int[] cnt, int[] outIndexes, double[] outValues, int taskID) {
+ _inData = inData;
+ _outData = outData;
+ _inStrides = inStrides;
+ _permutedOutStrides = permutedOutStrides;
+ _rl = rl;
+ _ru = ru;
+ _cnt = cnt;
+ _outIndexes = outIndexes;
+ _outValues = outValues;
+ _taskID = taskID;
}
- int dimSize = inDims[dim];
- long inStep = inStrides[dim];
- long outStep = permutedStrides[dim];
-
- final int BLOCK_SIZE = 128;
- for( int bi = 0; bi < dimSize; bi += BLOCK_SIZE ) {
- int bimin = Math.min(bi + BLOCK_SIZE, dimSize);
- for( int i = bi; i < bimin; i++ ) {
- permuteMultiBlock(
- inDB, outDB, inDims, inStrides, permutedStrides,
- dim + 1,
- inOffset + i * inStep,
- outOffset + i * outStep
- );
+ @Override
+ public Object call() {
+ if( _inData.isInSparseFormat() ) {
+ permuteSparseKernel(_inData, _inStrides, _permutedOutStrides, _rl, _ru,
+ _cnt, _outIndexes, _outValues, _taskID);
+ } else {
+ permuteDenseKernel(_inData, _outData, _inStrides, _permutedOutStrides, _rl, _ru);
}
+ return null;
}
}
- private static void permuteMultiBlockParallel(
- DenseBlock inDB, DenseBlock outDB,
- int[] inDims, long[] inStrides, long[] permutedStrides,
- int k, long totalElements) {
-
- final long elementsPerThread = Math.max(1024, (totalElements + k - 1) / k);
- final int actualThreads = (int) Math.min(k, (totalElements + elementsPerThread - 1) / elementsPerThread);
+ private static void permuteDenseKernel(MatrixBlock inData, MatrixBlock outData,
+ long[] inStrides, long[] permutedOutStrides, int rl, int ru) {
- final ExecutorService pool = CommonThreadPool.get(actualThreads);
- try {
- final ArrayList<PermuteMultiBlockTask> tasks = new ArrayList<>();
-
- for( int t = 0; t < actualThreads; t++ ) {
- final long start = t * elementsPerThread;
- final long end = Math.min(start + elementsPerThread, totalElements);
-
- if( start >= totalElements ) {
- break;
- }
-
- tasks.add(new PermuteMultiBlockTask(inDB, outDB, inDims,
- inStrides, permutedStrides, start, end));
- }
+ final int rank = inStrides.length;
+ final int clen = inData.getNumColumns();
- for( Future<Object> task : pool.invokeAll(tasks) ) {
- task.get();
- }
+ DenseBlock inDB = inData.getDenseBlock();
+ DenseBlock outDB = outData.getDenseBlock();
- } catch (Exception ex) {
- throw new DMLRuntimeException(ex);
- } finally {
- pool.shutdown();
- }
- }
+ // blocking according to typical L2 cache sizes
+ final int blocksizeI = 128;
+ final int blocksizeJ = 128;
- private static class PermuteSingleBlockTask implements Callable<Object> {
- //TODO call single-threaded kernel for block
-
- private final double[] inData;
- private final double[] outData;
- private final int[] inDims;
- private final long[] inStrides;
- private final long[] permutedStrides;
- private final long start;
- private final long end;
-
- protected PermuteSingleBlockTask(double[] inData, double[] outData,
- int[] inDims, long[] inStrides, long[] permutedStrides,
- long start, long end) {
- this.inData = inData;
- this.outData = outData;
- this.inDims = inDims;
- this.inStrides = inStrides;
- this.permutedStrides = permutedStrides;
- this.start = start;
- this.end = end;
- }
-
- @Override
- public Object call() {
- for( long idx = start; idx < end; idx++ ) {
- long inIdx = 0;
- long outIdx = 0;
- long remaining = idx;
-
- for( int d = 0; d < inDims.length; d++ ) {
- long coord = remaining / inStrides[d];
- remaining = remaining % inStrides[d];
- inIdx += coord * inStrides[d];
- outIdx += coord * permutedStrides[d];
+ for( int bi = rl; bi < ru; bi += blocksizeI ) {
+ int bimin = Math.min(bi + blocksizeI, ru);
+ for( int bj = 0; bj < clen; bj += blocksizeJ ) {
+ int bjmin = Math.min(bj + blocksizeJ, clen);
+
+ // core block permute operation
+ for( int i = bi; i < bimin; i++ ) {
+ double[] avals = inDB.values(i);
+ int apos = inDB.pos(i);
+
+ for( int j = bj; j < bjmin; j++ ) {
+ double val = avals[apos + j];
+ if( val == 0 )
+ continue;
+
+ long linearInIdx = (long) i * clen + j;
+ long remaining = linearInIdx;
+ long targetOutIdx = 0;
+
+ for( int d = 0; d < rank; d++ ) {
+ long coord = remaining / inStrides[d];
+ remaining %= inStrides[d];
+ targetOutIdx += coord * permutedOutStrides[d];
+ }
+
+ outDB.set(0, (int) targetOutIdx, val);
+ }
}
-
- outData[(int)outIdx] = inData[(int)inIdx];
}
- return null;
}
}
- private static class PermuteMultiBlockTask implements Callable<Object> {
- //TODO call single-threaded kernel for block
-
- private final DenseBlock inDB;
- private final DenseBlock outDB;
- private final int[] inDims;
- private final long[] inStrides;
- private final long[] permutedStrides;
- private final long start;
- private final long end;
-
- protected PermuteMultiBlockTask(DenseBlock inDB, DenseBlock outDB,
- int[] inDims, long[] inStrides, long[] permutedStrides,
- long start, long end) {
- this.inDB = inDB;
- this.outDB = outDB;
- this.inDims = inDims;
- this.inStrides = inStrides;
- this.permutedStrides = permutedStrides;
- this.start = start;
- this.end = end;
- }
-
- @Override
- public Object call() {
- int inBlockSize = inDB.blockSize();
- int outBlockSize = outDB.blockSize();
-
- for( long idx = start; idx < end; idx++ ) {
- long inIdx = 0;
- long outIdx = 0;
- long remaining = idx;
-
- for( int d = 0; d < inDims.length; d++ ) {
- long coord = remaining / inStrides[d];
- remaining = remaining % inStrides[d];
- inIdx += coord * inStrides[d];
- outIdx += coord * permutedStrides[d];
- }
-
- int inBlockIdx = (int) (inIdx / inBlockSize);
- int inRelIdx = (int) (inIdx % inBlockSize);
-
- int outBlockIdx = (int) (outIdx / outBlockSize);
- int outRelIdx = (int) (outIdx % outBlockSize);
-
- double[] inArr = inDB.valuesAt(inBlockIdx);
- double[] outArr = outDB.valuesAt(outBlockIdx);
-
- if( inArr != null && outArr != null &&
- inRelIdx < inArr.length && outRelIdx < outArr.length ) {
- outArr[outRelIdx] = inArr[inRelIdx];
+ private static void permuteSparseKernel(MatrixBlock inData,
+ long[] inStrides, long[] permutedOutStrides, int rl, int ru,
+ int[] cnt, int[] outIndexes, double[] outValues, int taskID) {
+
+ SparseBlock inSB = inData.getSparseBlock();
+ if( inSB == null ) return;
+
+ final int rank = inStrides.length;
+ final int clen = inData.getNumColumns();
+
+ // blocking according to typical L2 cache sizes with awareness of sparsity
+ final long nnz = inData.getNonZeros();
+ final long xsp = (nnz == 0) ? 1L : ((long) inData.getNumRows() * clen) / nnz;
+ final int blocksizeI = Math.min(Math.max(128, (int) (8 * xsp)), 512);
+
+ // temporary array for block boundaries (for preventing binary search)
+ final int[] ix = new int[Math.min(blocksizeI, ru - rl)];
+
+ // blocked execution
+ for( int bi = rl; bi < ru; bi += blocksizeI ) {
+ Arrays.fill(ix, 0);
+ // find column starting positions
+ int bimin = Math.min(bi + blocksizeI, ru);
+
+ for( int bj = 0; bj < clen; bj += blocksizeI ) {
+ final int bjmin = Math.min(bj + blocksizeI, clen);
+ // core block permute operation
+ for( int i = bi; i < bimin; i++ ) {
+ if( inSB.isEmpty(i) ) continue;
+
+ final int apos = inSB.pos(i);
+ final int alen = inSB.size(i);
+ final int[] aix = inSB.indexes(i);
+ final double[] avals = inSB.values(i);
+ int j = ix[i - bi] + apos; // last block boundary
+ for( ; j < apos + alen && aix[j] < bjmin; j++ ) {
+ long linearInIdx = (long) i * clen + aix[j];
+ long remaining = linearInIdx;
+ long targetOutIdx = 0;
+
+ for( int d = 0; d < rank; d++ ) {
+ long coord = remaining / inStrides[d];
+ remaining %= inStrides[d];
+ targetOutIdx += coord * permutedOutStrides[d];
+ }
+
+ int pointer = cnt[taskID];
+ cnt[taskID]++;
+ outIndexes[pointer] = (int) targetOutIdx;
+ outValues[pointer] = avals[j];
+ }
+ ix[i - bi] = j - apos; // keep block boundary
}
}
- return null;
}
}
}
+
diff --git a/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/PermuteTest.java b/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/PermuteTest.java
index 60810b9228..f6d309426b 100644
--- a/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/PermuteTest.java
+++ b/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/PermuteTest.java
@@ -31,10 +31,10 @@ import java.util.Arrays;
public class PermuteTest {
@Test
- public void testBasicPermute() {
+ public void testBasicPermuteDense() {
int[] shape = {2, 3, 4};
- MatrixBlock tensor = generateMatrixBlock(shape);
-
+ MatrixBlock tensor = generateDenseMatrixBlock(shape);
+
Assert.assertEquals(24, tensor.getNumRows() * tensor.getNumColumns());
double[] data = tensor.getDenseBlockValues();
@@ -51,66 +51,66 @@ public class PermuteTest {
}
@Test
- public void testPermute2DTranspose() {
+ public void testPermute2DTransposeDense() {
int[] shape = {10, 5};
int[] perm = {1, 0};
-
- MatrixBlock in = generateMatrixBlock(shape);
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-
+
verifyPermutation(in, out, shape, perm);
}
@Test
- public void testPermute3DSimple() {
+ public void testPermute3DSimpleDense() {
int[] shape = {2, 3, 4};
int[] perm = {1, 0, 2};
- MatrixBlock in = generateMatrixBlock(shape);
+ MatrixBlock in = generateDenseMatrixBlock(shape);
MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
verifyPermutation(in, out, shape, perm);
}
@Test
- public void testPermute3DIdentity() {
+ public void testPermute3DIdentityDense() {
int[] shape = {5, 5, 5};
int[] perm = {0, 1, 2};
- MatrixBlock in = generateMatrixBlock(shape);
+ MatrixBlock in = generateDenseMatrixBlock(shape);
MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
verifyPermutation(in, out, shape, perm);
}
@Test
- public void testPermute4DReverse() {
+ public void testPermute4DReverseDense() {
int[] shape = {2, 3, 4, 5};
int[] perm = {3, 2, 1, 0};
- MatrixBlock in = generateMatrixBlock(shape);
+ MatrixBlock in = generateDenseMatrixBlock(shape);
MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
verifyPermutation(in, out, shape, perm);
}
@Test
- public void testPermuteHighRank() {
+ public void testPermuteHighRankDense() {
int[] shape = {2, 2, 2, 2, 2, 2};
int[] perm = {5, 0, 4, 1, 3, 2};
- MatrixBlock in = generateMatrixBlock(shape);
+ MatrixBlock in = generateDenseMatrixBlock(shape);
MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
verifyPermutation(in, out, shape, perm);
}
@Test
- public void testLargeBlockLogicMocked() {
+ public void testLargeBlockLogicMockedDense() {
int[] shape = {10, 10, 10};
int[] perm = {2, 0, 1};
- MatrixBlock in = generateMatrixBlock(shape);
+ MatrixBlock in = generateDenseMatrixBlock(shape);
DenseBlock originalDB = in.getDenseBlock();
DenseBlock spyDB = Mockito.spy(originalDB);
Mockito.when(spyDB.numBlocks()).thenReturn(2);
@@ -118,245 +118,688 @@ public class PermuteTest {
MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
- MatrixBlock originalIn = generateMatrixBlock(shape);
- verifyPermutation(originalIn, out, shape, perm);
+ MatrixBlock reference = generateDenseMatrixBlock(shape);
+ verifyPermutation(reference, out, shape, perm);
}
@Test
- public void testLargeBlockLogicMockedInputAndOutput() {
+ public void testLargeBlockLogicMockedInputAndOutputDense() {
int[] shape = {4, 4, 4};
int[] perm = {2, 1, 0};
-
- MatrixBlock in = generateMatrixBlock(shape);
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
DenseBlock spyIn = Mockito.spy(in.getDenseBlock());
Mockito.when(spyIn.numBlocks()).thenReturn(5);
in.setDenseBlock(spyIn);
-
+
MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-
- MatrixBlock originalIn = generateMatrixBlock(shape);
- verifyPermutation(originalIn, out, shape, perm);
+
+ MatrixBlock reference = generateDenseMatrixBlock(shape);
+ verifyPermutation(reference, out, shape, perm);
}
@Test
- public void testPermute3DParallel() {
+ public void testPermute3DParallelDense() {
int[] shape = {100, 100, 100};
int[] perm = {2, 0, 1};
-
- MatrixBlock in = generateMatrixBlock(shape);
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
MatrixBlock out = LibMatrixReorg.permute(in, shape, perm, -1);
-
+
verifyPermutation(in, out, shape, perm);
}
@Test
- @Ignore
- public void testPerformanceSingleVsMultiThreaded() {
- int size = 100;
- int[] shape = {size, size, size};
+ public void testEdgeCaseSingleElementDense() {
+ int[] shape = {1, 1, 1};
+ int[] perm = {2, 1, 0};
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ verifyPermutation(in, out, shape, perm);
+ }
+
+ @Test
+ public void testEdgeCaseOneDimensionOneDense() {
+ int[] shape = {5, 1, 10};
int[] perm = {2, 0, 1};
-
- MatrixBlock in = generateMatrixBlock(shape);
-
- long startSingle = System.nanoTime();
- MatrixBlock outSingle = LibMatrixReorg.permute(in, shape, perm, 1);
- long timeSingle = System.nanoTime() - startSingle;
-
- long startMulti = System.nanoTime();
- MatrixBlock outMulti = LibMatrixReorg.permute(in, shape, perm, -1);
- long timeMulti = System.nanoTime() - startMulti;
-
- verifyPermutation(in, outSingle, shape, perm);
- verifyPermutation(in, outMulti, shape, perm);
-
- System.out.println("Large Matrix (" + size + "x" + size + "x" + size + "):");
- System.out.println("Single-threaded: " + timeSingle / 1_000_000 + " ms");
- System.out.println("Multi-threaded: " + timeMulti / 1_000_000 + " ms");
- System.out.println("Speedup: " + String.format("%.2fx", (double)timeSingle / timeMulti));
- Assert.assertTrue("Multi-threaded should be faster for large matrices", timeMulti < timeSingle);
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ verifyPermutation(in, out, shape, perm);
}
- @SuppressWarnings("unused")
@Test
- @Ignore
- public void testPerformanceLargeMatrixSingleVsMulti() {
- int[] shape = {1, 10000, 10000};
- int[] perm = {0, 2, 1};
-
- MatrixBlock in = generateMatrixBlock(shape);
-
- long startSingle = System.nanoTime();
- MatrixBlock outSingle = LibMatrixReorg.permute(in, shape, perm, 1);
- long timeSingle = System.nanoTime() - startSingle;
-
- long startMulti = System.nanoTime();
- MatrixBlock outMulti = LibMatrixReorg.permute(in, shape, perm, -1);
- long timeMulti = System.nanoTime() - startMulti;
-
- System.out.println("Large Matrix (" + 1 + "x" + 10000 + "x" + 100000 + "):");
- System.out.println("Single-threaded: " + timeSingle / 1_000_000 + " ms");
- System.out.println("Multi-threaded: " + timeMulti / 1_000_000 + " ms");
- System.out.println("Speedup: " + String.format("%.2fx", (double)timeSingle / timeMulti));
-
- Assert.assertTrue("Multi-threaded should be faster for large matrices", timeMulti < timeSingle);
+ public void testEdgeCaseTwoDimensionsOneDense() {
+ int[] shape = {1, 1, 100};
+ int[] perm = {2, 1, 0};
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ verifyPermutation(in, out, shape, perm);
}
- @SuppressWarnings("unused")
@Test
- @Ignore
- public void testPerformancePermuteVsNativeTranspose() {
- int size = 1000;
- MatrixBlock in = new MatrixBlock(size, size, false);
+ public void testConsecutivePermutationsDense() {
+ int[] shape = {3, 4, 5};
+ int[] perm1 = {1, 0, 2};
+ int[] perm2 = {2, 0, 1};
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+ MatrixBlock temp = LibMatrixReorg.permute(in, shape, perm1);
+
+ int[] tempShape = {shape[perm1[0]], shape[perm1[1]], shape[perm1[2]]};
+ MatrixBlock out = LibMatrixReorg.permute(temp, tempShape, perm2);
+
+ verifyPermutation(temp, out, tempShape, perm2);
+ }
+
+ @Test
+ public void testDifferentThreadCountsDense() {
+ int[] shape = {50, 50, 50};
+ int[] perm = {2, 0, 1};
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+
+ MatrixBlock out1 = LibMatrixReorg.permute(in, shape, perm, 1);
+ MatrixBlock out2 = LibMatrixReorg.permute(in, shape, perm, 2);
+ MatrixBlock out4 = LibMatrixReorg.permute(in, shape, perm, 4);
+ MatrixBlock out8 = LibMatrixReorg.permute(in, shape, perm, 8);
+
+ double[] data1 = out1.getDenseBlockValues();
+ double[] data2 = out2.getDenseBlockValues();
+ double[] data4 = out4.getDenseBlockValues();
+ double[] data8 = out8.getDenseBlockValues();
+
+ for (int i = 0; i < data1.length; i++) {
+ Assert.assertEquals(data1[i], data2[i], 0.0001);
+ Assert.assertEquals(data1[i], data4[i], 0.0001);
+ Assert.assertEquals(data1[i], data8[i], 0.0001);
+ }
+ }
+
+ @Test
+ public void testThreadCountExceedsElementCountDense() {
+ int[] shape = {2, 2};
+ int[] perm = {1, 0};
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+
+ MatrixBlock out1 = LibMatrixReorg.permute(in, shape, perm, 1);
+ MatrixBlock out16 = LibMatrixReorg.permute(in, shape, perm, 16);
+
+ verifyPermutation(in, out16, shape, perm);
+ double[] data1 = out1.getDenseBlockValues();
+ double[] data16 = out16.getDenseBlockValues();
+ for (int i = 0; i < data1.length; i++)
+ Assert.assertEquals(data1[i], data16[i], 0.0001);
+ }
+
+ @Test
+ public void testPermuteAllDimensionsCyclicDense() {
+ int[] shape = {3, 4, 5, 2};
+ int[] perm = {1, 2, 3, 0};
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ verifyPermutation(in, out, shape, perm);
+ }
+
+ @Test
+ public void testPermuteNonContiguousStridesDense() {
+ int[] shape = {7, 11, 13};
+ int[] perm = {2, 0, 1};
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ verifyPermutation(in, out, shape, perm);
+ }
+
+ @Test
+ public void testPermuteLargePrimeStridesDense() {
+ int[] shape = {17, 19};
+ int[] perm = {1, 0};
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ verifyPermutation(in, out, shape, perm);
+ }
+
+ @Test
+ public void testSpecialFloatingPointValuesDense() {
+ int[] shape = {2, 2};
+ int[] perm = {1, 0};
+
+ MatrixBlock in = new MatrixBlock(1, 4, false);
in.allocateDenseBlock();
double[] data = in.getDenseBlockValues();
- for (int i = 0; i < size; i++) {
- for (int j = 0; j < size; j++) {
- data[i * size + j] = i * size + j;
- }
+ data[0] = Double.NaN;
+ data[1] = Double.POSITIVE_INFINITY;
+ data[2] = Double.NEGATIVE_INFINITY;
+ data[3] = 0.0;
+
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+ double[] outData = out.getDenseBlockValues();
+
+ int nanCount = 0, posInfCount = 0, negInfCount = 0;
+ for (double v : outData) {
+ if (Double.isNaN(v)) nanCount++;
+ else if (v == Double.POSITIVE_INFINITY) posInfCount++;
+ else if (v == Double.NEGATIVE_INFINITY) negInfCount++;
}
-
- int[] shape = {size, size};
+ Assert.assertEquals(1, nanCount);
+ Assert.assertEquals(1, posInfCount);
+ Assert.assertEquals(1, negInfCount);
+ }
+
+ @Test
+ public void testInputImmutableAfterPermuteDense() {
+ int[] shape = {4, 5, 6};
+ int[] perm = {2, 0, 1};
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+ double[] before = in.getDenseBlockValues().clone();
+
+ LibMatrixReorg.permute(in, shape, perm);
+
+ double[] after = in.getDenseBlockValues();
+ Assert.assertArrayEquals(before, after, 0.0001);
+ }
+
+ @Test
+ public void testBasicPermuteSparse() {
+ int[] shape = {2, 3, 4};
+ int[] perm = {1, 0, 2};
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ verifyPermutation(in, out, shape, perm);
+ }
+
+ @Test
+ public void testPermute2DTransposeSparse() {
+ int[] shape = {10, 5};
int[] perm = {1, 0};
-
- long startPermute = System.nanoTime();
- MatrixBlock outPermute = LibMatrixReorg.permute(in, shape, perm, -1);
- long timePermute = System.nanoTime() - startPermute;
-
- long startTranspose = System.nanoTime();
- MatrixBlock outTranspose = LibMatrixReorg.transpose(in);
- long timeTranspose = System.nanoTime() - startTranspose;
-
- System.out.println("Transpose Performance (" + size + "x" + size + "):");
- System.out.println("Permute function: " + timePermute / 1_000_000 + " ms");
- System.out.println("Native transpose: " + timeTranspose / 1_000_000 + " ms");
- System.out.println("Ratio: " + String.format("%.2fx", (double)timePermute / timeTranspose));
-
- double[] permuteData = outPermute.getDenseBlockValues();
-
- for (int i = 0; i < size; i++) {
- for (int j = 0; j < size; j++) {
- double expected = in.get(j, i);
- double actual = permuteData[i * size + j];
- Assert.assertEquals("Mismatch at (" + i + "," + j + ")", expected, actual, 0.0001);
- }
- }
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ verifyPermutation(in, out, shape, perm);
+ }
+
+ @Test
+ public void testPermute3DSimpleSparse() {
+ int[] shape = {2, 3, 4};
+ int[] perm = {1, 0, 2};
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ verifyPermutation(in, out, shape, perm);
+ }
+
+ @Test
+ public void testPermute3DIdentitySparse() {
+ int[] shape = {5, 5, 5};
+ int[] perm = {0, 1, 2};
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ verifyPermutation(in, out, shape, perm);
+ }
+
+ @Test
+ public void testPermute4DReverseSparse() {
+ int[] shape = {2, 3, 4, 5};
+ int[] perm = {3, 2, 1, 0};
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ verifyPermutation(in, out, shape, perm);
+ }
+
+ @Test
+ public void testPermuteHighRankSparse() {
+ int[] shape = {2, 2, 2, 2, 2, 2};
+ int[] perm = {5, 0, 4, 1, 3, 2};
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ verifyPermutation(in, out, shape, perm);
}
@Test
- public void testEdgeCaseSingleElement() {
+ public void testPermute3DParallelSparse() {
+ int[] shape = {100, 100, 100};
+ int[] perm = {2, 0, 1};
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.1);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm, -1);
+
+ verifyPermutation(in, out, shape, perm);
+ }
+
+ @Test
+ public void testEdgeCaseEmptySparse() {
+ int[] shape = {5, 5, 5};
+ int[] perm = {1, 0, 2};
+
+ MatrixBlock in = new MatrixBlock(1, 125, true);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ Assert.assertTrue(out.isEmpty());
+ Assert.assertEquals(125, out.getNumColumns());
+ }
+
+ @Test
+ public void testEdgeCaseSingleElementSparse() {
int[] shape = {1, 1, 1};
int[] perm = {2, 1, 0};
-
- MatrixBlock in = generateMatrixBlock(shape);
+
+ MatrixBlock in = new MatrixBlock(1, 1, true);
+ in.allocateSparseRowsBlock();
+ in.appendValue(0, 0, 42.0);
+ in.recomputeNonZeros();
MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-
+
verifyPermutation(in, out, shape, perm);
}
@Test
- public void testEdgeCaseOneDimensionOne() {
+ public void testEdgeCaseOneDimensionOneSparse() {
int[] shape = {5, 1, 10};
int[] perm = {2, 0, 1};
-
- MatrixBlock in = generateMatrixBlock(shape);
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-
+
verifyPermutation(in, out, shape, perm);
}
@Test
- public void testEdgeCaseTwoDimensionsOne() {
+ public void testEdgeCaseTwoDimensionsOneSparse() {
int[] shape = {1, 1, 100};
int[] perm = {2, 1, 0};
-
- MatrixBlock in = generateMatrixBlock(shape);
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-
+
verifyPermutation(in, out, shape, perm);
}
- @SuppressWarnings("unused")
@Test
- public void testConsecutivePermutations() {
+ public void testConsecutivePermutationsSparse() {
int[] shape = {3, 4, 5};
int[] perm1 = {1, 0, 2};
int[] perm2 = {2, 0, 1};
-
- MatrixBlock in = generateMatrixBlock(shape);
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
MatrixBlock temp = LibMatrixReorg.permute(in, shape, perm1);
-
+
int[] tempShape = {shape[perm1[0]], shape[perm1[1]], shape[perm1[2]]};
MatrixBlock out = LibMatrixReorg.permute(temp, tempShape, perm2);
-
- int[] finalShape = {tempShape[perm2[0]], tempShape[perm2[1]], tempShape[perm2[2]]};
-
+
verifyPermutation(temp, out, tempShape, perm2);
}
@Test
- public void testDifferentThreadCounts() {
+ public void testDifferentThreadCountsSparse() {
int[] shape = {50, 50, 50};
int[] perm = {2, 0, 1};
-
- MatrixBlock in = generateMatrixBlock(shape);
-
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.1);
+
MatrixBlock out1 = LibMatrixReorg.permute(in, shape, perm, 1);
MatrixBlock out2 = LibMatrixReorg.permute(in, shape, perm, 2);
MatrixBlock out4 = LibMatrixReorg.permute(in, shape, perm, 4);
MatrixBlock out8 = LibMatrixReorg.permute(in, shape, perm, 8);
-
- double[] data1 = out1.getDenseBlockValues();
- double[] data2 = out2.getDenseBlockValues();
- double[] data4 = out4.getDenseBlockValues();
- double[] data8 = out8.getDenseBlockValues();
-
- for (int i = 0; i < data1.length; i++) {
- Assert.assertEquals(data1[i], data2[i], 0.0001);
- Assert.assertEquals(data1[i], data4[i], 0.0001);
- Assert.assertEquals(data1[i], data8[i], 0.0001);
+
+ long len = totalLength(shape);
+ for (int i = 0; i < len; i++) {
+ double v1 = out1.get(0, i);
+ Assert.assertEquals(v1, out2.get(0, i), 0.0001);
+ Assert.assertEquals(v1, out4.get(0, i), 0.0001);
+ Assert.assertEquals(v1, out8.get(0, i), 0.0001);
}
}
@Test
- public void testPermuteAllDimensionsCyclic() {
+ public void testThreadCountExceedsElementCountSparse() {
+ int[] shape = {2, 2};
+ int[] perm = {1, 0};
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.5);
+
+ MatrixBlock out1 = LibMatrixReorg.permute(in, shape, perm, 1);
+ MatrixBlock out16 = LibMatrixReorg.permute(in, shape, perm, 16);
+
+ verifyPermutation(in, out16, shape, perm);
+ long len = totalLength(shape);
+ for (int i = 0; i < len; i++)
+ Assert.assertEquals(out1.get(0, i), out16.get(0, i), 0.0001);
+ }
+
+ @Test
+ public void testPermuteAllDimensionsCyclicSparse() {
int[] shape = {3, 4, 5, 2};
int[] perm = {1, 2, 3, 0};
-
- MatrixBlock in = generateMatrixBlock(shape);
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-
+
verifyPermutation(in, out, shape, perm);
}
@Test
- public void testPermuteNonContiguousStrides() {
+ public void testPermuteNonContiguousStridesSparse() {
int[] shape = {7, 11, 13};
int[] perm = {2, 0, 1};
-
- MatrixBlock in = generateMatrixBlock(shape);
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-
+
verifyPermutation(in, out, shape, perm);
}
@Test
- public void testPermuteLargePrimeStrides() {
+ public void testPermuteLargePrimeStridesSparse() {
int[] shape = {17, 19};
int[] perm = {1, 0};
-
- MatrixBlock in = generateMatrixBlock(shape);
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-
+
verifyPermutation(in, out, shape, perm);
}
- private MatrixBlock generateMatrixBlock(int[] shape) {
+ @Test
+ public void testSpecialFloatingPointValuesSparse() {
+ int[] shape = {2, 2};
+ int[] perm = {1, 0};
+
+ MatrixBlock in = new MatrixBlock(1, 4, true);
+ in.allocateSparseRowsBlock();
+ in.appendValue(0, 0, Double.NaN);
+ in.appendValue(0, 1, Double.POSITIVE_INFINITY);
+ in.appendValue(0, 2, Double.NEGATIVE_INFINITY);
+ in.recomputeNonZeros();
+
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ int nanCount = 0, posInfCount = 0, negInfCount = 0;
+ for (int i = 0; i < 4; i++) {
+ double v = out.get(0, i);
+ if (Double.isNaN(v)) nanCount++;
+ else if (v == Double.POSITIVE_INFINITY) posInfCount++;
+ else if (v == Double.NEGATIVE_INFINITY) negInfCount++;
+ }
+ Assert.assertEquals(1, nanCount);
+ Assert.assertEquals(1, posInfCount);
+ Assert.assertEquals(1, negInfCount);
+ }
+
+ @Test
+ public void testInputImmutableAfterPermuteSparse() {
+ int[] shape = {4, 5, 6};
+ int[] perm = {2, 0, 1};
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+ long len = totalLength(shape);
+ double[] before = new double[(int) len];
+ for (int i = 0; i < len; i++)
+ before[i] = in.get(0, i);
+
+ LibMatrixReorg.permute(in, shape, perm);
+
+ for (int i = 0; i < len; i++)
+ Assert.assertEquals(before[i], in.get(0, i), 0.0001);
+ }
+
+ @Test
+ public void testLargeSparseManyRowsConsistency() {
+ int[] shape = {10, 10, 10};
+ int[] perm = {2, 0, 1};
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.3);
+
+ MatrixBlock outSingle = LibMatrixReorg.permute(in, shape, perm, 1);
+ MatrixBlock outMulti = LibMatrixReorg.permute(in, shape, perm, -1);
+
+ verifyPermutation(in, outSingle, shape, perm);
+ long len = totalLength(shape);
+ for (int i = 0; i < len; i++)
+ Assert.assertEquals(outSingle.get(0, i), outMulti.get(0, i), 0.0001);
+ }
+
+ @Test
+ public void testNonZeroCountPreservedAfterPermuteSparse() {
+ int[] shape = {6, 7, 8};
+ int[] perm = {2, 0, 1};
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.25);
+ long nnzBefore = in.getNonZeros();
+
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+ out.recomputeNonZeros();
+
+ Assert.assertEquals(nnzBefore, out.getNonZeros());
+ Assert.assertEquals(nnzBefore == 0, out.isEmpty());
+ }
+
+ @Test
+ public void testDenseSparseParitySmall() {
+ int[] shape = {4, 3, 5};
+ int[] perm = {2, 0, 1};
+
+ MatrixBlock dense = generateDenseMatrixBlock(shape);
+ MatrixBlock sparse = denseToSparse(dense);
+
+ MatrixBlock outDense = LibMatrixReorg.permute(dense, shape, perm);
+ MatrixBlock outSparse = LibMatrixReorg.permute(sparse, shape, perm);
+
+ long len = totalLength(shape);
+ for (int i = 0; i < len; i++) {
+ Assert.assertEquals(outDense.get(0, i), outSparse.get(0, i), 0.0001);
+ }
+ }
+
+ @Test
+ public void testDenseSparseParityHighRank() {
+ int[] shape = {2, 3, 4, 5};
+ int[] perm = {3, 1, 0, 2};
+
+ MatrixBlock dense = generateDenseMatrixBlock(shape);
+ MatrixBlock sparse = denseToSparse(dense);
+
+ MatrixBlock outDense = LibMatrixReorg.permute(dense, shape, perm);
+ MatrixBlock outSparse = LibMatrixReorg.permute(sparse, shape, perm);
+
+ long len = totalLength(shape);
+ for (int i = 0; i < len; i++) {
+ Assert.assertEquals(outDense.get(0, i), outSparse.get(0, i), 0.0001);
+ }
+ }
+
+ @Test
+ public void testInvalidPermutationDuplicateIndicesDense() {
+ int[] shape = {2, 3, 4};
+ int[] perm = {0, 0, 2};
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+ try {
+ LibMatrixReorg.permute(in, shape, perm);
+ Assert.fail("Expected an exception for duplicate indices");
+ } catch (Exception expected) {
+ }
+ }
+
+ @Test
+ public void testInvalidPermutationOutOfRangeIndexDense() {
+ int[] shape = {2, 3, 4};
+ int[] perm = {0, 1, 5};
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+ try {
+ LibMatrixReorg.permute(in, shape, perm);
+ Assert.fail("Expected an exception for an out-of-range permutation index");
+ } catch (Exception expected) {
+ }
+ }
+
+ @Test
+ public void testInvalidPermutationWrongLengthDense() {
+ int[] shape = {2, 3, 4};
+ int[] perm = {1, 0};
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+ try {
+ LibMatrixReorg.permute(in, shape, perm);
+ Assert.fail("Expected an exception for a permutation array of the wrong length");
+ } catch (Exception expected) {
+ }
+ }
+
+ @Test
+ public void testInvalidShapeDataLengthMismatchDense() {
+ int[] shape = {3, 3, 3};
+ int[] perm = {1, 0, 2};
+ MatrixBlock in = generateDenseMatrixBlock(new int[]{2, 2, 2});
+ try {
+ LibMatrixReorg.permute(in, shape, perm);
+ Assert.fail("Expected an exception when shape does not match input data length");
+ } catch (Exception expected) {
+ }
+ }
+
+ @Test
+ public void testInvalidPermutationDuplicateIndicesSparse() {
+ int[] shape = {2, 3, 4};
+ int[] perm = {0, 0, 2};
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+ try {
+ LibMatrixReorg.permute(in, shape, perm);
+ Assert.fail("Expected an exception for duplicate indices");
+ } catch (Exception expected) {
+ }
+ }
+
+ @Test
+ public void testSparseFormatPreservedAfterPermute() {
+ int[] shape = {6, 7, 8};
+ int[] perm = {2, 0, 1};
+
+ MatrixBlock in = generateSparseMatrixBlock(shape, 0.05);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ Assert.assertTrue("Sparse input must produce a sparse output", out.isInSparseFormat());
+ }
+
+ @Test
+ public void testDenseFormatPreservedAfterPermute() {
+ int[] shape = {6, 7, 8};
+ int[] perm = {2, 0, 1};
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+ MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+ Assert.assertFalse("Dense input must produce a dense output", out.isInSparseFormat());
+ }
+
+ /*
+ This Test takes relatively long.
+ The smaller sparse tests are relatively unstable, sometimes showing some speedup, sometimes not.
+ The larg test however, always shows some speedup but in the range between 1.01 and 10.4.
+ */
+ @Test
+ @Ignore
+ public void testPerformanceBenchmarkDenseAndSparse() {
+ int size = 100;
+ int[] shape = {size, size, size};
+ int[] perm = {2, 0, 1};
+
+ System.out.println("--- Benchmark Results (Size " + size + "^3) ---");
+
+ MatrixBlock denseIn = generateDenseMatrixBlock(shape);
+ double dSingle = benchmarkPermute(denseIn, shape, perm, 1);
+ double dMulti = benchmarkPermute(denseIn, shape, perm, -1);
+ printBenchmarkResult("Dense", dSingle, dMulti);
+
+ MatrixBlock sparseIn10 = generateSparseMatrixBlock(shape, 0.1);
+ double s10Single = benchmarkPermute(sparseIn10, shape, perm, 1);
+ double s10Multi = benchmarkPermute(sparseIn10, shape, perm, -1);
+ printBenchmarkResult("Sparse (0.1)", s10Single, s10Multi);
+
+ MatrixBlock sparseIn50 = generateSparseMatrixBlock(shape, 0.5);
+ double s50Single = benchmarkPermute(sparseIn50, shape, perm, 1);
+ double s50Multi = benchmarkPermute(sparseIn50, shape, perm, -1);
+ printBenchmarkResult("Sparse (0.5)", s50Single, s50Multi);
+
+ MatrixBlock sparseLarge = generateSparseMatrixBlock(new int[]{100, 1000, 1000}, 0.5);
+ double sLargeSingle = benchmarkPermute(sparseLarge, new int[]{100, 1000, 1000}, new int[]{2, 0, 1}, 1);
+ double sLargeMulti = benchmarkPermute(sparseLarge, new int[]{100, 1000, 1000}, new int[]{2, 0, 1}, -1);
+ printBenchmarkResult("Sparse Large (0.5)", sLargeSingle, sLargeMulti);
+
+ Assert.assertTrue(dMulti < dSingle * 2.0);
+ }
+
+ @Test
+ @Ignore // Unstable on my device
+ public void testPerformanceSingleVsMultiThreadedDense() {
+ int size = 100;
+ int[] shape = {size, size, size};
+ int[] perm = {2, 0, 1};
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+
+ MatrixBlock outSingle = LibMatrixReorg.permute(in, shape, perm, 1);
+ MatrixBlock outMulti = LibMatrixReorg.permute(in, shape, perm, -1);
+ verifyPermutation(in, outSingle, shape, perm);
+ verifyPermutation(in, outMulti, shape, perm);
+
+ double timeSingle = benchmarkPermute(in, shape, perm, 1);
+ double timeMulti = benchmarkPermute(in, shape, perm, -1);
+
+ System.out.println("Large Matrix (" + size + "x" + size + "x" + size + "):");
+ System.out.printf("Single-threaded (avg): %.2f ms%n", timeSingle);
+ System.out.printf("Multi-threaded (avg): %.2f ms%n", timeMulti);
+ System.out.printf("Speedup: %.2fx%n", timeSingle / timeMulti);
+
+ Assert.assertTrue("Multi-threaded should be faster for large matrices", timeMulti < timeSingle);
+ }
+
+ @Test // Shows a stable speedup of ~2,20
+ @Ignore
+ public void testPerformanceLargeMatrixSingleVsMultiDense() {
+ int[] shape = {10, 1000, 1000};
+ int[] perm = {0, 2, 1};
+
+ MatrixBlock in = generateDenseMatrixBlock(shape);
+
+ double timeSingle = benchmarkPermute(in, shape, perm, 1);
+ double timeMulti = benchmarkPermute(in, shape, perm, -1);
+
+ System.out.println("Large Matrix (10x1000x1000):");
+ System.out.printf("Single-threaded (avg): %.2f ms%n", timeSingle);
+ System.out.printf("Multi-threaded (avg): %.2f ms%n", timeMulti);
+ System.out.printf("Speedup: %.2fx%n", timeSingle / timeMulti);
+
+ Assert.assertTrue("Multi-threaded should be faster for large matrices", timeMulti < timeSingle);
+ }
+
+ private MatrixBlock generateDenseMatrixBlock(int[] shape) {
long len = 1;
for (int d : shape) len *= d;
-
- MatrixBlock mb = new MatrixBlock(1, (int)len, false);
+
+ int rows = shape[0];
+ int cols = (int) (len / rows);
+
+ MatrixBlock mb = new MatrixBlock(rows, cols, false);
mb.allocateDenseBlock();
+
double[] data = mb.getDenseBlockValues();
for (int i = 0; i < data.length; i++) {
data[i] = (double) i;
@@ -364,65 +807,83 @@ public class PermuteTest {
return mb;
}
- private void verifyPermutation(MatrixBlock in, MatrixBlock out, int[] inShape, int[] perm) {
- double[] inData = new double[(int)(in.getNumRows() * in.getNumColumns())];
- double[] outData = new double[(int)(out.getNumRows() * out.getNumColumns())];
-
- DenseBlock inDB = in.getDenseBlock();
- DenseBlock outDB = out.getDenseBlock();
+ private MatrixBlock generateSparseMatrixBlock(int[] shape, double sparsity) {
+ long len = 1;
+ for (int d : shape) len *= d;
+
+ int rows = shape[0];
+ int cols = (int) (len / rows);
+
+ MatrixBlock mb = new MatrixBlock(rows, cols, true);
+ mb.allocateSparseRowsBlock();
- if (inDB != null) {
- int inBlockSize = inDB.blockSize();
- for (int i = 0; i < inDB.numBlocks(); i++) {
- double[] block = inDB.valuesAt(i);
- int offset = i * inBlockSize;
- int len = Math.min(inBlockSize, inData.length - offset);
- System.arraycopy(block, 0, inData, offset, len);
+ for (long i = 0; i < len; i++) {
+ if ((i * 0.12345) % 1.0 < sparsity) {
+ int r = (int) (i / cols);
+ int c = (int) (i % cols);
+ mb.appendValue(r, c, (double) i);
}
}
+ mb.recomputeNonZeros();
+ return mb;
+ }
+
+ private MatrixBlock denseToSparse(MatrixBlock dense) {
+ int rows = dense.getNumRows();
+ int cols = dense.getNumColumns();
+
+ MatrixBlock sparse = new MatrixBlock(rows, cols, true);
+ sparse.allocateSparseRowsBlock();
- if (outDB != null) {
- int outBlockSize = outDB.blockSize();
- for (int i = 0; i < outDB.numBlocks(); i++) {
- double[] block = outDB.valuesAt(i);
- int offset = i * outBlockSize;
- int len = Math.min(outBlockSize, outData.length - offset);
- System.arraycopy(block, 0, outData, offset, len);
+ for (int r = 0; r < rows; r++) {
+ for (int c = 0; c < cols; c++) {
+ double val = dense.get(r, c);
+ if (val != 0) {
+ sparse.appendValue(r, c, val);
+ }
}
}
-
+ sparse.recomputeNonZeros();
+ return sparse;
+ }
+
+ private void verifyPermutation(MatrixBlock in, MatrixBlock out, int[] inShape, int[] perm) {
int rank = inShape.length;
int[] outShape = new int[rank];
- for (int i = 0; i < rank; i++)
+ for (int i = 0; i < rank; i++)
outShape[i] = inShape[perm[i]];
long[] outStrides = getStrides(outShape);
long[] inStrides = getStrides(inShape);
-
+
long len = 1;
for (int d : outShape) len *= d;
for (long i = 0; i < len; i++) {
int[] outCoords = new int[rank];
- long temp = i;
+ long remaining = i;
for (int d = 0; d < rank; d++) {
- outCoords[d] = (int)(temp / outStrides[d]);
- temp = temp % outStrides[d];
+ outCoords[d] = (int) (remaining / outStrides[d]);
+ remaining %= outStrides[d];
}
int[] inCoords = new int[rank];
- for (int d = 0; d < rank; d++) {
+ for (int d = 0; d < rank; d++){
inCoords[perm[d]] = outCoords[d];
}
-
+
long inIndex = 0;
- for (int d = 0; d < rank; d++) {
+ for (int d = 0; d < rank; d++){
inIndex += inCoords[d] * inStrides[d];
}
+
+ int inCols = in.getNumColumns();
+ int r = (int) (inIndex / inCols);
+ int c = (int) (inIndex % inCols);
- double expectedValue = inData[(int)inIndex];
- double actualValue = outData[(int)i];
-
+ double expectedValue = in.get(r, c);
+ double actualValue = out.get(0, (int)i);
+
if (Math.abs(expectedValue - actualValue) > 0.0001) {
Assert.fail("Mismatch at linear output index " + i +
". Output coords " + Arrays.toString(outCoords) +
@@ -441,4 +902,30 @@ public class PermuteTest {
}
return strides;
}
-}
\ No newline at end of file
+
+ private long totalLength(int[] shape) {
+ long len = 1;
+ for (int d : shape) len *= d;
+ return len;
+ }
+
+ private double benchmarkPermute(MatrixBlock in, int[] shape, int[] perm, int k) {
+ double checksum = 0;
+ for (int i = 0; i < 5; i++)
+ checksum += LibMatrixReorg.permute(in, shape, perm, k).get(0, 0);
+
+ long start = System.nanoTime();
+ for (int i = 0; i < 10; i++)
+ checksum += LibMatrixReorg.permute(in, shape, perm, k).get(0, 0);
+ long elapsed = System.nanoTime() - start;
+
+ if (checksum == Double.NaN)
+ System.out.println("unreachable");
+ return (double) elapsed / 1_000_000.0 / 10.0;
+ }
+
+ private void printBenchmarkResult(String label, double single, double multi) {
+ System.out.printf("%-20s Single: %6.2fms Multi: %6.2fms Speedup: %.2fx%n",
+ label, single, multi, single / multi);
+ }
+}