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 91291b6029 [MINOR] Sparse Block pushdown operations
91291b6029 is described below
commit 91291b6029d22e964825be6bea35f6c134e34877
Author: Sebastian Baunsgaard <[email protected]>
AuthorDate: Fri Jan 5 16:42:01 2024 +0100
[MINOR] Sparse Block pushdown operations
A few optimization blocks for allocating and appending to sparse blocks.
This commit does not use them, but simply adds the primitives to verify
that it does not break anything else.
Closes #1973
---
.../org/apache/sysds/runtime/data/DenseBlock.java | 4 +++
.../org/apache/sysds/runtime/data/SparseBlock.java | 3 ---
.../apache/sysds/runtime/data/SparseBlockMCSR.java | 25 +++++++----------
.../org/apache/sysds/runtime/data/SparseRow.java | 13 ++++++++-
.../apache/sysds/runtime/data/SparseRowScalar.java | 31 +++++++++++++++++-----
.../apache/sysds/runtime/data/SparseRowVector.java | 30 ++++++++++++++-------
6 files changed, 70 insertions(+), 36 deletions(-)
diff --git a/src/main/java/org/apache/sysds/runtime/data/DenseBlock.java
b/src/main/java/org/apache/sysds/runtime/data/DenseBlock.java
index 64e3789d4a..037231fa0e 100644
--- a/src/main/java/org/apache/sysds/runtime/data/DenseBlock.java
+++ b/src/main/java/org/apache/sysds/runtime/data/DenseBlock.java
@@ -734,6 +734,10 @@ public abstract class DenseBlock implements Serializable,
Block
return true;
}
+ public void fill(double value){
+ reset(_odims, value);
+ }
+
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
diff --git a/src/main/java/org/apache/sysds/runtime/data/SparseBlock.java
b/src/main/java/org/apache/sysds/runtime/data/SparseBlock.java
index bc6d4727d1..cd1bd751f3 100644
--- a/src/main/java/org/apache/sysds/runtime/data/SparseBlock.java
+++ b/src/main/java/org/apache/sysds/runtime/data/SparseBlock.java
@@ -424,9 +424,6 @@ public abstract class SparseBlock implements Serializable,
Block
/**
* Get values of row r in the format of a sparse row.
*
- * NOTE: This method exists for incremental runtime integration and
might
- * be deleted in the future.
- *
* @param r row index starting at 0
* @return values of row r as a sparse row
*/
diff --git a/src/main/java/org/apache/sysds/runtime/data/SparseBlockMCSR.java
b/src/main/java/org/apache/sysds/runtime/data/SparseBlockMCSR.java
index 08dbc8b0a4..c7e79b8dbc 100644
--- a/src/main/java/org/apache/sysds/runtime/data/SparseBlockMCSR.java
+++ b/src/main/java/org/apache/sysds/runtime/data/SparseBlockMCSR.java
@@ -271,7 +271,7 @@ public class SparseBlockMCSR extends SparseBlock
@Override
public long size(int rl, int ru) {
- int ret = 0;
+ long ret = 0;
for( int i=rl; i<ru; i++ )
ret += isAllocated(i) ? _rows[i].size() : 0;
return ret;
@@ -348,12 +348,13 @@ public class SparseBlockMCSR extends SparseBlock
}
@Override
- public void append(int r, int c, double v) {
- if( !isAllocated(r) )
- _rows[r] = new SparseRowScalar();
- else if( _rows[r] instanceof SparseRowScalar &&
!_rows[r].isEmpty() )
- _rows[r] = new SparseRowVector(_rows[r]);
- _rows[r].append(c, v);
+ public final void append(final int r, final int c, final double v) {
+ if(v == 0)
+ return;
+ else if(_rows[r] == null)
+ _rows[r] = new SparseRowScalar().append(c, v);
+ else
+ _rows[r] = _rows[r].append(c, v);
}
@Override
@@ -420,18 +421,12 @@ public class SparseBlockMCSR extends SparseBlock
@Override
public int posFIndexGTE(int r, int c) {
- //prior check with isEmpty(r) expected
- if( _rows[r] instanceof SparseRowScalar )
- _rows[r] = new SparseRowVector(_rows[r]);
- return ((SparseRowVector)_rows[r]).searchIndexesFirstGTE(c);
+ return _rows[r].searchIndexesFirstGTE(c);
}
@Override
public int posFIndexGT(int r, int c) {
- //prior check with isEmpty(r) expected
- if( _rows[r] instanceof SparseRowScalar )
- _rows[r] = new SparseRowVector(_rows[r]);
- return ((SparseRowVector)_rows[r]).searchIndexesFirstGT(c);
+ return _rows[r].searchIndexesFirstGT(c);
}
public void setNnzEstimatePerRow(int nnzPerCol, int nCol){
diff --git a/src/main/java/org/apache/sysds/runtime/data/SparseRow.java
b/src/main/java/org/apache/sysds/runtime/data/SparseRow.java
index e0b47a895a..33f958344d 100644
--- a/src/main/java/org/apache/sysds/runtime/data/SparseRow.java
+++ b/src/main/java/org/apache/sysds/runtime/data/SparseRow.java
@@ -95,8 +95,9 @@ public abstract class SparseRow implements Serializable
*
* @param col column index, zero-based
* @param v value
+ * @return the row with an appended element
*/
- public abstract void append(int col, double v);
+ public abstract SparseRow append(int col, double v);
/**
* Gets the value of a specified column. If the column
@@ -139,6 +140,16 @@ public abstract class SparseRow implements Serializable
* @return A copy
*/
public abstract SparseRow copy(boolean deep);
+
+ /**
+ * Get first index greater than equal column index.
+ * @param col column to be greater than
+ * @return index
+ */
+ public abstract int searchIndexesFirstGTE(int col);
+
+
+ public abstract int searchIndexesFirstGT(int col);
@Override
public String toString() {
diff --git a/src/main/java/org/apache/sysds/runtime/data/SparseRowScalar.java
b/src/main/java/org/apache/sysds/runtime/data/SparseRowScalar.java
index b4b07c8bae..485e239a2b 100644
--- a/src/main/java/org/apache/sysds/runtime/data/SparseRowScalar.java
+++ b/src/main/java/org/apache/sysds/runtime/data/SparseRowScalar.java
@@ -78,14 +78,21 @@ public final class SparseRowScalar extends SparseRow{
}
@Override
- public void append(int col, double v) {
+ public SparseRow 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;
+ return this;
+ else if( index >= 0 ){ // if already set
+ SparseRowVector srv = new SparseRowVector();
+ srv.append(index, value);
+ srv.append(col, v);
+ return srv;
+ }
+ else{
+ index = col;
+ value = v;
+ return this;
+ }
+
}
@Override
@@ -116,6 +123,16 @@ public final class SparseRowScalar extends SparseRow{
return value;
}
+ @Override
+ public int searchIndexesFirstGTE(int col) {
+ return col <= index ? 0 : -1;
+ }
+
+ @Override
+ public int searchIndexesFirstGT(int col) {
+ return col < index ? 0 : -1;
+ }
+
@Override
public SparseRow copy(boolean deep){
return new SparseRowScalar(index, value);
diff --git a/src/main/java/org/apache/sysds/runtime/data/SparseRowVector.java
b/src/main/java/org/apache/sysds/runtime/data/SparseRowVector.java
index 3e433f15fc..50229e15df 100644
--- a/src/main/java/org/apache/sysds/runtime/data/SparseRowVector.java
+++ b/src/main/java/org/apache/sysds/runtime/data/SparseRowVector.java
@@ -54,6 +54,7 @@ public final class SparseRowVector extends SparseRow {
}
public SparseRowVector(int capacity) {
+ capacity = Math.max(initialCapacity, capacity);
estimatedNzs = capacity;
values = new double[capacity];
indexes = new int[capacity];
@@ -78,6 +79,12 @@ public final class SparseRowVector extends SparseRow {
size = v.length;
}
+ public SparseRowVector(double[] v, int[] i, int nnz){
+ values = v;
+ indexes = i;
+ size = nnz;
+ }
+
/**
* Sparse row vector constructor that take a dense array, and allocate
sparsely by ignoring zero values
* @param v The dense row
@@ -268,19 +275,20 @@ public final class SparseRowVector extends SparseRow {
}
@Override
- public void append(int col, double v) {
- //early abort on zero
- if( v==0.0 )
- return;
+ public SparseRowVector append(int col, double v) {
+ // early abort on zero
+ if(v == 0.0)
+ return this;
- //resize if required
- if( size==values.length )
+ // resize if required
+ if( size == values.length )
recap(newCapacity());
- //append value at end
+ // append value at end
values[size] = v;
indexes[size] = col;
size++;
+ return this;
}
@Override
@@ -309,8 +317,9 @@ public final class SparseRowVector extends SparseRow {
return (index-1 < size) ? index-1 : -1;
}
+ @Override
public int searchIndexesFirstGTE(int col) {
- if( size == 0 ) return -1;
+ // assumed that empty check is made.
//search for existing col index
int index = Arrays.binarySearch(indexes, 0, size, col);
@@ -322,9 +331,10 @@ public final class SparseRowVector extends SparseRow {
return (index < size) ? index : -1;
}
+ @Override
public int searchIndexesFirstGT(int col) {
- if( size == 0 ) return -1;
-
+ // assumed that empty check is made.
+
//search for existing col index
int index = Arrays.binarySearch(indexes, 0, size, col);
if( index >= 0 )
