Repository: incubator-systemml Updated Branches: refs/heads/master 14e9f6443 -> a5584c0fd
[SYSTEMML-826] Basic get value over compressed matrix blocks, tests Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/f85cf16e Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/f85cf16e Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/f85cf16e Branch: refs/heads/master Commit: f85cf16e6e3f38124f96f5e8cd8b561cb4a601fd Parents: 14e9f64 Author: Matthias Boehm <[email protected]> Authored: Fri Jul 22 14:03:06 2016 -0700 Committer: Matthias Boehm <[email protected]> Committed: Sat Jul 23 14:41:46 2016 -0700 ---------------------------------------------------------------------- .../apache/sysml/runtime/compress/ColGroup.java | 9 + .../sysml/runtime/compress/ColGroupBitmap.java | 26 +++ .../runtime/compress/ColGroupUncompressed.java | 11 ++ .../runtime/compress/CompressedMatrixBlock.java | 16 ++ .../functions/compress/BasicGetValueTest.java | 170 +++++++++++++++++++ .../functions/compress/ZPackageSuite.java | 1 + 6 files changed, 233 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/f85cf16e/src/main/java/org/apache/sysml/runtime/compress/ColGroup.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/compress/ColGroup.java b/src/main/java/org/apache/sysml/runtime/compress/ColGroup.java index b1072d1..200e12a 100644 --- a/src/main/java/org/apache/sysml/runtime/compress/ColGroup.java +++ b/src/main/java/org/apache/sysml/runtime/compress/ColGroup.java @@ -203,6 +203,15 @@ public abstract class ColGroup implements Serializable public abstract long getExactSizeOnDisk(); /** + * Get the value at a global row/column position. + * + * @param r + * @param c + * @return + */ + public abstract double get(int r, int c); + + /** * Multiply the slice of the matrix that this column group represents by a * vector on the right. * http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/f85cf16e/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java b/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java index 3455cc7..0ab65f1 100644 --- a/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java +++ b/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java @@ -263,6 +263,32 @@ public abstract class ColGroupBitmap extends ColGroup } } } + + //generic get for OLE/RLE, to be overwritten for performance + //potential: skip scan (segment length agg and run length) instead of decode + @Override + public double get(int r, int c) { + //find local column index + int ix = Arrays.binarySearch(_colIndexes, c); + if( ix < 0 ) + throw new RuntimeException("Column index "+c+" not in bitmap group."); + + //find row index in value offset lists via scan + final int numCols = getNumCols(); + final int numVals = getNumValues(); + for (int i = 0; i < numVals; i++) { + Iterator<Integer> decoder = getDecodeIterator(i); + int valOff = i*numCols; + while (decoder.hasNext()) { + int row = decoder.next(); + if( row == r ) + return _values[valOff+ix]; + else if( row > r ) + break; //current value + } + } + return 0; + } /** * http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/f85cf16e/src/main/java/org/apache/sysml/runtime/compress/ColGroupUncompressed.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/compress/ColGroupUncompressed.java b/src/main/java/org/apache/sysml/runtime/compress/ColGroupUncompressed.java index 21df0c0..43bfa72 100644 --- a/src/main/java/org/apache/sysml/runtime/compress/ColGroupUncompressed.java +++ b/src/main/java/org/apache/sysml/runtime/compress/ColGroupUncompressed.java @@ -248,6 +248,17 @@ public class ColGroupUncompressed extends ColGroup } @Override + public double get(int r, int c) { + //find local column index + int ix = Arrays.binarySearch(_colIndexes, c); + if( ix < 0 ) + throw new RuntimeException("Column index "+c+" not in uncompressed group."); + + //uncompressed get value + return _data.quickGetValue(r, ix); + } + + @Override public void rightMultByVector(MatrixBlock vector, MatrixBlock result, int rl, int ru) throws DMLRuntimeException { http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/f85cf16e/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java b/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java index aa21e16..81d933d 100644 --- a/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java +++ b/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java @@ -497,6 +497,22 @@ public class CompressedMatrixBlock extends MatrixBlock implements Externalizable } } + @Override + public double quickGetValue(int r, int c) { + if( !isCompressed() ) { + return super.quickGetValue(r, c); + } + + //find column group according to col index + ColGroup grp = null; + for( ColGroup group : _colGroups ) + if( Arrays.binarySearch(group.getColIndices(), c) >= 0 ) { + grp = group; break; + } + + //find row value + return grp.get(r, c); + } ////////////////////////////////////////// // Serialization / Deserialization http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/f85cf16e/src/test/java/org/apache/sysml/test/integration/functions/compress/BasicGetValueTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/sysml/test/integration/functions/compress/BasicGetValueTest.java b/src/test/java/org/apache/sysml/test/integration/functions/compress/BasicGetValueTest.java new file mode 100644 index 0000000..0515acb --- /dev/null +++ b/src/test/java/org/apache/sysml/test/integration/functions/compress/BasicGetValueTest.java @@ -0,0 +1,170 @@ +/* + * 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.sysml.test.integration.functions.compress; + +import org.apache.sysml.runtime.compress.CompressedMatrixBlock; +import org.apache.sysml.runtime.matrix.data.MatrixBlock; +import org.apache.sysml.runtime.util.DataConverter; +import org.apache.sysml.test.integration.AutomatedTestBase; +import org.apache.sysml.test.utils.TestUtils; +import org.junit.Assert; +import org.junit.Test; + + +/** + * + */ +public class BasicGetValueTest extends AutomatedTestBase +{ + private static final int rows = 1023; + private static final int cols = 20; + private static final double sparsity1 = 0.9; + private static final double sparsity2 = 0.1; + private static final double sparsity3 = 0.0; + + public enum SparsityType { + DENSE, + SPARSE, + EMPTY, + } + + public enum ValueType { + RAND, + RAND_ROUND, + CONST, + } + + @Override + public void setUp() { + + } + + @Test + public void testDenseRandDataCompression() { + runGetValueTest(SparsityType.DENSE, ValueType.RAND, true); + } + + @Test + public void testSparseRandDataCompression() { + runGetValueTest(SparsityType.SPARSE, ValueType.RAND, true); + } + + @Test + public void testEmptyCompression() { + runGetValueTest(SparsityType.EMPTY, ValueType.RAND, true); + } + + @Test + public void testDenseRoundRandDataCompression() { + runGetValueTest(SparsityType.DENSE, ValueType.RAND_ROUND, true); + } + + @Test + public void testSparseRoundRandDataCompression() { + runGetValueTest(SparsityType.SPARSE, ValueType.RAND_ROUND, true); + } + + @Test + public void testDenseConstantDataCompression() { + runGetValueTest(SparsityType.DENSE, ValueType.CONST, true); + } + + @Test + public void testSparseConstDataCompression() { + runGetValueTest(SparsityType.SPARSE, ValueType.CONST, true); + } + + @Test + public void testDenseRandDataNoCompression() { + runGetValueTest(SparsityType.DENSE, ValueType.RAND, false); + } + + @Test + public void testSparseRandDataNoCompression() { + runGetValueTest(SparsityType.SPARSE, ValueType.RAND, false); + } + + @Test + public void testEmptyNoCompression() { + runGetValueTest(SparsityType.EMPTY, ValueType.RAND, false); + } + + @Test + public void testDenseRoundRandDataNoCompression() { + runGetValueTest(SparsityType.DENSE, ValueType.RAND_ROUND, false); + } + + @Test + public void testSparseRoundRandDataNoCompression() { + runGetValueTest(SparsityType.SPARSE, ValueType.RAND_ROUND, false); + } + + @Test + public void testDenseConstDataNoCompression() { + runGetValueTest(SparsityType.DENSE, ValueType.CONST, false); + } + + @Test + public void testSparseConstDataNoCompression() { + runGetValueTest(SparsityType.SPARSE, ValueType.CONST, false); + } + + + /** + * + * @param mb + */ + private void runGetValueTest(SparsityType sptype, ValueType vtype, boolean compress) + { + try + { + //prepare sparsity for input data + double sparsity = -1; + switch( sptype ){ + case DENSE: sparsity = sparsity1; break; + case SPARSE: sparsity = sparsity2; break; + case EMPTY: sparsity = sparsity3; break; + } + + //generate input data + double min = (vtype==ValueType.CONST)? 10 : -10; + double[][] input = TestUtils.generateTestMatrix(rows, cols, min, 10, sparsity, 7); + if( vtype==ValueType.RAND_ROUND ) + input = TestUtils.round(input); + MatrixBlock mb = DataConverter.convertToMatrixBlock(input); + + //compress given matrix block + CompressedMatrixBlock cmb = new CompressedMatrixBlock(mb); + if( compress ) + cmb.compress(); + + //iterate over all cells, get and compare + for(int i=0; i<rows; i++) + for(int j=0; j<cols; j++) { + double ulaVal = mb.getValue(i, j); //calls quickGetValue internally + double claVal = cmb.getValue(i, j); //calls quickGetValue internally + Assert.assertTrue("Get returned wrong value: "+claVal+" (expected: "+ulaVal+")", ulaVal==claVal); + } + } + catch(Exception ex) { + throw new RuntimeException(ex); + } + } +} http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/f85cf16e/src/test_suites/java/org/apache/sysml/test/integration/functions/compress/ZPackageSuite.java ---------------------------------------------------------------------- diff --git a/src/test_suites/java/org/apache/sysml/test/integration/functions/compress/ZPackageSuite.java b/src/test_suites/java/org/apache/sysml/test/integration/functions/compress/ZPackageSuite.java index 62dc46e..c8dc906 100644 --- a/src/test_suites/java/org/apache/sysml/test/integration/functions/compress/ZPackageSuite.java +++ b/src/test_suites/java/org/apache/sysml/test/integration/functions/compress/ZPackageSuite.java @@ -27,6 +27,7 @@ import org.junit.runners.Suite; @RunWith(Suite.class) @Suite.SuiteClasses({ BasicCompressionTest.class, + BasicGetValueTest.class, BasicMatrixAppendTest.class, BasicMatrixMultChainTest.class, BasicMatrixTransposeSelfMultTest.class,
