[SYSTEMML-1029] Fix performance CSR update-in-place left indexing, test Sparse update-in-place matrices are represented in CSR (instead of MCSR) in order to enable shallow serialize because the CSR in-memory size is almost equivalent its serialized representation. This is important because otherwise, the O(n) serialization costs would eliminate the benefits of update-in-place.
However, column-wise CSR updates led to severe performance issues as each row update triggered shifting of all subsequent values leading to O(n^2) shifting costs. This patch adds low-level CSR update routines which require at most O(n) shifting costs for this worst-case access pattern (which is still faster than serialization or copy). Note that the full benefits of append-only update-in-place remain unchanged. Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/2c32dbf5 Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/2c32dbf5 Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/2c32dbf5 Branch: refs/heads/master Commit: 2c32dbf542bf182b59b6143f7b9211b230bbc29d Parents: df9976f Author: Matthias Boehm <mbo...@us.ibm.com> Authored: Wed Oct 12 01:01:51 2016 -0700 Committer: Matthias Boehm <mbo...@us.ibm.com> Committed: Wed Oct 12 14:53:29 2016 -0700 ---------------------------------------------------------------------- .../sysml/runtime/matrix/data/MatrixBlock.java | 13 +- .../runtime/matrix/data/SparseBlockCSR.java | 165 +++++++++++++++++++ .../indexing/LeftIndexingUpdateInPlaceTest.java | 158 ++++++++++++++++++ .../indexing/LeftIndexingUpdateInPlaceTest.R | 35 ++++ .../indexing/LeftIndexingUpdateInPlaceTest.dml | 32 ++++ .../functions/indexing/ZPackageSuite.java | 1 + 6 files changed, 403 insertions(+), 1 deletion(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/2c32dbf5/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 d3de376..5c45360 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 @@ -3953,8 +3953,19 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab result.quickSetValue(rl, cl, src.quickGetValue(0, 0)); } else { //general case + //handle csr sparse blocks separately to avoid repeated shifting on column-wise access + if( !result.isEmptyBlock(false) && result.sparse && result.sparseBlock instanceof SparseBlockCSR ) { + SparseBlockCSR sblock = (SparseBlockCSR) result.sparseBlock; + if( src.sparse ) + sblock.setIndexRange(rl, ru+1, cl, cu+1, src.getSparseBlock()); + else //dense + sblock.setIndexRange(rl, ru+1, cl, cu+1, src.getDenseBlock(), 0, src.getNumRows()*src.getNumColumns()); + result.nonZeros = sblock.size(); + } //copy submatrix into result - result.copy(rl, ru, cl, cu, src, true); + else { + result.copy(rl, ru, cl, cu, src, true); + } } return result; http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/2c32dbf5/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java index 04a6cb7..a26a834 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java @@ -410,6 +410,153 @@ public class SparseBlockCSR extends SparseBlock } incrPtr(r+1, lnnz); } + + /** + * Inserts a sorted row-major array of non-zero values into the row and column + * range [rl,ru) and [cl,cu). Note: that this is a CSR-specific method to address + * performance issues due to repeated re-shifting on update-in-place. + * + * @param rl lower row index, starting at 0, inclusive + * @param ru upper row index, starting at 0, exclusive + * @param cl lower column index, starting at 0, inclusive + * @param cu upper column index, starting at 0, exclusive + * @param v right-hand-side dense block + * @param vix right-hand-side dense block index + * @param vlen right-hand-side dense block value length + */ + public void setIndexRange(int rl, int ru, int cl, int cu, double[] v, int vix, int vlen) { + //step 1: determine output nnz + int nnz = _size - (int)size(rl, ru, cl, cu); + if( v != null ) + for( int i=vix; i<vix+vlen; i++ ) + nnz += (v[i]!=0) ? 1: 0; + + //step 2: reallocate if necessary + if( _values.length < nnz ) + resize(nnz); + + //step 3: insert and overwrite index range + //total shift can be negative or positive and w/ internal skew + + //step 3a: forward pass: compact (delete index range) + int pos = pos(rl); + for( int r=rl; r<ru; r++ ) { + int rpos = pos(r); + int rlen = size(r); + _ptr[r] = pos; + for( int k=rpos; k<rpos+rlen; k++ ) + if( _indexes[k]<cl || cu<=_indexes[k] ) { + _indexes[pos] = _indexes[k]; + _values[pos++] = _values[k]; + } + } + shiftLeftByN(pos(ru), pos(ru)-pos); + decrPtr(ru, pos(ru)-pos); + + //step 3b: backward pass: merge (insert index range) + int tshift1 = nnz - _size; //always non-negative + if( v == null || tshift1==0 ) //early abort + return; + shiftRightByN(pos(ru), tshift1); + incrPtr(ru, tshift1); + pos = pos(ru)-1; + int clen2 = cu-cl; + for( int r=ru-1; r>=rl; r-- ) { + int rpos = pos(r); + int rlen = size(r) - tshift1; + //copy lhs right + int k = -1; + for( k=rpos+rlen-1; k>=rpos && _indexes[k]>=cu; k-- ) { + _indexes[pos] = _indexes[k]; + _values[pos--] = _values[k]; + } + //copy rhs + int voff = vix + (r-rl) * clen2; + for( int k2=clen2-1; k2>=0 & vlen>voff; k2-- ) + if( v[voff+k2] != 0 ) { + _indexes[pos] = cl + k2; + _values[pos--] = v[voff+k2]; + tshift1--; + } + //copy lhs left + for( ; k>=rpos; k-- ) { + _indexes[pos] = _indexes[k]; + _values[pos--] = _values[k]; + } + _ptr[r] = pos+1; + } + } + + /** + * Inserts a sparse block into the row and column range [rl,ru) and [cl,cu). + * Note: that this is a CSR-specific method to address performance issues + * due to repeated re-shifting on update-in-place. + * + * @param rl lower row index, starting at 0, inclusive + * @param ru upper row index, starting at 0, exclusive + * @param cl lower column index, starting at 0, inclusive + * @param cu upper column index, starting at 0, exclusive + * @param sb right-hand-side sparse block + */ + public void setIndexRange(int rl, int ru, int cl, int cu, SparseBlock sb) { + //step 1: determine output nnz + int nnz = (int) (_size - size(rl, ru, cl, cu) + + ((sb!=null) ? sb.size() : 0)); + + //step 2: reallocate if necessary + if( _values.length < nnz ) + resize(nnz); + + //step 3: insert and overwrite index range (backwards) + //total shift can be negative or positive and w/ internal skew + + //step 3a: forward pass: compact (delete index range) + int pos = pos(rl); + for( int r=rl; r<ru; r++ ) { + int rpos = pos(r); + int rlen = size(r); + _ptr[r] = pos; + for( int k=rpos; k<rpos+rlen; k++ ) + if( _indexes[k]<cl || cu<=_indexes[k] ) { + _indexes[pos] = _indexes[k]; + _values[pos++] = _values[k]; + } + } + shiftLeftByN(pos(ru), pos(ru)-pos); + decrPtr(ru, pos(ru)-pos); + + //step 3b: backward pass: merge (insert index range) + int tshift1 = nnz - _size; //always non-negative + if( sb == null || tshift1==0 ) //early abort + return; + shiftRightByN(pos(ru), tshift1); + incrPtr(ru, tshift1); + pos = pos(ru)-1; + for( int r=ru-1; r>=rl; r-- ) { + int rpos = pos(r); + int rlen = size(r) - tshift1; + //copy lhs right + int k = -1; + for( k=rpos+rlen-1; k>=rpos && _indexes[k]>=cu; k-- ) { + _indexes[pos] = _indexes[k]; + _values[pos--] = _values[k]; + } + //copy rhs + int r2 = r-rl; + int r2pos = sb.pos(r2); + for( int k2=r2pos+sb.size(r2)-1; k2>=r2pos; k2-- ) { + _indexes[pos] = cl + sb.indexes(r2)[k2]; + _values[pos--] = sb.values(r2)[k2]; + tshift1--; + } + //copy lhs left + for( ; k>=rpos; k-- ) { + _indexes[pos] = _indexes[k]; + _values[pos--] = _values[k]; + } + _ptr[r] = pos+1; + } + } @Override public void deleteIndexRange(int r, int cl, int cu) { @@ -634,6 +781,11 @@ public class SparseBlockCSR extends SparseBlock _size--; } + /** + * + * @param ix + * @param n + */ private void shiftRightByN(int ix, int n) { //overlapping array copy (shift rhs values right by 1) @@ -645,6 +797,19 @@ public class SparseBlockCSR extends SparseBlock /** * * @param ix + * @param n + */ + private void shiftLeftByN(int ix, int n) + { + //overlapping array copy (shift rhs values left by n) + System.arraycopy(_indexes, ix, _indexes, ix-n, _size-ix); + System.arraycopy(_values, ix, _values, ix-n, _size-ix); + _size -= n; + } + + /** + * + * @param ix * @param c * @param v */ http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/2c32dbf5/src/test/java/org/apache/sysml/test/integration/functions/indexing/LeftIndexingUpdateInPlaceTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/sysml/test/integration/functions/indexing/LeftIndexingUpdateInPlaceTest.java b/src/test/java/org/apache/sysml/test/integration/functions/indexing/LeftIndexingUpdateInPlaceTest.java new file mode 100644 index 0000000..afa2356 --- /dev/null +++ b/src/test/java/org/apache/sysml/test/integration/functions/indexing/LeftIndexingUpdateInPlaceTest.java @@ -0,0 +1,158 @@ +/* + * 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.indexing; + +import java.util.HashMap; + +import org.junit.Test; +import org.apache.sysml.api.DMLScript.RUNTIME_PLATFORM; +import org.apache.sysml.runtime.matrix.MatrixCharacteristics; +import org.apache.sysml.runtime.matrix.data.MatrixValue.CellIndex; +import org.apache.sysml.test.integration.AutomatedTestBase; +import org.apache.sysml.test.integration.TestConfiguration; +import org.apache.sysml.test.utils.TestUtils; + +public class LeftIndexingUpdateInPlaceTest extends AutomatedTestBase +{ + private final static String TEST_DIR = "functions/indexing/"; + private final static String TEST_NAME = "LeftIndexingUpdateInPlaceTest"; + private final static String TEST_CLASS_DIR = TEST_DIR + LeftIndexingUpdateInPlaceTest.class.getSimpleName() + "/"; + + private final static int rows1 = 1281; + private final static int cols1 = 1102; + private final static int cols2 = 226; + private final static int cols3 = 1; + + private final static double sparsity1 = 0.05; + private final static double sparsity2 = 0.9; + + @Override + public void setUp() { + addTestConfiguration(TEST_NAME, new TestConfiguration(TEST_CLASS_DIR, TEST_NAME, new String[] {"R"})); + } + + @Test + public void testSparseMatrixSparseMatrix() { + runLeftIndexingUpdateInPlaceTest(true, true, false, false); + } + + @Test + public void testSparseMatrixSparseVector() { + runLeftIndexingUpdateInPlaceTest(true, true, true, false); + } + + @Test + public void testSparseMatrixDenseMatrix() { + runLeftIndexingUpdateInPlaceTest(true, false, false, false); + } + + @Test + public void testSparseMatrixDenseVector() { + runLeftIndexingUpdateInPlaceTest(true, false, true, false); + } + + @Test + public void testDenseMatrixSparseMatrix() { + runLeftIndexingUpdateInPlaceTest(false, true, false, false); + } + + @Test + public void testDenseMatrixSparseVector() { + runLeftIndexingUpdateInPlaceTest(false, true, true, false); + } + + @Test + public void testDenseMatrixDenseMatrix() { + runLeftIndexingUpdateInPlaceTest(false, false, false, false); + } + + @Test + public void testDenseMatrixDenseVector() { + runLeftIndexingUpdateInPlaceTest(false, false, true, false); + } + + @Test + public void testSparseMatrixEmptyMatrix() { + runLeftIndexingUpdateInPlaceTest(true, true, false, true); + } + + @Test + public void testSparseMatrixEmptyVector() { + runLeftIndexingUpdateInPlaceTest(true, true, true, true); + } + + @Test + public void testDenseMatrixEmptyMatrix() { + runLeftIndexingUpdateInPlaceTest(false, true, false, true); + } + + @Test + public void testDenseMatrixEmptyVector() { + runLeftIndexingUpdateInPlaceTest(false, true, true, true); + } + + + /** + * + * @param sparseM1 + * @param sparseM2 + * @param vectorM2 + */ + public void runLeftIndexingUpdateInPlaceTest(boolean sparseM1, boolean sparseM2, boolean vectorM2, boolean emptyM2) + { + RUNTIME_PLATFORM oldRTP = rtplatform; + rtplatform = RUNTIME_PLATFORM.HYBRID; + + try { + TestConfiguration config = getTestConfiguration(TEST_NAME); + loadTestConfiguration(config); + + double spM1 = sparseM1 ? sparsity1 : sparsity2; + double spM2 = emptyM2 ? 0 : (sparseM2 ? sparsity1 : sparsity2); + int colsM2 = vectorM2 ? cols3 : cols2; + + String HOME = SCRIPT_DIR + TEST_DIR; + fullDMLScriptName = HOME + TEST_NAME + ".dml"; + programArgs = new String[]{"-explain","-args", input("A"), input("B"), output("R")}; + + fullRScriptName = HOME + TEST_NAME + ".R"; + rCmd = "Rscript" + " " + fullRScriptName + " " + + inputDir() + " " + expectedDir(); + + //generate input data sets + double[][] A = getRandomMatrix(rows1, cols1, -1, 1, spM1, 1234); + writeInputMatrixWithMTD("A", A, true); + double[][] B = getRandomMatrix(rows1, colsM2, -1, 1, spM2, 5678); + writeInputMatrixWithMTD("B", B, true); + + //run dml and r script + runTest(true, false, null, 1); + runRScript(true); + + HashMap<CellIndex, Double> dmlfile = readDMLMatrixFromHDFS("R"); + HashMap<CellIndex, Double> rfile = readRMatrixFromFS("R"); + TestUtils.compareMatrices(dmlfile, rfile, 0, "DML", "R"); + checkDMLMetaDataFile("R", new MatrixCharacteristics(rows1,cols1,1,1)); + } + finally { + rtplatform = oldRTP; + } + } +} http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/2c32dbf5/src/test/scripts/functions/indexing/LeftIndexingUpdateInPlaceTest.R ---------------------------------------------------------------------- diff --git a/src/test/scripts/functions/indexing/LeftIndexingUpdateInPlaceTest.R b/src/test/scripts/functions/indexing/LeftIndexingUpdateInPlaceTest.R new file mode 100644 index 0000000..11bed94 --- /dev/null +++ b/src/test/scripts/functions/indexing/LeftIndexingUpdateInPlaceTest.R @@ -0,0 +1,35 @@ +#------------------------------------------------------------- +# +# 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. +# +#------------------------------------------------------------- + + +args <- commandArgs(TRUE) +options(digits=22) +library("Matrix") + +A = as.matrix(readMM(paste(args[1], "A.mtx", sep=""))) +B = as.matrix(readMM(paste(args[1], "B.mtx", sep=""))) + +R = A; +for( i in 1:4 ) { + R[,((1+i)*100):((1+i)*100+ncol(B)-1)] = B; +} + +writeMM(as(R,"CsparseMatrix"), paste(args[2], "R", sep="")) http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/2c32dbf5/src/test/scripts/functions/indexing/LeftIndexingUpdateInPlaceTest.dml ---------------------------------------------------------------------- diff --git a/src/test/scripts/functions/indexing/LeftIndexingUpdateInPlaceTest.dml b/src/test/scripts/functions/indexing/LeftIndexingUpdateInPlaceTest.dml new file mode 100644 index 0000000..4439394 --- /dev/null +++ b/src/test/scripts/functions/indexing/LeftIndexingUpdateInPlaceTest.dml @@ -0,0 +1,32 @@ +#------------------------------------------------------------- +# +# 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. +# +#------------------------------------------------------------- + + +A = read($1); +B = read($2); +R = A; + +#use loop to test update-in-place +for( i in 1:4 ) { + R[,((1+i)*100):((1+i)*100+ncol(B)-1)] = B; +} + +write(R, $3, format="text"); http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/2c32dbf5/src/test_suites/java/org/apache/sysml/test/integration/functions/indexing/ZPackageSuite.java ---------------------------------------------------------------------- diff --git a/src/test_suites/java/org/apache/sysml/test/integration/functions/indexing/ZPackageSuite.java b/src/test_suites/java/org/apache/sysml/test/integration/functions/indexing/ZPackageSuite.java index 1db03cb..76e4832 100644 --- a/src/test_suites/java/org/apache/sysml/test/integration/functions/indexing/ZPackageSuite.java +++ b/src/test_suites/java/org/apache/sysml/test/integration/functions/indexing/ZPackageSuite.java @@ -30,6 +30,7 @@ import org.junit.runners.Suite; LeftIndexingSparseDenseTest.class, LeftIndexingSparseSparseTest.class, LeftIndexingTest.class, + LeftIndexingUpdateInPlaceTest.class, RightIndexingMatrixTest.class, RightIndexingVectorTest.class,
