This is an automated email from the ASF dual-hosted git repository. baunsgaard 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 dd7bfe6cb1 [SYSTEMDS-3718] Improve reshaping of Sparse MatrixBlock dd7bfe6cb1 is described below commit dd7bfe6cb1a025a2903994e43066632a3eb37d44 Author: Sebastian Baunsgaard <baunsga...@apache.org> AuthorDate: Wed Aug 14 12:11:44 2024 +0200 [SYSTEMDS-3718] Improve reshaping of Sparse MatrixBlock This commit adds minor refinements to some of the reshaping instructions Mainly for the MCSR to MCSR case where for instance 1/3 on 10k by 10k matrices of 0.1 sparsity improve by 1/3. While CSR to CSR improve by 5-15%. See the PR for performance details Closes #2064 --- .../instructions/cp/ReshapeCPInstruction.java | 2 +- .../sysds/runtime/matrix/data/LibMatrixReorg.java | 441 +++++++++++++------ .../java/org/apache/sysds/performance/Main.java | 4 + .../java/org/apache/sysds/performance/README.md | 6 + .../sysds/performance/matrix/ReshapePerf.java | 86 ++++ src/test/java/org/apache/sysds/test/TestUtils.java | 21 +- .../matrix/libMatrixReorg/ReshapeTest.java | 476 +++++++++++++++++++++ .../{ => libMatrixReorg}/TransposeCSRTest.java | 2 +- .../{ => libMatrixReorg}/TransposeInplaceTest.java | 2 +- .../{ => libMatrixReorg}/TransposeTwiceTest.java | 2 +- 10 files changed, 882 insertions(+), 160 deletions(-) diff --git a/src/main/java/org/apache/sysds/runtime/instructions/cp/ReshapeCPInstruction.java b/src/main/java/org/apache/sysds/runtime/instructions/cp/ReshapeCPInstruction.java index 9cf30acb37..96fcc20a3f 100644 --- a/src/main/java/org/apache/sysds/runtime/instructions/cp/ReshapeCPInstruction.java +++ b/src/main/java/org/apache/sysds/runtime/instructions/cp/ReshapeCPInstruction.java @@ -100,7 +100,7 @@ public class ReshapeCPInstruction extends UnaryCPInstruction { //execute operations MatrixBlock out = new MatrixBlock(); - LibMatrixReorg.reshape(in, out, rows, cols, byRow.getBooleanValue()); + LibMatrixReorg.reshape(in, out, rows, cols, byRow.getBooleanValue(), -1); //set output and release inputs ec.releaseMatrixInput(input1.getName()); 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 1ebd73da4d..17a3ae1a4f 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 @@ -41,6 +41,7 @@ import org.apache.sysds.runtime.DMLRuntimeException; import org.apache.sysds.runtime.compress.CompressedMatrixBlock; import org.apache.sysds.runtime.compress.DMLCompressionException; import org.apache.sysds.runtime.controlprogram.caching.MatrixObject.UpdateType; +import org.apache.sysds.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer; import org.apache.sysds.runtime.data.DenseBlock; import org.apache.sysds.runtime.data.DenseBlockFactory; import org.apache.sysds.runtime.data.SparseBlock; @@ -282,16 +283,23 @@ public class LibMatrixReorg { for(int i = 0; i < k & i * blklen < len; i++) tasks.add(new TransposeTask(in, out, row, i * blklen, Math.min((i + 1) * blklen, len), cnt, allowReturnBlock)); - List<MatrixBlock> blocks = allowReturnBlock ? new ArrayList<>(): null; - // List<Future<Object>> taskret = pool.invokeAll(tasks); - for(Future<MatrixBlock> task : pool.invokeAll(tasks)){ - MatrixBlock m = task.get(); - if(allowReturnBlock && m != null) - blocks.add(m); - } + + if(allowReturnBlock) { + List<MatrixBlock> blocks = new ArrayList<>(); + for(Future<MatrixBlock> task : pool.invokeAll(tasks)) { + MatrixBlock m = task.get(); + if(allowReturnBlock && m != null) + blocks.add(m); + } - if(allowReturnBlock) - combine(blocks, out, row, k); + if(allowReturnBlock) + combine(blocks, out, row, k); + } + else { + for(Future<MatrixBlock> task : pool.invokeAll(tasks)) { + task.get(); + } + } } catch(Exception ex) { throw new DMLRuntimeException(ex); @@ -548,13 +556,22 @@ public class LibMatrixReorg { if( !ixret ) { out.allocateBlock(); //copy input data in sorted order into result - ExecutorService pool = CommonThreadPool.get(k); - ArrayList<CopyTask> tasks = new ArrayList<>(); - ArrayList<Integer> blklen = UtilFunctions + if(k > 1){ + + ExecutorService pool = CommonThreadPool.get(k); + ArrayList<CopyTask> tasks = new ArrayList<>(); + ArrayList<Integer> blklen = UtilFunctions + .getBalancedBlockSizesDefault(rlen, k, false); + for( int i=0, lb=0; i<blklen.size(); lb+=blklen.get(i), i++ ) + tasks.add( new CopyTask(in, out, vix, lb, lb+blklen.get(i))); + CommonThreadPool.invokeAndShutdown(pool, tasks); + } + else{ + ArrayList<Integer> blklen = UtilFunctions .getBalancedBlockSizesDefault(rlen, k, false); - for( int i=0, lb=0; i<blklen.size(); lb+=blklen.get(i), i++ ) - tasks.add( new CopyTask(in, out, vix, lb, lb+blklen.get(i))); - CommonThreadPool.invokeAndShutdown(pool, tasks); + for( int i=0, lb=0; i<blklen.size(); lb+=blklen.get(i), i++ ) + new CopyTask(in, out, vix, lb, lb+blklen.get(i)).call(); + } } else { //copy sorted index vector into result @@ -568,57 +585,101 @@ public class LibMatrixReorg { } /** - * CP reshape operation (single input, single output matrix) + * CP reshape operation (single input, single output matrix) * - * NOTE: In contrast to R, the rowwise parameter specifies both - * the read and write order, with row-wise being the default, while - * R uses always a column-wise read, rowwise specifying the write - * order and column-wise being the default. + * NOTE: In contrast to R, the rowwise parameter specifies both the read and write order, with row-wise being the + * default, while R uses always a column-wise read, rowwise specifying the write order and column-wise being the + * default. * - * @param in input matrix - * @param out output matrix - * @param rows number of rows - * @param cols number of columns + * @param in input matrix + * @param rows number of rows + * @param cols number of columns * @param rowwise if true, reshape by row * @return output matrix */ - public static MatrixBlock reshape( MatrixBlock in, MatrixBlock out, int rows, int cols, boolean rowwise ) { - int rlen = in.rlen; - int clen = in.clen; - - //check validity - if( ((long)rlen)*clen != ((long)rows)*cols ) - throw new DMLRuntimeException("Reshape matrix requires consistent numbers of input/output cells ("+rlen+":"+clen+", "+rows+":"+cols+")."); + public static MatrixBlock reshape(MatrixBlock in, int rows, int cols, boolean rowwise) { + return reshape(in, null, rows,cols, rowwise, 1); + } + + /** + * CP reshape operation (single input, single output matrix) + * + * NOTE: In contrast to R, the rowwise parameter specifies both the read and write order, with row-wise being the + * default, while R uses always a column-wise read, rowwise specifying the write order and column-wise being the + * default. + * + * @param in input matrix + * @param out output matrix + * @param rows number of rows + * @param cols number of columns + * @param rowwise if true, reshape by row + * @return output matrix + */ + public static MatrixBlock reshape(MatrixBlock in, MatrixBlock out, int rows, int cols, boolean rowwise) { + return reshape(in, out, rows,cols, rowwise, 1); + } + + /** + * CP reshape operation (single input, single output matrix) + * + * NOTE: In contrast to R, the rowwise parameter specifies both the read and write order, with row-wise being the + * default, while R uses always a column-wise read, rowwise specifying the write order and column-wise being the + * default. + * + * @param in input matrix + * @param out output matrix + * @param rows number of rows + * @param cols number of columns + * @param rowwise if true, reshape by row + * @param k The parallelization degree + * @return output matrix + */ + public static MatrixBlock reshape(MatrixBlock in, MatrixBlock out, int rows, int cols, boolean rowwise, int k) { + try{ + final int rlen = in.rlen; + final int clen = in.clen; + + if(out == null) + out = new MatrixBlock(); + + //check for same dimensions + if(rlen == rows && clen == cols) { + // copy incl dims, nnz + if(SHALLOW_COPY_REORG) + out.copyShallow(in); + else + out.copy(in); + return out; + } + + //check validity + if(((long) rlen) * clen != ((long) rows) * cols) + throw new DMLRuntimeException("Reshape matrix requires consistent numbers of input/output cells (" + rlen + ":" + + clen + ", " + rows + ":" + cols + ")."); - //check for same dimensions - if( rlen==rows && clen == cols ) { - //copy incl dims, nnz - if( SHALLOW_COPY_REORG ) - out.copyShallow(in); + //determine output representation + out.sparse = MatrixBlock.evalSparseFormatInMemory(rows, cols, in.nonZeros); + + //set output dimensions + out.rlen = rows; + out.clen = cols; + out.nonZeros = in.nonZeros; + + //core reshape (sparse or dense) + if(!in.sparse && !out.sparse) + reshapeDense(in, out, rows, cols, rowwise); + else if(in.sparse && out.sparse) + reshapeSparse(in, out, rows, cols, rowwise, k); + else if(in.sparse) + reshapeSparseToDense(in, out, rows, cols, rowwise); else - out.copy(in); + reshapeDenseToSparse(in, out, rows, cols, rowwise); + return out; } - - //determine output representation - out.sparse = MatrixBlock.evalSparseFormatInMemory(rows, cols, in.nonZeros); - - //set output dimensions - out.rlen = rows; - out.clen = cols; - out.nonZeros = in.nonZeros; - - //core reshape (sparse or dense) - if(!in.sparse && !out.sparse) - reshapeDense(in, out, rows, cols, rowwise); - else if(in.sparse && out.sparse) - reshapeSparse(in, out, rows, cols, rowwise); - else if(in.sparse) - reshapeSparseToDense(in, out, rows, cols, rowwise); - else - reshapeDenseToSparse(in, out, rows, cols, rowwise); - - return out; + catch(Exception e) { + throw new RuntimeException("Failed to reshape Matrix", e); + } } @@ -2277,7 +2338,7 @@ public class LibMatrixReorg { //reshape empty block if( in.denseBlock == null ) return; - + //shallow dense by-row reshape (w/o result allocation) if( SHALLOW_COPY_REORG && rowwise && in.denseBlock.numBlocks()==1 ) { //since the physical representation of dense matrices is always the same, @@ -2336,8 +2397,8 @@ public class LibMatrixReorg { } } - private static void reshapeSparse( MatrixBlock in, MatrixBlock out, int rows, int cols, boolean rowwise ) - { + private static void reshapeSparse(MatrixBlock in, MatrixBlock out, int rows, int cols, boolean rowwise, int k) + throws Exception { int rlen = in.rlen; int clen = in.clen; @@ -2373,89 +2434,12 @@ public class LibMatrixReorg { c.append(0, cix+aix[j], avals[j]); } } - else if( cols%clen==0 //SPECIAL CSR N:1 MATRIX->MATRIX - && SHALLOW_COPY_REORG && SPARSE_OUTPUTS_IN_CSR - && in.nonZeros < Integer.MAX_VALUE ) { //int nnz - int n = cols/clen, pos = 0; - int[] rptr = new int[rows+1]; - int[] indexes = new int[(int)a.size()]; - double[] values = null; - rptr[0] = 0; - - if(a instanceof SparseBlockCSR) { - int[] aix = ((SparseBlockCSR)a).indexes(); - for(int bi=0, ci=0; bi<rlen; bi+=n, ci++) { - for( int i=bi, cix=0; i<bi+n; i++, cix+=clen ) { - if(a.isEmpty(i)) continue; - int apos = a.pos(i); - int alen = a.size(i); - for( int j=apos; j<apos+alen; j++ ) - indexes[pos++] = cix+aix[j]; - } - rptr[ci+1] = pos; - } - //shallow copy of CSR values - values = ((SparseBlockCSR)a).values(); - } - else { - values = new double[indexes.length]; - for(int bi=0, ci=0; bi<rlen; bi+=n, ci++) { //output rows - for( int i=bi, cix=0; i<bi+n; i++, cix+=clen ) { // N input rows - if(a.isEmpty(i)) continue; - int apos = a.pos(i); - int alen = a.size(i); - int[] aix = a.indexes(i); - System.arraycopy(a.values(i), apos, values, pos, alen); - for( int j=apos; j<apos+alen; j++ ) - indexes[pos++] = cix+aix[j]; - } - rptr[ci+1] = pos; - } - } - - //create CSR block from constructed or shallow-copy arrays - out.sparseBlock = new SparseBlockCSR(rptr, indexes, values, pos); - } - else if( cols%clen==0 ) { //SPECIAL N:1 MATRIX->MATRIX - int n = cols/clen; - for(int bi=0, ci=0; bi<rlen; bi+=n, ci++) { - //allocate output row once (w/o re-allocations) - long lnnz = a.size(bi, bi+n); - c.allocate(ci, (int)lnnz); - //copy N input rows into output row - for( int i=bi, cix=0; i<bi+n; i++, cix+=clen ) { - if(a.isEmpty(i)) continue; - int apos = a.pos(i); - int alen = a.size(i); - int[] aix = a.indexes(i); - double[] avals = a.values(i); - for( int j=apos; j<apos+alen; j++ ) - c.append(ci, cix+aix[j], avals[j]); - } - } - } - else //GENERAL CASE: MATRIX->MATRIX - { - //note: cache-friendly on a but not c; append-only - //long cix because total cells in sparse can be larger than int - long cix = 0; - for( int i=0; i<rlen; i++ ) { - if( !a.isEmpty(i) ){ - int apos = a.pos(i); - int alen = a.size(i); - int[] aix = a.indexes(i); - double[] avals = a.values(i); - for( int j=apos; j<apos+alen; j++ ) { - int ci = (int)((cix+aix[j])/cols); - int cj = (int)((cix+aix[j])%cols); - c.allocate(ci, estnnz, cols); - c.append(ci, cj, avals[j]); - } - } - - cix += clen; - } + else if( cols%clen==0 // SPECIAL CSR N:1 MATRIX->MATRIX + && SHALLOW_COPY_REORG && SPARSE_OUTPUTS_IN_CSR && in.getNonZeros() < Integer.MAX_VALUE) { // int nnz + reshapeSparseToCSR(in, out, rows, cols); } + else + reshapeSparseToMCSR(in, out, rows, cols, k); } else //colwise { @@ -2501,6 +2485,179 @@ public class LibMatrixReorg { } } + private static void reshapeSparseToMCSR(MatrixBlock in, MatrixBlock out, int rows, int cols, int k) throws Exception{ + int rlen = in.rlen; + int clen = in.clen; + + // allocate block + out.allocateSparseRowsBlock(false); + int estnnz = (int) (in.nonZeros / rows); + + // sparse reshape + SparseBlock a = in.sparseBlock; + SparseBlock c = out.sparseBlock; + if(cols % clen == 0) + reshapeSparseToMCSR_Nto1(in, out, rows, cols, k); + else // GENERAL CASE: MATRIX->MATRIX + { + // note: cache-friendly on a but not c; append-only + // long cix because total cells in sparse can be larger than int + long cix = 0; + for(int i = 0; i < rlen; i++) { + if(!a.isEmpty(i)) { + int apos = a.pos(i); + int alen = a.size(i); + int[] aix = a.indexes(i); + double[] avals = a.values(i); + for(int j = apos; j < apos + alen; j++) { + int ci = (int) ((cix + aix[j]) / cols); + int cj = (int) ((cix + aix[j]) % cols); + c.allocate(ci, estnnz, cols); + c.append(ci, cj, avals[j]); + } + } + + cix += clen; + } + } + } + + private static void reshapeSparseToMCSR_Nto1(MatrixBlock in, MatrixBlock out, int rows, int cols, int k) throws Exception{ + // SPECIAL N:1 MATRIX->MATRIX + final int rlen = in.rlen; + final int clen = in.clen; + + final SparseBlock a = in.sparseBlock; + final SparseBlock c = out.sparseBlock; + final int n = cols / clen; + // safe now since we fixed the parfor threading. + if((k > 1 || k == -1) && ((double) rows / k) > 16) { + final ExecutorService pool = CommonThreadPool.get(k == -1 ? InfrastructureAnalyzer.getLocalParallelism() : k); + try { + final int blkz = Math.max((int) Math.ceil((double) rows / k), 16); + ArrayList<Future<?>> tasks = new ArrayList<>(); + for(int i = 0; i < rows; i += blkz) { + final int start = i; + final int end = Math.min(i + blkz, rows); + tasks.add(pool.submit(() -> { + for(int bi = start * n, ci = start; ci < end; bi += n, ci++) { + reshapeSparseToMCSR_Nto1_row(a, c, clen, bi, n, ci); + } + })); + } + for(Future<?> f : tasks) + f.get(); + } + finally { + pool.shutdown(); + } + } + else { + for(int bi = 0, ci = 0; bi < rlen; bi += n, ci++) { + reshapeSparseToMCSR_Nto1_row(a, c, clen, bi, n, ci); + } + } + + out.setNonZeros(in.nonZeros); + } + + private static void reshapeSparseToMCSR_Nto1_row(SparseBlock a, SparseBlock c, int clen, int bi, int n, int ci){ + // allocate output row once (w/o re-allocations) + final int s = (int) a.size(bi, bi + n); // get exact size of row output + final int[] cix = new int[s]; + final double[] cvals = new double[s]; + + int pos = 0; + // copy N input rows into output row + for(int i = bi, colOffset = 0; i < bi + n; i++, colOffset += clen) { + pos = reshapeSparseToMCSR_Nto1_row_one(a,i, pos,cix, colOffset, cvals); + } + c.set(ci, new SparseRowVector(cvals, cix), false); + } + + private static int reshapeSparseToMCSR_Nto1_row_one(SparseBlock a, int i, int pos, int[] cix, int colOffset, + double[] cvals) { + if(a.isEmpty(i)) + return pos; + final int apos = a.pos(i); + final int alen = a.size(i); + final int[] aix = a.indexes(i); + final double[] avals = a.values(i); + for(int j = apos; j < apos + alen; j++, pos++) { + cix[pos] = colOffset + aix[j]; + cvals[pos] = avals[j]; + } + return pos; + } + + private static void reshapeSparseToCSR(MatrixBlock in, MatrixBlock out, int rows, int cols) { + if(in.sparseBlock instanceof SparseBlockCSR) + reshapeSparseToCSRFromCSR(in, out, rows, cols); + else + reshapeSparseToCSRFromMCSR(in, out, rows, cols); + } + + private static void reshapeSparseToCSRFromMCSR(MatrixBlock in, MatrixBlock out, int rows, int cols) { + final SparseBlock a = in.sparseBlock; + final int rlen = in.rlen; + final int clen = in.clen; + + final int n = cols / clen; + final int[] rptr = new int[rows + 1]; + final int[] indexes = new int[(int) a.size()]; + final double[] values = new double[indexes.length]; + + int pos = 0; + + for(int bi = 0, ci = 0; bi < rlen; bi += n, ci++) { // output rows + for(int i = bi, cix = 0; i < bi + n; i++, cix += clen) { // N input rows + if(a.isEmpty(i)) + continue; + final int apos = a.pos(i); + final int alen = a.size(i); + final int[] aix = a.indexes(i); + System.arraycopy(a.values(i), apos, values, pos, alen); + for(int j = apos; j < apos + alen; j++) + indexes[pos++] = cix + aix[j]; + } + rptr[ci + 1] = pos; + } + + // create CSR block from constructed or shallow-copy arrays + out.sparseBlock = new SparseBlockCSR(rptr, indexes, values, pos); + } + + + private static void reshapeSparseToCSRFromCSR(MatrixBlock in, MatrixBlock out, int rows, int cols) { + final SparseBlock a = in.sparseBlock; + int rlen = in.rlen; + int clen = in.clen; + + int n = cols / clen, pos = 0; + int[] rptr = new int[rows + 1]; + int[] indexes = new int[(int) a.size()]; + double[] values = null; + rptr[0] = 0; + + int[] aix = ((SparseBlockCSR) a).indexes(); + for(int bi = 0, ci = 0; bi < rlen; bi += n, ci++) { + for(int i = bi, cix = 0; i < bi + n; i++, cix += clen) { + if(a.isEmpty(i)) + continue; + int apos = a.pos(i); + int alen = a.size(i); + for(int j = apos; j < apos + alen; j++) + indexes[pos++] = cix + aix[j]; + } + rptr[ci + 1] = pos; + } + // shallow copy of CSR values + values = ((SparseBlockCSR) a).values(); + + // create CSR block from constructed or shallow-copy arrays + out.sparseBlock = new SparseBlockCSR(rptr, indexes, values, pos); + } + private static void reshapeDenseToSparse( MatrixBlock in, MatrixBlock out, int rows, int cols, boolean rowwise ) { int rlen = in.rlen; diff --git a/src/test/java/org/apache/sysds/performance/Main.java b/src/test/java/org/apache/sysds/performance/Main.java index a281dd2cf0..e161ca0187 100644 --- a/src/test/java/org/apache/sysds/performance/Main.java +++ b/src/test/java/org/apache/sysds/performance/Main.java @@ -33,6 +33,7 @@ import org.apache.sysds.performance.generators.MatrixFile; import org.apache.sysds.performance.matrix.MatrixMulPerformance; import org.apache.sysds.performance.matrix.MatrixReplacePerf; import org.apache.sysds.performance.matrix.MatrixStorage; +import org.apache.sysds.performance.matrix.ReshapePerf; import org.apache.sysds.performance.matrix.SparseAppend; import org.apache.sysds.runtime.data.SparseBlock; import org.apache.sysds.runtime.frame.data.FrameBlock; @@ -123,6 +124,9 @@ public class Main { case 1004: run1004(args); break; + case 1005: + ReshapePerf.main(args); + break; default: break; } diff --git a/src/test/java/org/apache/sysds/performance/README.md b/src/test/java/org/apache/sysds/performance/README.md index 7129757f34..751e5e3cf9 100644 --- a/src/test/java/org/apache/sysds/performance/README.md +++ b/src/test/java/org/apache/sysds/performance/README.md @@ -70,3 +70,9 @@ Frame Operation timings java -jar -agentpath:$HOME/Programs/profiler/lib/libasyncProfiler.so=start,event=cpu,file=temp/log.html target/systemds-3.3.0-SNAPSHOT-perf.jar 15 16 10 "src/test/resources/datasets/titanic/titanic.csv" "src/test/resources/datasets/titanic/tfspec.json" ``` +Reshape Sparse + +```bash +java -cp "target/systemds-3.3.0-SNAPSHOT-perf.jar:target/lib/*" -agentpath:$HOME/Programs/profiler/lib/libasyncProfiler.so=start,event=cpu,file=temp/log.html org.apache.sysds.performance.Main 1005 +``` + diff --git a/src/test/java/org/apache/sysds/performance/matrix/ReshapePerf.java b/src/test/java/org/apache/sysds/performance/matrix/ReshapePerf.java new file mode 100644 index 0000000000..246598bcf8 --- /dev/null +++ b/src/test/java/org/apache/sysds/performance/matrix/ReshapePerf.java @@ -0,0 +1,86 @@ +/* + * 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.performance.compression.APerfTest; +import org.apache.sysds.performance.generators.ConstMatrix; +import org.apache.sysds.performance.generators.IGenerate; +import org.apache.sysds.runtime.data.SparseBlockCSR; +import org.apache.sysds.runtime.matrix.data.LibMatrixReorg; +import org.apache.sysds.runtime.matrix.data.MatrixBlock; +import org.apache.sysds.test.TestUtils; + +public class ReshapePerf extends APerfTest<Object, MatrixBlock> { + + private final int k; + + public ReshapePerf(int N, IGenerate<MatrixBlock> gen, int k) { + super(N, gen); + this.k = k; + } + + public void run() throws Exception { + MatrixBlock mb = gen.take(); + System.out.println( + String.format("Input Size: %d x %d , sparsity: %f ", mb.getNumRows(), mb.getNumColumns(), mb.getSparsity())); + warmup(() -> reshape_Div(k, 2), 1000); + + execute(() -> reshape_Div(k, 1), "same"); + for(int i = 2; i < 51; i++) { + double d = ((double) mb.getNumRows() / i); + final int ii = i; + if((int) d == d) { + execute(() -> reshape_Div(k, ii), "replace_div " + i + " Parallel: " + k); + } + + } + } + + private void reshape_Div(int k, int div) { + MatrixBlock mb = gen.take(); + LibMatrixReorg.reshape(mb, null, mb.getNumRows() / div, mb.getNumColumns() * div, true, k); + ret.add(null); + } + + @Override + protected String makeResString() { + return ""; + } + + public static void main(String[] args) throws Exception { + MatrixBlock a = TestUtils.ceil(TestUtils.generateTestMatrixBlock(10000, 10000, 0, 100, 0.1, 42)); + // to CSR + // System.out.println("MCSR to CSR"); + // new ReshapePerf(100, new ConstMatrix(a), 1).run(); + // new ReshapePerf(1000, new ConstMatrix(a), 16).run(); + + // System.out.println("MCSR to MCSR parallel"); + // MatrixBlock spy = spy(a); + // when(spy.getNonZeros()).thenReturn((long)Integer.MAX_VALUE + 42L); + // new ReshapePerf(100, new ConstMatrix(spy), 1).run(); + // new ReshapePerf(100, new ConstMatrix(spy), 16).run(); + + System.out.println("CSR to CSR"); + a.setSparseBlock(new SparseBlockCSR(a.getSparseBlock())); + new ReshapePerf(100, new ConstMatrix(a), 1).run(); + + } + +} diff --git a/src/test/java/org/apache/sysds/test/TestUtils.java b/src/test/java/org/apache/sysds/test/TestUtils.java index ca6a3b2bf5..3a78a3780b 100644 --- a/src/test/java/org/apache/sysds/test/TestUtils.java +++ b/src/test/java/org/apache/sysds/test/TestUtils.java @@ -2056,25 +2056,18 @@ public class TestUtils { /** * <p> - * Generates a test matrix with the specified parameters as a two - * dimensional array. + * Generates a test matrix with the specified parameters as a two dimensional array. * </p> * <p> * Set seed to -1 to use the current time as seed. * </p> * - * @param rows - * number of rows - * @param cols - * number of columns - * @param min - * minimum value - * @param max - * maximum value - * @param sparsity - * sparsity - * @param seed - * seed + * @param rows number of rows + * @param cols number of columns + * @param min minimum value + * @param max maximum value + * @param sparsity sparsity + * @param seed seed * @return random matrix */ public static double[][] generateTestMatrix(int rows, int cols, double min, double max, double sparsity, long seed) { diff --git a/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/ReshapeTest.java b/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/ReshapeTest.java new file mode 100644 index 0000000000..379128e0d4 --- /dev/null +++ b/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/ReshapeTest.java @@ -0,0 +1,476 @@ +/* + * 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.test.component.matrix.libMatrixReorg; + +import static org.junit.Assert.assertEquals; +import static org.mockito.Mockito.spy; +import static org.mockito.Mockito.when; + +import java.util.ArrayList; +import java.util.Collection; + +import org.apache.commons.logging.Log; +import org.apache.commons.logging.LogFactory; +import org.apache.sysds.runtime.data.DenseBlock; +import org.apache.sysds.runtime.data.SparseBlockCSR; +import org.apache.sysds.runtime.matrix.data.LibMatrixReorg; +import org.apache.sysds.runtime.matrix.data.MatrixBlock; +import org.apache.sysds.test.TestUtils; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.Parameterized; +import org.junit.runners.Parameterized.Parameters; + +@RunWith(value = Parameterized.class) + +public class ReshapeTest { + protected static final Log LOG = LogFactory.getLog(ReshapeTest.class.getName()); + + @Parameterized.Parameter + public int k; + @Parameterized.Parameter(1) + public boolean rowWise; + + @Parameters + public static Collection<Object[]> data() { + ArrayList<Object[]> tests = new ArrayList<>(); + tests.add(new Object[] {1, true}); + tests.add(new Object[] {10, true}); + tests.add(new Object[] {-1, true}); + tests.add(new Object[] {1, false}); + tests.add(new Object[] {10, false}); + tests.add(new Object[] {-1, false}); + + return tests; + } + + @Test + public void reshapeDense1() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(10, 5, 0, 10, 1.0, 132); + MatrixBlock b = runReshape(a, 5, 10); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDense2() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 5, 0, 10, 1.0, 132); + MatrixBlock b = runReshape(a, 5, 100); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDense3() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 24, 0, 10, 1.0, 132); + MatrixBlock b = runReshape(a, 24, 100); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDense4() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(2, 2, 0, 10, 1.0, 132); + MatrixBlock b = runReshape(a, 1, 4); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDense5() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 50, 0, 10, 1.0, 132); + MatrixBlock b = runReshape(a, 25, 200); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDense6() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 1, 0, 10, 1.0, 132); + MatrixBlock b = runReshape(a, 25, 4); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDense7() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(1, 100, 0, 10, 1.0, 132); + MatrixBlock b = runReshape(a, 25, 4); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDense8() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 50, 0, 10, 1.0, 132); + DenseBlock db = a.getDenseBlock(); + DenseBlock spy = spy(db); + when(spy.numBlocks()).thenReturn(2); + a.setDenseBlock(spy); + MatrixBlock b = runReshape(a, 25, 200); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDense9() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(25, 4, 0, 10, 1.0, 132); + MatrixBlock b = runReshape(a, 100, 1); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDense10() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(25, 4, 0, 10, 1.0, 132); + MatrixBlock b = runReshape(a, 1, 100); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDense11() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(25, 4, 0, 10, 1.0, 132); + a.setDenseBlock(null); + MatrixBlock b = runReshape(a, 1, 100); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDense4OtherInterface() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 50, 0, 10, 1.0, 132); + MatrixBlock b = LibMatrixReorg.reshape(a, null, 25, 200, rowWise); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDense4OtherInterfaceObject() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 50, 0, 10, 1.0, 132); + MatrixBlock b = LibMatrixReorg.reshape(a, new MatrixBlock(), 25, 200, rowWise); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSameSize1() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 50, 0, 10, 1.0, 132); + MatrixBlock b = runReshape(a, 100, 50); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSameSize2() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(10, 5, 0, 10, 1.0, 132); + MatrixBlock b = runReshape(a, 10, 5); + verifyEqualReshaped(a, b); + } + + @Test(expected = Exception.class) + public void invalid1() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(10, 5, 0, 10, 1.0, 132); + runReshape(a, 10, 10); + } + + @Test(expected = Exception.class) + public void invalid2() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(10, 5, 0, 10, 1.0, 132); + runReshape(a, 5, 5); + } + + @Test(expected = Exception.class) + public void invalid3() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(10, 5, 0, 10, 1.0, 132); + runReshape(a, 12, 12); + } + + @Test + public void reshapeSparseToDense() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(1, 100, 0, 10, 0.1, 132); + MatrixBlock b = runReshape(a, 100, 1); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToDense2() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(1, 100, 0, 10, 0.1, 132); + MatrixBlock b = runReshape(a, 50, 2); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToDense3() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 100, 0, 10, 0.9, 132); + + a.denseToSparse(true); + MatrixBlock b = runReshape(a, 200, 50); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToDense4() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 100, 0, 10, 0.9, 132); + a.denseToSparse(true); + MatrixBlock b = runReshape(a, 50, 200); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToDense5() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 100, 0, 10, 0.9, 132); + a.getDenseBlock().fillRow(3, 0); + a.denseToSparse(true); + MatrixBlock b = runReshape(a, 50, 200); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToDense6() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(3, 100, 0, 10, 1.0, 132); + a.getDenseBlock().fillRow(1, 0); + a.denseToSparse(true); + MatrixBlock b = runReshape(a, 1, 300); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToDense7() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(1, 100, 0, 10, 1.0, 132); + a.getDenseBlock().fillRow(0, 0); + a.denseToSparse(false); + MatrixBlock b = runReshape(a, 2, 50); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDenseToSparse1() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 1, 0, 10, 0.1, 132); + MatrixBlock b = runReshape(a, 1, 100); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDenseToSparse2() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 1, 0, 10, 0.1, 132); + MatrixBlock b = runReshape(a, 2, 50); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDenseToSparse3() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 2, 0, 10, 0.1, 132); + MatrixBlock b = runReshape(a, 2, 100); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDenseToSparse4() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 2, 0, 10, 0.1, 132); + a.setDenseBlock(null); + MatrixBlock b = runReshape(a, 2, 100); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeDenseToSparse5() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(50, 2, 0, 10, 0.1, 132); + MatrixBlock b = runReshape(a, 1, 100); + verifyEqualReshaped(a, b); + } + + + @Test + public void reshapeDenseToSparse6() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(1, 100, 0, 10, 0.1, 132); + a.sparseToDense(); + MatrixBlock b = runReshape(a, 2, 50); + verifyEqualReshaped(a, b); + } + + + @Test + public void reshapeSparseToSparse() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 100, 0, 10, 0.1, 132); + MatrixBlock b = runReshape(a, 50, 200); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToSparse2() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 100, 0, 10, 0.1, 132); + MatrixBlock b = runReshape(a, 25, 400); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToSparse3() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 125, 0, 10, 0.1, 132); + MatrixBlock b = runReshape(a, 25, 500); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToSparse4() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 125, 0, 10, 0.1, 132); + MatrixBlock b = runReshape(a, 1, 100 * 125); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToSparse5() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 1, 0, 10, 0.1, 132); + MatrixBlock b = runReshape(a, 1, 100); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToSparse6() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 100, 0, 10, 0.001, 132); + MatrixBlock b = runReshape(a, 50, 200); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToSparse7() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(10, 100, 0, 10, 0.0001, 132); + MatrixBlock b = runReshape(a, 1, 1000); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToSparse8() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(1, 1000, 0, 10, 0.0001, 132); + MatrixBlock b = runReshape(a, 2, 500); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToSparse9() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(1, 1000, 0, 10, 0.001, 132); + MatrixBlock b = runReshape(a, 2, 500); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToSparse10() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(4, 250, 0, 10, 0.001, 132); + a.setSparseBlock(new SparseBlockCSR(a.getSparseBlock())); + MatrixBlock b = runReshape(a, 2, 500); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToSparse11() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(4, 250, 0, 10, 0.001, 132); + MatrixBlock spy = spy(a); + when(spy.getNonZeros()).thenReturn((long) Integer.MAX_VALUE + 45L); + MatrixBlock b = runReshape(spy, 2, 500); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToSparse12() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(4, 125, 0, 10, (double)1 / (125*2), 132); + MatrixBlock b = runReshape(a, 1, 500); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeSparseToSparse13() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(1, 100, 0, 10, 0.1, 132); + a.getSparseBlock().reset(0, 10, 100); + MatrixBlock b = runReshape(a, 2, 50); + verifyEqualReshaped(a, b); + } + + + @Test + public void reshapeEmpty1() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(100, 125, 0, 10, 0.0, 132); + MatrixBlock b = runReshape(a, 25, 500); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeEmpty2() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(10, 10, 0, 10, 0.0, 132); + MatrixBlock b = runReshape(a, 5, 20); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeEmpty3() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(5, 5, 0, 10, 0.0, 132); + MatrixBlock b = runReshape(a, 1, 25); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeEmpty4() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(5, 5, 0, 10, 0.0, 132); + MatrixBlock b = runReshape(a, 25, 1); + verifyEqualReshaped(a, b); + } + + @Test + public void reshapeEmpty5() { + MatrixBlock a = TestUtils.generateTestMatrixBlock(6, 6, 0, 10, 0.0, 132); + MatrixBlock b = runReshape(a, 3, 12); + verifyEqualReshaped(a, b); + } + + private MatrixBlock runReshape(MatrixBlock a, int r, int c) { + return LibMatrixReorg.reshape(a, null, r, c, rowWise, k); + } + + private void verifyEqualReshaped(MatrixBlock expected, MatrixBlock actual) { + final long expectedCells = (long) expected.getNumRows() * expected.getNumColumns(); + final long actualCells = (long) actual.getNumRows() * actual.getNumColumns(); + + assertEquals(expectedCells, actualCells); + final long eCols = expected.getNumColumns(); + final long eRows = expected.getNumRows(); + final long aCols = actual.getNumColumns(); + final long aRows = actual.getNumRows(); + + if(rowWise) { + + for(long c = 0; c < expectedCells; c++) { + int r1 = (int) (c / eCols); + int c1 = (int) (c % eCols); + + int r2 = (int) (c / aCols); + int c2 = (int) (c % aCols); + if(expected.get(r1, c1) != actual.get(r2, c2)) { + double v1 = expected.get(r1, c1); + double v2 = actual.get(r2, c2); + String err = String.format("%d,%d vs %d,%d not equal with values: %f vs %f", r1, c1, r2, c2, v1, v2); + assertEquals(err, v1, v2, 0.0); + } + } + } + else { + + for(long c = 0; c < expectedCells; c++) { + int r2 = (int) (c / aCols); + int c2 = (int) (c % aCols); + + int r1 = (int) ((aRows * c2 + r2) % eRows); + int c1 = (int) ((aRows * c2 + r2) / eRows); + + if(expected.get(r1, c1) != actual.get(r2, c2)) { + double v1 = expected.get(r1, c1); + double v2 = actual.get(r2, c2); + String err = String.format("%d,%d vs %d,%d not equal with values: %f vs %f", r1, c1, r2, c2, v1, v2); + assertEquals(err, v1, v2, 0.0); + } + } + } + + } +} diff --git a/src/test/java/org/apache/sysds/test/component/matrix/TransposeCSRTest.java b/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/TransposeCSRTest.java similarity index 98% rename from src/test/java/org/apache/sysds/test/component/matrix/TransposeCSRTest.java rename to src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/TransposeCSRTest.java index 9f4ff33719..35d4d0546d 100644 --- a/src/test/java/org/apache/sysds/test/component/matrix/TransposeCSRTest.java +++ b/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/TransposeCSRTest.java @@ -17,7 +17,7 @@ * under the License. */ -package org.apache.sysds.test.component.matrix; +package org.apache.sysds.test.component.matrix.libMatrixReorg; import static org.junit.Assert.fail; diff --git a/src/test/java/org/apache/sysds/test/component/matrix/TransposeInplaceTest.java b/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/TransposeInplaceTest.java similarity index 97% rename from src/test/java/org/apache/sysds/test/component/matrix/TransposeInplaceTest.java rename to src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/TransposeInplaceTest.java index 7b23bdadb9..4490136cd6 100644 --- a/src/test/java/org/apache/sysds/test/component/matrix/TransposeInplaceTest.java +++ b/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/TransposeInplaceTest.java @@ -17,7 +17,7 @@ * under the License. */ -package org.apache.sysds.test.component.matrix; +package org.apache.sysds.test.component.matrix.libMatrixReorg; import java.util.ArrayList; import java.util.Collection; diff --git a/src/test/java/org/apache/sysds/test/component/matrix/TransposeTwiceTest.java b/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/TransposeTwiceTest.java similarity index 98% rename from src/test/java/org/apache/sysds/test/component/matrix/TransposeTwiceTest.java rename to src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/TransposeTwiceTest.java index c8fcb7abb1..eb38914f1e 100644 --- a/src/test/java/org/apache/sysds/test/component/matrix/TransposeTwiceTest.java +++ b/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/TransposeTwiceTest.java @@ -17,7 +17,7 @@ * under the License. */ -package org.apache.sysds.test.component.matrix; +package org.apache.sysds.test.component.matrix.libMatrixReorg; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail;