Repository: systemml Updated Branches: refs/heads/master 581077712 -> d91d24a9f
[SYSTEMML-2051] Fix sort of sparse blocks in COO format There was an issue with sorting sparse blocks in COO format if the underlying allocated arrays match exactly the logical size. This patch fixes this issue and makes minor cleanups of the matrix block sparse merge primitive, which applies to all sparse block formats. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/38332acd Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/38332acd Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/38332acd Branch: refs/heads/master Commit: 38332acde74cb235cf22397981cd9aa6f5598c9b Parents: 5810777 Author: Matthias Boehm <[email protected]> Authored: Mon Dec 25 10:14:33 2017 +0100 Committer: Matthias Boehm <[email protected]> Committed: Mon Dec 25 14:25:59 2017 +0100 ---------------------------------------------------------------------- .../sysml/runtime/matrix/data/MatrixBlock.java | 4 +- .../runtime/matrix/data/SparseBlockCOO.java | 12 ++-- .../functions/sparse/SparseBlockMerge.java | 68 +++++++++++++++++--- 3 files changed, 66 insertions(+), 18 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/38332acd/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java b/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java index 1245475..fb14acb 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java @@ -1756,7 +1756,7 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab } } //only sort if value appended - if( !appendOnly && appended ) + if( !COO && !appendOnly && appended ) a.sort(i); } } @@ -1769,7 +1769,7 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab boolean appended = false; for( int j=0; j<n; j++ ) { if( b[bix+j] != 0 ) { - appendValue(i, j, b[bix+j]); + appendValue(i, j, b[bix+j]); //incl alloc appended = true; } } http://git-wip-us.apache.org/repos/asf/systemml/blob/38332acd/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java index 8c2604b..d8b5326 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java @@ -211,7 +211,7 @@ public class SparseBlockCOO extends SparseBlock System.arraycopy(_rindexes, pos+len, _rindexes, pos, _size-(pos+len)); System.arraycopy(_cindexes, pos+len, _cindexes, pos, _size-(pos+len)); System.arraycopy(_values, pos+len, _values, pos, _size-(pos+len)); - _size -= len; + _size -= len; } } @@ -230,7 +230,7 @@ public class SparseBlockCOO extends SparseBlock double rix0 = _rindexes[pos]; int cnt = 0; while( pos<_size && rix0 == _rindexes[pos++] ) - cnt ++; + cnt ++; return cnt; } @@ -393,10 +393,10 @@ public class SparseBlockCOO extends SparseBlock //sort _cindexes/_values by _cindexes per row partition int index = 0; - while( index < _size ){ + while( index < _size ) { int r = _rindexes[index]; int len = 0; - while( r == _rindexes[index] ) { + while( index < _size && r == _rindexes[index] ) { len ++; index ++; } @@ -574,7 +574,7 @@ public class SparseBlockCOO extends SparseBlock insert(ix, r, c, v); } - private void shiftRightAndInsert(int ix, int r, int c, double v) { + private void shiftRightAndInsert(int ix, int r, int c, double v) { //overlapping array copy (shift rhs values right by 1) System.arraycopy(_rindexes, ix, _rindexes, ix+1, _size-ix); System.arraycopy(_cindexes, ix, _cindexes, ix+1, _size-ix); @@ -605,7 +605,7 @@ public class SparseBlockCOO extends SparseBlock _rindexes[ix] = r; _cindexes[ix] = c; _values[ix] = v; - _size++; + _size++; } /** http://git-wip-us.apache.org/repos/asf/systemml/blob/38332acd/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockMerge.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockMerge.java b/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockMerge.java index 019b89b..b6c9324 100644 --- a/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockMerge.java +++ b/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockMerge.java @@ -32,6 +32,7 @@ public class SparseBlockMerge extends AutomatedTestBase { private final static int rows = 1000; private final static int cols = 1000; + private final static double sparsity0 = 0.000005; private final static double sparsity1 = 0.001; private final static double sparsity2 = 0.01; private final static double sparsity3 = 0.1; @@ -42,6 +43,11 @@ public class SparseBlockMerge extends AutomatedTestBase } @Test + public void testMergeMCSR_MCSR_0() { + runSparseBlockMergeTest(SparseBlock.Type.MCSR, SparseBlock.Type.MCSR, sparsity0); + } + + @Test public void testMergeMCSR_MCSR_1() { runSparseBlockMergeTest(SparseBlock.Type.MCSR, SparseBlock.Type.MCSR, sparsity1); } @@ -57,6 +63,11 @@ public class SparseBlockMerge extends AutomatedTestBase } @Test + public void testMergeMCSR_CSR_0() { + runSparseBlockMergeTest(SparseBlock.Type.MCSR, SparseBlock.Type.CSR, sparsity0); + } + + @Test public void testMergeMCSR_CSR_1() { runSparseBlockMergeTest(SparseBlock.Type.MCSR, SparseBlock.Type.CSR, sparsity1); } @@ -72,6 +83,11 @@ public class SparseBlockMerge extends AutomatedTestBase } @Test + public void testMergeMCSR_COO_0() { + runSparseBlockMergeTest(SparseBlock.Type.MCSR, SparseBlock.Type.COO, sparsity0); + } + + @Test public void testMergeMCSR_COO_1() { runSparseBlockMergeTest(SparseBlock.Type.MCSR, SparseBlock.Type.COO, sparsity1); } @@ -87,6 +103,11 @@ public class SparseBlockMerge extends AutomatedTestBase } @Test + public void testMergeCSR_CSR_0() { + runSparseBlockMergeTest(SparseBlock.Type.CSR, SparseBlock.Type.CSR, sparsity0); + } + + @Test public void testMergeCSR_CSR_1() { runSparseBlockMergeTest(SparseBlock.Type.CSR, SparseBlock.Type.CSR, sparsity1); } @@ -102,6 +123,11 @@ public class SparseBlockMerge extends AutomatedTestBase } @Test + public void testMergeCSR_MCSR_0() { + runSparseBlockMergeTest(SparseBlock.Type.CSR, SparseBlock.Type.MCSR, sparsity0); + } + + @Test public void testMergeCSR_MCSR_1() { runSparseBlockMergeTest(SparseBlock.Type.CSR, SparseBlock.Type.MCSR, sparsity1); } @@ -117,6 +143,11 @@ public class SparseBlockMerge extends AutomatedTestBase } @Test + public void testMergeCSR_COO_0() { + runSparseBlockMergeTest(SparseBlock.Type.CSR, SparseBlock.Type.COO, sparsity0); + } + + @Test public void testMergeCSR_COO_1() { runSparseBlockMergeTest(SparseBlock.Type.CSR, SparseBlock.Type.COO, sparsity1); } @@ -132,6 +163,11 @@ public class SparseBlockMerge extends AutomatedTestBase } @Test + public void testMergeCOO_COO_0() { + runSparseBlockMergeTest(SparseBlock.Type.COO, SparseBlock.Type.COO, sparsity0); + } + + @Test public void testMergeCOO_COO_1() { runSparseBlockMergeTest(SparseBlock.Type.COO, SparseBlock.Type.COO, sparsity1); } @@ -147,6 +183,11 @@ public class SparseBlockMerge extends AutomatedTestBase } @Test + public void testMergeCOO_MCSR_0() { + runSparseBlockMergeTest(SparseBlock.Type.COO, SparseBlock.Type.MCSR, sparsity0); + } + + @Test public void testMergeCOO_MCSR_1() { runSparseBlockMergeTest(SparseBlock.Type.COO, SparseBlock.Type.MCSR, sparsity1); } @@ -162,6 +203,11 @@ public class SparseBlockMerge extends AutomatedTestBase } @Test + public void testMergeCOO_CSR_0() { + runSparseBlockMergeTest(SparseBlock.Type.COO, SparseBlock.Type.CSR, sparsity0); + } + + @Test public void testMergeCOO_CSR_1() { runSparseBlockMergeTest(SparseBlock.Type.COO, SparseBlock.Type.CSR, sparsity1); } @@ -212,16 +258,18 @@ public class SparseBlockMerge extends AutomatedTestBase //check correct values long count = 0; SparseBlock sblock = mb1.getSparseBlock(); - for( int i=0; i<rows; i++) { - if( sblock.isEmpty(i) ) continue; - int alen = sblock.size(i); - int apos = sblock.pos(i); - int[] aix = sblock.indexes(i); - double[] avals = sblock.values(i); - for( int j=0; j<alen; j++ ) { - if( avals[apos+j] != A[i][aix[apos+j]] ) - Assert.fail("Wrong value returned by scan: "+avals[apos+j]+", expected: "+A[i][apos+aix[j]]); - count++; + if( sblock != null ) { + for( int i=0; i<rows; i++) { + if( sblock.isEmpty(i) ) continue; + int alen = sblock.size(i); + int apos = sblock.pos(i); + int[] aix = sblock.indexes(i); + double[] avals = sblock.values(i); + for( int j=0; j<alen; j++ ) { + if( avals[apos+j] != A[i][aix[apos+j]] ) + Assert.fail("Wrong value returned by scan: "+avals[apos+j]+", expected: "+A[i][apos+aix[j]]); + count++; + } } } if( count != nnz )
