You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@systemml.apache.org by mb...@apache.org on 2017/04/22 21:46:10 UTC
incubator-systemml git commit: [SYSTEMML-1548] Memory efficiency
ultra-sparse matrices in MCSR format
Repository: incubator-systemml
Updated Branches:
refs/heads/master b481324d0 -> dd373ee01
[SYSTEMML-1548] Memory efficiency ultra-sparse matrices in MCSR format
This patch improves the memory efficiency of our default MCSR sparse
block format for ultra-sparse matrices including permutation and
selection matrices. MCSR is our default format because it allows for
efficient multi-threaded incremental construction. However, instead of
always using sparse row vectors (which have an overhead of about 120
bytes for meta data and array headers in addition to the pointer and
object), we now adaptively use either sparse row scalars (single
index-value pair) or sparse row vectors. For permutation matrices, all
rows are encoded as such sparse row scalars which significantly reduces
the size overhead and thus, garbage collection overheads.
Note that this patch does not tighten the respective memory estimates
yet in order to make the compiler independent from these adaptive
runtime decisions - however the adaptive policy is guaranteed to have a
smaller or equal memory footprint.
Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/dd373ee0
Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/dd373ee0
Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/dd373ee0
Branch: refs/heads/master
Commit: dd373ee013ca4b1ff004a59263d37d4562ef2d79
Parents: b481324
Author: Matthias Boehm <mb...@gmail.com>
Authored: Fri Apr 21 23:21:23 2017 -0700
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Sat Apr 22 14:46:15 2017 -0700
----------------------------------------------------------------------
.../parfor/opt/OptimizerRuleBased.java | 6 +-
.../runtime/matrix/data/LibMatrixBincell.java | 6 +-
.../sysml/runtime/matrix/data/MatrixBlock.java | 2 +-
.../runtime/matrix/data/SparseBlockCOO.java | 2 +-
.../runtime/matrix/data/SparseBlockCSR.java | 2 +-
.../runtime/matrix/data/SparseBlockMCSR.java | 63 ++-
.../sysml/runtime/matrix/data/SparseRow.java | 444 +++----------------
.../runtime/matrix/data/SparseRowScalar.java | 101 +++++
.../runtime/matrix/data/SparseRowVector.java | 396 +++++++++++++++++
9 files changed, 620 insertions(+), 402 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/dd373ee0/src/main/java/org/apache/sysml/runtime/controlprogram/parfor/opt/OptimizerRuleBased.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/controlprogram/parfor/opt/OptimizerRuleBased.java b/src/main/java/org/apache/sysml/runtime/controlprogram/parfor/opt/OptimizerRuleBased.java
index 851e193..1a8122a 100644
--- a/src/main/java/org/apache/sysml/runtime/controlprogram/parfor/opt/OptimizerRuleBased.java
+++ b/src/main/java/org/apache/sysml/runtime/controlprogram/parfor/opt/OptimizerRuleBased.java
@@ -103,7 +103,7 @@ import org.apache.sysml.runtime.matrix.MatrixCharacteristics;
import org.apache.sysml.runtime.matrix.MatrixFormatMetaData;
import org.apache.sysml.runtime.matrix.data.MatrixBlock;
import org.apache.sysml.runtime.matrix.data.OutputInfo;
-import org.apache.sysml.runtime.matrix.data.SparseRow;
+import org.apache.sysml.runtime.matrix.data.SparseRowVector;
import org.apache.sysml.utils.Explain;
import org.apache.sysml.yarn.ropt.YarnClusterAnalyzer;
@@ -750,13 +750,13 @@ public class OptimizerRuleBased extends Optimizer
private double estimateSizeSparseRow( long cols, long nnz ) {
//see MatrixBlock.estimateSizeSparseInMemory
- long cnnz = Math.max(SparseRow.initialCapacity, Math.max(cols, nnz));
+ long cnnz = Math.max(SparseRowVector.initialCapacity, Math.max(cols, nnz));
return ( 116 + 12 * cnnz ); //sparse row
}
private double estimateSizeSparseRowMin( long cols ) {
//see MatrixBlock.estimateSizeSparseInMemory
- long cnnz = Math.min(SparseRow.initialCapacity, cols);
+ long cnnz = Math.min(SparseRowVector.initialCapacity, cols);
return ( 116 + 12 * cnnz ); //sparse row
}
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/dd373ee0/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java
index 15d6e70..4542882 100644
--- a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java
+++ b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java
@@ -924,7 +924,7 @@ public class LibMatrixBincell
if( copyOnes ) { //SPECIAL CASE: e.g., (X != 0)
//create sparse row without repeated resizing
- SparseRow crow = new SparseRow(alen);
+ SparseRowVector crow = new SparseRowVector(alen);
crow.setSize(alen);
//memcopy/memset of indexes/values (sparseblock guarantees absence of 0s)
@@ -1082,7 +1082,7 @@ public class LibMatrixBincell
//temp
SparseRow thisRow = c.get(r);
- c.set(r, new SparseRow(estimateSize, clen), false);
+ c.set(r, new SparseRowVector(estimateSize, clen), false);
if(thisRow!=null)
{
@@ -1105,7 +1105,7 @@ public class LibMatrixBincell
for(int r=0; r<rlen; r++)
{
if( !b.isEmpty(r) ) {
- SparseRow tmp = new SparseRow( b.size(r), clen );
+ SparseRow tmp = new SparseRowVector( b.size(r), clen );
appendRightForSparseBinary(op, b.values(r), b.indexes(r), b.pos(r), b.size(r), 0, r, m1ret);
m1ret.sparseBlock.set(r, tmp, false);
}
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/dd373ee0/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 70c25a0..f5d0a45 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
@@ -730,7 +730,7 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab
int len = b.size(i);
int[] ix = b.indexes(i);
double[] val = b.values(i);
- sparseBlock.allocate(aix, estimatedNNzsPerRow, clen);
+ sparseBlock.allocate(aix, sparseBlock.size(aix)+len);
for( int j=pos; j<pos+len; j++ )
sparseBlock.append(aix, coloffset+ix[j], val[j]);
}
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/dd373ee0/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 77f450b..9ca9418 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
@@ -417,7 +417,7 @@ public class SparseBlockCOO extends SparseBlock
int pos = pos(r);
int len = size(r);
- SparseRow row = new SparseRow(len);
+ SparseRowVector row = new SparseRowVector(len);
System.arraycopy(_cindexes, pos, row.indexes(), 0, len);
System.arraycopy(_values, pos, row.values(), 0, len);
row.setSize(len);
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/dd373ee0/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 02f009a..9ddff9e 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
@@ -639,7 +639,7 @@ public class SparseBlockCSR extends SparseBlock
int pos = pos(r);
int len = size(r);
- SparseRow row = new SparseRow(len);
+ SparseRowVector row = new SparseRowVector(len);
System.arraycopy(_indexes, pos, row.indexes(), 0, len);
System.arraycopy(_values, pos, row.values(), 0, len);
row.setSize(len);
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/dd373ee0/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockMCSR.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockMCSR.java b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockMCSR.java
index 35e38c9..9952fab 100644
--- a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockMCSR.java
+++ b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockMCSR.java
@@ -47,7 +47,7 @@ public class SparseBlockMCSR extends SparseBlock
SparseRow[] orows = ((SparseBlockMCSR)sblock)._rows;
_rows = new SparseRow[orows.length];
for( int i=0; i<_rows.length; i++ )
- _rows[i] = new SparseRow(orows[i]);
+ _rows[i] = new SparseRowVector(orows[i]);
}
//general case SparseBlock
else {
@@ -56,8 +56,8 @@ public class SparseBlockMCSR extends SparseBlock
if( !sblock.isEmpty(i) ) {
int apos = sblock.pos(i);
int alen = sblock.size(i);
- _rows[i] = new SparseRow(alen);
- _rows[i].setSize(alen);
+ _rows[i] = new SparseRowVector(alen);
+ ((SparseRowVector)_rows[i]).setSize(alen);
System.arraycopy(sblock.indexes(i), apos, _rows[i].indexes(), 0, alen);
System.arraycopy(sblock.values(i), apos, _rows[i].values(), 0, alen);
}
@@ -74,8 +74,11 @@ public class SparseBlockMCSR extends SparseBlock
public SparseBlockMCSR(SparseRow[] rows, boolean deep) {
if( deep ) {
_rows = new SparseRow[rows.length];
- for( int i=0; i<_rows.length; i++ )
- _rows[i] = new SparseRow(rows[i]);
+ for( int i=0; i<_rows.length; i++ ) {
+ _rows[i] = (rows[i].size()==1) ? new SparseRowScalar(
+ rows[i].indexes()[0], rows[i].values()[0]) :
+ new SparseRowVector(rows[i]);
+ }
}
else {
_rows = rows;
@@ -96,7 +99,7 @@ public class SparseBlockMCSR extends SparseBlock
* @return memory estimate
*/
public static long estimateMemory(long nrows, long ncols, double sparsity) {
- double cnnz = Math.max(SparseRow.initialCapacity, Math.ceil(sparsity*ncols));
+ double cnnz = Math.max(SparseRowVector.initialCapacity, Math.ceil(sparsity*ncols));
double rlen = Math.min(nrows, Math.ceil(sparsity*nrows*ncols));
//Each sparse row has a fixed overhead of 8B (reference) + 32B (object) +
@@ -118,19 +121,21 @@ public class SparseBlockMCSR extends SparseBlock
@Override
public void allocate(int r) {
if( _rows[r] == null )
- _rows[r] = new SparseRow();
+ _rows[r] = new SparseRowVector();
}
@Override
public void allocate(int r, int nnz) {
- if( _rows[r] == null )
- _rows[r] = new SparseRow(nnz);
+ if( _rows[r] == null ) {
+ _rows[r] = (nnz == 1) ? new SparseRowScalar() :
+ new SparseRowVector(nnz);
+ }
}
@Override
public void allocate(int r, int ennz, int maxnnz) {
if( _rows[r] == null )
- _rows[r] = new SparseRow(ennz, maxnnz);
+ _rows[r] = new SparseRowVector(ennz, maxnnz);
}
@Override
@@ -181,7 +186,6 @@ public class SparseBlockMCSR extends SparseBlock
@Override
public int size(int r) {
//prior check with isEmpty(r) expected
- //TODO perf sparse block
return (_rows[r]!=null) ? _rows[r].size() : 0;
}
@@ -231,41 +235,50 @@ public class SparseBlockMCSR extends SparseBlock
@Override
public boolean set(int r, int c, double v) {
if( _rows[r] == null )
- _rows[r] = new SparseRow();
+ _rows[r] = new SparseRowScalar();
+ else if( _rows[r] instanceof SparseRowScalar && !_rows[r].isEmpty())
+ _rows[r] = new SparseRowVector(_rows[r]);
return _rows[r].set(c, v);
}
@Override
public void set(int r, SparseRow row, boolean deep) {
//copy values into existing row to avoid allocation
- if( _rows[r] != null && _rows[r].capacity() >= row.size() && deep )
- _rows[r].copy(row);
+ if( _rows[r] != null && _rows[r] instanceof SparseRowVector
+ && ((SparseRowVector)_rows[r]).capacity() >= row.size() && deep )
+ ((SparseRowVector)_rows[r]).copy(row);
//set new sparse row (incl allocation if required)
else
_rows[r] = (deep && row != null) ?
- new SparseRow(row) : row;
+ new SparseRowVector(row) : row;
}
@Override
public void append(int r, int c, double v) {
if( _rows[r] == null )
- _rows[r] = new SparseRow();
+ _rows[r] = new SparseRowScalar();
+ else if( _rows[r] instanceof SparseRowScalar && !_rows[r].isEmpty() )
+ _rows[r] = new SparseRowVector(_rows[r]);
_rows[r].append(c, v);
}
@Override
public void setIndexRange(int r, int cl, int cu, double[] v, int vix, int len) {
if( _rows[r] == null )
- _rows[r] = new SparseRow();
+ _rows[r] = new SparseRowVector();
+ else if( _rows[r] instanceof SparseRowScalar )
+ _rows[r] = new SparseRowVector(_rows[r]);
//different sparse row semantics: upper bound inclusive
- _rows[r].setIndexRange(cl, cu-1, v, vix, len);
+ ((SparseRowVector)_rows[r]).setIndexRange(cl, cu-1, v, vix, len);
}
@Override
public void deleteIndexRange(int r, int cl, int cu) {
//prior check with isEmpty(r) expected
//different sparse row semantics: upper bound inclusive
- _rows[r].deleteIndexRange(cl, cu-1);
+ if( _rows[r] instanceof SparseRowScalar )
+ _rows[r] = new SparseRowVector(_rows[r]);
+ ((SparseRowVector)_rows[r]).deleteIndexRange(cl, cu-1);
}
@Override
@@ -296,19 +309,25 @@ public class SparseBlockMCSR extends SparseBlock
@Override
public int posFIndexLTE(int r, int c) {
//prior check with isEmpty(r) expected
- return _rows[r].searchIndexesFirstLTE(c);
+ if( _rows[r] instanceof SparseRowScalar )
+ _rows[r] = new SparseRowVector(_rows[r]);
+ return ((SparseRowVector)_rows[r]).searchIndexesFirstLTE(c);
}
@Override
public int posFIndexGTE(int r, int c) {
//prior check with isEmpty(r) expected
- return _rows[r].searchIndexesFirstGTE(c);
+ if( _rows[r] instanceof SparseRowScalar )
+ _rows[r] = new SparseRowVector(_rows[r]);
+ return ((SparseRowVector)_rows[r]).searchIndexesFirstGTE(c);
}
@Override
public int posFIndexGT(int r, int c) {
//prior check with isEmpty(r) expected
- return _rows[r].searchIndexesFirstGT(c);
+ if( _rows[r] instanceof SparseRowScalar )
+ _rows[r] = new SparseRowVector(_rows[r]);
+ return ((SparseRowVector)_rows[r]).searchIndexesFirstGT(c);
}
@Override
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/dd373ee0/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRow.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRow.java b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRow.java
index b90c5bc..2ce2d87 100644
--- a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRow.java
+++ b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRow.java
@@ -21,406 +21,108 @@
package org.apache.sysml.runtime.matrix.data;
import java.io.Serializable;
-import java.util.Arrays;
-import org.apache.sysml.runtime.util.SortUtils;
-
-public class SparseRow implements Serializable
+/**
+ * Base class for sparse row implementations such as sparse
+ * row vectors and sparse scalars (single value per row).
+ *
+ */
+public abstract class SparseRow implements Serializable
{
private static final long serialVersionUID = 5806895317005796456L;
- //initial capacity of any created sparse row
- //WARNING: be aware that this affects the core memory estimates (incl. implicit assumptions)!
- public static final int initialCapacity = 4;
-
- private int estimatedNzs = initialCapacity;
- private int maxNzs = Integer.MAX_VALUE;
- private int size = 0;
- private double[] values = null;
- private int[] indexes = null;
-
- public SparseRow() {
- this(initialCapacity);
- }
-
- public SparseRow(int capacity)
- {
- estimatedNzs = capacity;
- values = new double[capacity];
- indexes = new int[capacity];
- }
-
- public SparseRow(int estnnz, int maxnnz)
- {
- if( estnnz > initialCapacity )
- estimatedNzs = estnnz;
- maxNzs = maxnnz;
- int capacity = ((estnnz<initialCapacity && estnnz>0) ?
- estnnz : initialCapacity);
- values = new double[capacity];
- indexes = new int[capacity];
- }
-
- public SparseRow(SparseRow that)
- {
- size = that.size;
- int cap = Math.max(initialCapacity, that.size);
-
- //allocate arrays and copy new values
- values = Arrays.copyOf(that.values, cap);
- indexes = Arrays.copyOf(that.indexes, cap);
- }
-
- public int size() {
- return size;
- }
-
- public void setSize(int newsize) {
- size = newsize;
- }
-
- public boolean isEmpty() {
- return (size == 0);
- }
-
- public double[] values() {
- return values;
- }
+ /**
+ * Get the number of non-zero values of the sparse row.
+ *
+ * @return number of non-zeros
+ */
+ public abstract int size();
- public int[] indexes() {
- return indexes;
- }
+ /**
+ * Indicates if the sparse row is empty, i.e., if is has
+ * size zero.
+ *
+ * @return true if empty
+ */
+ public abstract boolean isEmpty();
- public void setValues(double[] d) {
- values = d;
- }
+ /**
+ * Get the value array of non-zero entries, co-aligned
+ * with the array of indexes.
+ *
+ * @return array of values
+ */
+ public abstract double[] values();
- public void setIndexes(int[] i) {
- indexes = i;
- }
+ /**
+ * Get the index array of non-zero entries, co-aligned
+ * with the array of values.
+ *
+ * @return array of indexes
+ */
+ public abstract int[] indexes();
- public int capacity() {
- return values.length;
- }
-
- public void copy(SparseRow that)
- {
- //note: no recap (if required) + copy, in order to prevent unnecessary copy of old values
- //in case we have to reallocate the arrays
-
- if( values.length < that.size ) {
- //reallocate arrays and copy new values
- values = Arrays.copyOf(that.values, that.size);
- indexes = Arrays.copyOf(that.indexes, that.size);
- }
- else {
- //copy new values
- System.arraycopy(that.values, 0, values, 0, that.size);
- System.arraycopy(that.indexes, 0, indexes, 0, that.size);
- }
- size = that.size;
- }
-
- public void reset(int estnns, int maxnns)
- {
- estimatedNzs = estnns;
- maxNzs = maxnns;
- size = 0;
- }
-
- public void recap(int newCap)
- {
- if( newCap<=values.length )
- return;
-
- //reallocate arrays and copy old values
- values = Arrays.copyOf(values, newCap);
- indexes = Arrays.copyOf(indexes, newCap);
- }
+ /**
+ * Resets the sparse row to empty, after this call size and
+ * isEmpty are guaranteed to return 0 and true, respectively.
+ *
+ * @param estnns estimated number of non-zeros
+ * @param maxnns maximum number of non-zeros, e.g., number of columns
+ */
+ public abstract void reset(int estnns, int maxnns);
/**
- * Heuristic for resizing:
- * doubling before capacity reaches estimated nonzeros, then 1.1x after that for default behavior: always 1.1x
- * (both with exponential size increase for log N steps of reallocation and shifting)
+ * Sets the value of a specified column with awareness of
+ * potential overwrites or deletes (set to value zero).
*
- * @return new capacity for resizing
+ * @param col column index, zero-based
+ * @param v value
+ * @return true if the size of the sparse row changed
*/
- private int newCapacity()
- {
- if( values.length < estimatedNzs )
- return Math.min(estimatedNzs, values.length*2);
- else
- return (int) Math.min(maxNzs, Math.ceil((double)(values.length)*1.1));
- }
-
+ public abstract boolean set(int col, double v);
+
/**
- * In-place compaction of non-zero-entries; removes zero entries and
- * shifts non-zero entries to the left if necessary.
+ * Appends a value to the end of the sparse row.
+ *
+ * @param col column index, zero-based
+ * @param v value
*/
- public void compact()
- {
- int nnz = 0;
- for( int i=0; i<size; i++ )
- if( values[i] != 0 ){
- values[nnz] = values[i];
- indexes[nnz] = indexes[i];
- nnz++;
- }
- size = nnz; //adjust row size
- }
-
- public boolean set(int col, double v)
- {
- //search for existing col index
- int index = Arrays.binarySearch(indexes, 0, size, col);
- if( index >= 0 ) {
- //delete/overwrite existing value (on value delete, we shift
- //left for (1) correct nnz maintenance, and (2) smaller size)
- if( v == 0 ) {
- shiftLeftAndDelete(index);
- return true; // nnz--
- }
- else {
- values[index] = v;
- return false;
- }
- }
-
- //early abort on zero (if no overwrite)
- if( v==0.0 ) {
- return false;
- }
-
- //insert new index-value pair
- index = Math.abs( index+1 );
- if( size==values.length )
- resizeAndInsert(index, col, v);
- else
- shiftRightAndInsert(index, col, v);
- return true; // nnz++
- }
-
- public void append(int col, double v)
- {
- //early abort on zero
- if( v==0.0 ) {
- return;
- }
-
- //resize if required
- if( size==values.length )
- recap(newCapacity());
-
- //append value at end
- values[size] = v;
- indexes[size] = col;
- size++;
- }
-
- public double get(int col)
- {
- //search for existing col index
- int index = Arrays.binarySearch(indexes, 0, size, col);
- if( index >= 0 )
- return values[index];
- else
- return 0;
- }
-
- public int searchIndexesFirstLTE(int col)
- {
- //search for existing col index
- int index = Arrays.binarySearch(indexes, 0, size, col);
- if( index >= 0 ) {
- if( index < size )
- return index;
- else
- return -1;
- }
-
- //search lt col index (see binary search)
- index = Math.abs( index+1 );
- if( index-1 < size )
- return index-1;
- else
- return -1;
- }
-
- public int searchIndexesFirstGTE(int col)
- {
- //search for existing col index
- int index = Arrays.binarySearch(indexes, 0, size, col);
- if( index >= 0 ) {
- if( index < size )
- return index;
- else
- return -1;
- }
-
- //search gt col index (see binary search)
- index = Math.abs( index+1 );
- if( index < size )
- return index;
- else
- return -1;
- }
-
- public int searchIndexesFirstGT(int col)
- {
- //search for existing col index
- int index = Arrays.binarySearch(indexes, 0, size, col);
- if( index >= 0 ) {
- if( index+1 < size )
- return index+1;
- else
- return -1;
- }
-
- //search gt col index (see binary search)
- index = Math.abs( index+1 );
- if( index < size )
- return index;
- else
- return -1;
- }
-
- public void deleteIndexRange(int lowerCol, int upperCol)
- {
- int start = searchIndexesFirstGTE(lowerCol);
- if( start < 0 ) //nothing to delete
- return;
-
- int end = searchIndexesFirstGT(upperCol);
- if( end < 0 ) //delete all remaining
- end = size;
-
- //overlapping array copy (shift rhs values left)
- System.arraycopy(values, end, values, start, size-end);
- System.arraycopy(indexes, end, indexes, start, size-end);
- size -= (end-start);
- }
+ public abstract void append(int col, double v);
/**
- * Inserts a dense vector into a column range; calling this methods helps to
- * avoid repeated shifting of remaining values/indexes for every set value.
+ * Gets the value of a specified column. If the column
+ * index does not exist in the sparse row, this call
+ * returns zero.
*
- * @param lowerCol lower column index
- * @param upperCol upper column index
- * @param v dense vector
- * @param vix ?
- * @param len ?
+ * @param col column index, zero-based
+ * @return value
*/
- public void setIndexRange(int lowerCol, int upperCol, double[] v, int vix, int len)
- {
- int start = searchIndexesFirstGTE(lowerCol);
- if( start < 0 ) { //nothing to delete/shift
- for( int i=vix; i<vix+len; i++ )
- append(lowerCol+i-vix, v[i]);
- return;
- }
-
- int end = searchIndexesFirstGT(upperCol);
- if( end < 0 ) { //delete all remaining
- size = start;
- for( int i=vix; i<vix+len; i++ )
- append(lowerCol+i-vix, v[i]);
- return;
- }
-
- //determine input nnz
- int lnnz = 0;
- for( int i=vix; i<vix+len; i++ )
- lnnz += ( v[i] != 0 ) ? 1 : 0;
-
- //prepare free space (allocate and shift)
- int lsize = size+lnnz-(end-start);
- if( values.length < lsize )
- recap(lsize);
- shiftRightByN(end, lnnz-(end-start));
-
- //insert values
- for( int i=vix, pos=start; i<vix+len; i++ )
- if( v[i] != 0 ) {
- values[ pos ] = v[i];
- indexes[ pos ] = lowerCol+i-vix;
- pos++;
- }
- }
-
- private void resizeAndInsert(int index, int col, double v)
- {
- //allocate new arrays
- int newCap = newCapacity();
- double[] oldvalues = values;
- int[] oldindexes = indexes;
- values = new double[newCap];
- indexes = new int[newCap];
-
- //copy lhs values to new array
- System.arraycopy(oldvalues, 0, values, 0, index);
- System.arraycopy(oldindexes, 0, indexes, 0, index);
-
- //insert new value
- indexes[index] = col;
- values[index] = v;
-
- //copy rhs values to new array
- System.arraycopy(oldvalues, index, values, index+1, size-index);
- System.arraycopy(oldindexes, index, indexes, index+1, size-index);
- size++;
- }
-
- private void shiftRightAndInsert(int index, int col, double v)
- {
- //overlapping array copy (shift rhs values right by 1)
- System.arraycopy(values, index, values, index+1, size-index);
- System.arraycopy(indexes, index, indexes, index+1, size-index);
-
- //insert new value
- values[index] = v;
- indexes[index] = col;
- size++;
- }
-
- private void shiftRightByN(int index, int n)
- {
- //overlapping array copy (shift rhs values right by 1)
- System.arraycopy(values, index, values, index+n, size-index);
- System.arraycopy(indexes, index, indexes, index+n, size-index);
- size += n;
- }
-
- private void shiftLeftAndDelete(int index)
- {
- //overlapping array copy (shift rhs values left by 1)
- System.arraycopy(values, index+1, values, index, size-index-1);
- System.arraycopy(indexes, index+1, indexes, index, size-index-1);
- size--;
- }
+ public abstract double get(int col);
/**
* In-place sort of column-index value pairs in order to allow binary search
* after constant-time append was used for reading unordered sparse rows. We
* first check if already sorted and subsequently sort if necessary in order
- * to get O(n) bestcase.
+ * to get O(n) best case.
*
- * Note: In-place sort necessary in order to guarantee the memory estimate
+ * Note: In-place sort is necessary in order to guarantee the memory estimate
* for operations that implicitly read that data set.
*/
- public void sort()
- {
- if( size<=100 || !SortUtils.isSorted(0, size, indexes) )
- SortUtils.sortByIndex(0, size, indexes, values);
- }
-
+ public abstract void sort();
+
+ /**
+ * In-place compaction of non-zero-entries; removes zero entries
+ * and shifts non-zero entries to the left if necessary.
+ */
+ public abstract void compact();
+
@Override
- public String toString()
- {
+ public String toString() {
StringBuilder sb = new StringBuilder();
- for(int i=0; i<size; i++) {
- sb.append(indexes[i]);
+ for(int i=0; i<size(); i++) {
+ sb.append(indexes()[i]);
sb.append(": ");
- sb.append(values[i]);
+ sb.append(values()[i]);
sb.append("\t");
}
return sb.toString();
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/dd373ee0/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRowScalar.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRowScalar.java b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRowScalar.java
new file mode 100644
index 0000000..a86eee9
--- /dev/null
+++ b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRowScalar.java
@@ -0,0 +1,101 @@
+/*
+ * 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.runtime.matrix.data;
+
+import java.io.Serializable;
+
+public final class SparseRowScalar extends SparseRow implements Serializable
+{
+ private static final long serialVersionUID = 722193514969067477L;
+
+ private int index;
+ private double value;
+
+ public SparseRowScalar() {
+ index = -1;
+ value = 0;
+ }
+
+ public SparseRowScalar(int ix, double val) {
+ index = ix;
+ value = val;
+ }
+
+ @Override
+ public int size() {
+ return (index < 0) ? 0 : 1;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return (index < 0);
+ }
+
+ @Override
+ public double[] values() {
+ return new double[]{value};
+ }
+
+ public int[] indexes() {
+ return new int[]{index};
+ }
+
+ @Override
+ public void reset(int estnns, int maxnns) {
+ index = -1;
+ }
+
+ @Override
+ public boolean set(int col, double v) {
+ boolean ret = (index==col && v==0
+ || index<0 && v!=0);
+ if( index >= 0 && index != col )
+ throw new RuntimeException(
+ "Invalid set to sparse row scalar.");
+ index = (v!=0) ? col : -1;
+ value = v;
+ return ret;
+ }
+
+ @Override
+ public void append(int col, double v) {
+ if( v == 0 )
+ return;
+ if( index >= 0 )
+ throw new RuntimeException(
+ "Invalid append to sparse row scalar.");
+ index = col;
+ value = v;
+ }
+
+ public double get(int col) {
+ return (index==col) ? value : 0;
+ }
+
+ public void sort() {
+ //do nothing
+ }
+
+ @Override
+ public void compact() {
+ index = (value!=0) ? index : -1;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/dd373ee0/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRowVector.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRowVector.java b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRowVector.java
new file mode 100644
index 0000000..1c160b2
--- /dev/null
+++ b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRowVector.java
@@ -0,0 +1,396 @@
+/*
+ * 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.runtime.matrix.data;
+
+import java.io.Serializable;
+import java.util.Arrays;
+
+import org.apache.sysml.runtime.util.SortUtils;
+
+public final class SparseRowVector extends SparseRow implements Serializable
+{
+ private static final long serialVersionUID = 2971077474424464992L;
+
+ //initial capacity of any created sparse row
+ //WARNING: be aware that this affects the core memory estimates (incl. implicit assumptions)!
+ public static final int initialCapacity = 4;
+
+ private int estimatedNzs = initialCapacity;
+ private int maxNzs = Integer.MAX_VALUE;
+ private int size = 0;
+ private double[] values = null;
+ private int[] indexes = null;
+
+ public SparseRowVector() {
+ this(initialCapacity);
+ }
+
+ public SparseRowVector(int capacity) {
+ estimatedNzs = capacity;
+ values = new double[capacity];
+ indexes = new int[capacity];
+ }
+
+ public SparseRowVector(int estnnz, int maxnnz) {
+ if( estnnz > initialCapacity )
+ estimatedNzs = estnnz;
+ maxNzs = maxnnz;
+ int capacity = ((estnnz<initialCapacity && estnnz>0) ?
+ estnnz : initialCapacity);
+ values = new double[capacity];
+ indexes = new int[capacity];
+ }
+
+ public SparseRowVector(SparseRow that) {
+ size = that.size();
+ int cap = Math.max(initialCapacity, that.size());
+
+ //allocate arrays and copy new values
+ values = Arrays.copyOf(that.values(), cap);
+ indexes = Arrays.copyOf(that.indexes(), cap);
+ }
+
+ @Override
+ public int size() {
+ return size;
+ }
+
+ public void setSize(int newsize) {
+ size = newsize;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return (size == 0);
+ }
+
+ @Override
+ public double[] values() {
+ return values;
+ }
+
+ @Override
+ public int[] indexes() {
+ return indexes;
+ }
+
+ public void setValues(double[] d) {
+ values = d;
+ }
+
+ public void setIndexes(int[] i) {
+ indexes = i;
+ }
+
+ public int capacity() {
+ return values.length;
+ }
+
+ public void copy(SparseRow that)
+ {
+ //note: no recap (if required) + copy, in order to prevent unnecessary copy of old values
+ //in case we have to reallocate the arrays
+
+ int thatSize = that.size();
+ if( values.length < thatSize ) {
+ //reallocate arrays and copy new values
+ values = Arrays.copyOf(that.values(), thatSize);
+ indexes = Arrays.copyOf(that.indexes(), thatSize);
+ }
+ else {
+ //copy new values
+ System.arraycopy(that.values(), 0, values, 0, thatSize);
+ System.arraycopy(that.indexes(), 0, indexes, 0, thatSize);
+ }
+ size = thatSize;
+ }
+
+ @Override
+ public void reset(int estnns, int maxnns) {
+ estimatedNzs = estnns;
+ maxNzs = maxnns;
+ size = 0;
+ }
+
+ private void recap(int newCap) {
+ if( newCap<=values.length )
+ return;
+
+ //reallocate arrays and copy old values
+ values = Arrays.copyOf(values, newCap);
+ indexes = Arrays.copyOf(indexes, newCap);
+ }
+
+ /**
+ * Heuristic for resizing:
+ * doubling before capacity reaches estimated nonzeros, then 1.1x after that for default behavior: always 1.1x
+ * (both with exponential size increase for log N steps of reallocation and shifting)
+ *
+ * @return new capacity for resizing
+ */
+ private int newCapacity() {
+ if( values.length < estimatedNzs )
+ return Math.min(estimatedNzs, values.length*2);
+ else
+ return (int) Math.min(maxNzs, Math.ceil((double)(values.length)*1.1));
+ }
+
+ @Override
+ public boolean set(int col, double v) {
+ //search for existing col index
+ int index = Arrays.binarySearch(indexes, 0, size, col);
+ if( index >= 0 ) {
+ //delete/overwrite existing value (on value delete, we shift
+ //left for (1) correct nnz maintenance, and (2) smaller size)
+ if( v == 0 ) {
+ shiftLeftAndDelete(index);
+ return true; // nnz--
+ }
+ else {
+ values[index] = v;
+ return false;
+ }
+ }
+
+ //early abort on zero (if no overwrite)
+ if( v==0.0 )
+ return false;
+
+ //insert new index-value pair
+ index = Math.abs( index+1 );
+ if( size==values.length )
+ resizeAndInsert(index, col, v);
+ else
+ shiftRightAndInsert(index, col, v);
+ return true; // nnz++
+ }
+
+ @Override
+ public void append(int col, double v) {
+ //early abort on zero
+ if( v==0.0 )
+ return;
+
+ //resize if required
+ if( size==values.length )
+ recap(newCapacity());
+
+ //append value at end
+ values[size] = v;
+ indexes[size] = col;
+ size++;
+ }
+
+ @Override
+ public double get(int col) {
+ //search for existing col index
+ int index = Arrays.binarySearch(indexes, 0, size, col);
+ if( index >= 0 )
+ return values[index];
+ else
+ return 0;
+ }
+
+ public int searchIndexesFirstLTE(int col)
+ {
+ //search for existing col index
+ int index = Arrays.binarySearch(indexes, 0, size, col);
+ if( index >= 0 ) {
+ if( index < size )
+ return index;
+ else
+ return -1;
+ }
+
+ //search lt col index (see binary search)
+ index = Math.abs( index+1 );
+ if( index-1 < size )
+ return index-1;
+ else
+ return -1;
+ }
+
+ public int searchIndexesFirstGTE(int col)
+ {
+ //search for existing col index
+ int index = Arrays.binarySearch(indexes, 0, size, col);
+ if( index >= 0 ) {
+ if( index < size )
+ return index;
+ else
+ return -1;
+ }
+
+ //search gt col index (see binary search)
+ index = Math.abs( index+1 );
+ if( index < size )
+ return index;
+ else
+ return -1;
+ }
+
+ public int searchIndexesFirstGT(int col)
+ {
+ //search for existing col index
+ int index = Arrays.binarySearch(indexes, 0, size, col);
+ if( index >= 0 ) {
+ if( index+1 < size )
+ return index+1;
+ else
+ return -1;
+ }
+
+ //search gt col index (see binary search)
+ index = Math.abs( index+1 );
+ if( index < size )
+ return index;
+ else
+ return -1;
+ }
+
+ public void deleteIndexRange(int lowerCol, int upperCol)
+ {
+ int start = searchIndexesFirstGTE(lowerCol);
+ if( start < 0 ) //nothing to delete
+ return;
+
+ int end = searchIndexesFirstGT(upperCol);
+ if( end < 0 ) //delete all remaining
+ end = size;
+
+ //overlapping array copy (shift rhs values left)
+ System.arraycopy(values, end, values, start, size-end);
+ System.arraycopy(indexes, end, indexes, start, size-end);
+ size -= (end-start);
+ }
+
+ /**
+ * Inserts a dense vector into a column range; calling this methods helps to
+ * avoid repeated shifting of remaining values/indexes for every set value.
+ *
+ * @param lowerCol lower column index
+ * @param upperCol upper column index
+ * @param v dense vector
+ * @param vix ?
+ * @param len ?
+ */
+ public void setIndexRange(int lowerCol, int upperCol, double[] v, int vix, int len)
+ {
+ int start = searchIndexesFirstGTE(lowerCol);
+ if( start < 0 ) { //nothing to delete/shift
+ for( int i=vix; i<vix+len; i++ )
+ append(lowerCol+i-vix, v[i]);
+ return;
+ }
+
+ int end = searchIndexesFirstGT(upperCol);
+ if( end < 0 ) { //delete all remaining
+ size = start;
+ for( int i=vix; i<vix+len; i++ )
+ append(lowerCol+i-vix, v[i]);
+ return;
+ }
+
+ //determine input nnz
+ int lnnz = 0;
+ for( int i=vix; i<vix+len; i++ )
+ lnnz += ( v[i] != 0 ) ? 1 : 0;
+
+ //prepare free space (allocate and shift)
+ int lsize = size+lnnz-(end-start);
+ if( values.length < lsize )
+ recap(lsize);
+ shiftRightByN(end, lnnz-(end-start));
+
+ //insert values
+ for( int i=vix, pos=start; i<vix+len; i++ )
+ if( v[i] != 0 ) {
+ values[ pos ] = v[i];
+ indexes[ pos ] = lowerCol+i-vix;
+ pos++;
+ }
+ }
+
+ private void resizeAndInsert(int index, int col, double v) {
+ //allocate new arrays
+ int newCap = newCapacity();
+ double[] oldvalues = values;
+ int[] oldindexes = indexes;
+ values = new double[newCap];
+ indexes = new int[newCap];
+
+ //copy lhs values to new array
+ System.arraycopy(oldvalues, 0, values, 0, index);
+ System.arraycopy(oldindexes, 0, indexes, 0, index);
+
+ //insert new value
+ indexes[index] = col;
+ values[index] = v;
+
+ //copy rhs values to new array
+ System.arraycopy(oldvalues, index, values, index+1, size-index);
+ System.arraycopy(oldindexes, index, indexes, index+1, size-index);
+ size++;
+ }
+
+ private void shiftRightAndInsert(int index, int col, double v) {
+ //overlapping array copy (shift rhs values right by 1)
+ System.arraycopy(values, index, values, index+1, size-index);
+ System.arraycopy(indexes, index, indexes, index+1, size-index);
+
+ //insert new value
+ values[index] = v;
+ indexes[index] = col;
+ size++;
+ }
+
+ private void shiftRightByN(int index, int n) {
+ //overlapping array copy (shift rhs values right by 1)
+ System.arraycopy(values, index, values, index+n, size-index);
+ System.arraycopy(indexes, index, indexes, index+n, size-index);
+ size += n;
+ }
+
+ private void shiftLeftAndDelete(int index) {
+ //overlapping array copy (shift rhs values left by 1)
+ System.arraycopy(values, index+1, values, index, size-index-1);
+ System.arraycopy(indexes, index+1, indexes, index, size-index-1);
+ size--;
+ }
+
+ @Override
+ public void sort() {
+ if( size<=100 || !SortUtils.isSorted(0, size, indexes) )
+ SortUtils.sortByIndex(0, size, indexes, values);
+ }
+
+ @Override
+ public void compact() {
+ int nnz = 0;
+ for( int i=0; i<size; i++ )
+ if( values[i] != 0 ){
+ values[nnz] = values[i];
+ indexes[nnz] = indexes[i];
+ nnz++;
+ }
+ size = nnz; //adjust row size
+ }
+}