Package org.apache.sysds.runtime.data

Class SparseBlock

java.lang.Object
org.apache.sysds.runtime.data.SparseBlock
All Implemented Interfaces:
Serializable, Block
Direct Known Subclasses:
SparseBlockCOO, SparseBlockCSC, SparseBlockCSR, SparseBlockDCSR, SparseBlockMCSC, SparseBlockMCSR
public abstract class SparseBlock extends Object implements Serializable, Block
This SparseBlock is an abstraction for different sparse matrix formats. Since the design is a tradeoff between performance and generality, we restrict this abstraction to row-major sparse representations for now. All sparse matrix block operations are supposed to be implemented against this abstraction in order to enable variability/extensibility. Example sparse format that can be implemented efficiently include CSR, MCSR, and - with performance drawbacks - COO.
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static enum 
    SparseBlock.Type
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    SparseBlock()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    abstract boolean
    add(int r, int c, double v)
    Add a value to a matrix cell (r,c).
    abstract void
    allocate(int r)
    Allocate the underlying data structure holding non-zero values of row r if necessary.
    abstract void
    allocate(int r, int nnz)
    Allocate the underlying data structure holding non-zero values of row r if necessary, w/ given size.
    abstract void
    allocate(int r, int ennz, int maxnnz)
    Allocate the underlying data structure holding non-zero values of row r w/ the specified estimated nnz and max nnz.
    abstract void
    append(int r, int c, double v)
    Append a value to the end of the physical representation.
    abstract boolean
    checkValidity(int rlen, int clen, long nnz, boolean strict)
    Validate the correctness of the internal data structures of the different sparse block implementations.
    abstract void
    compact()
    In-place compaction of non-zero-entries; removes zero entries and shifts non-zero entries to the left if necessary.
    abstract void
    compact(int r)
    Re-allocate physical row if physical size exceeds logical size plus resize factor.
    List<Integer>
    contains(double[] pattern, boolean earlyAbort)
     
    boolean
    contains(double pattern, int rl, int ru)
    Checks if the block contains at least one value of the given pattern.
    abstract void
    deleteIndexRange(int r, int cl, int cu)
    Deletes all non-zero values of the given column range [cl,cu) in row r.
    boolean
    equals(double[] denseValues, int nCol)
    Get if the dense double array is equivalent to this sparse Block.
    boolean
    equals(double[] denseValues, int nCol, double eps)
    Get if the dense double array is equivalent to this sparse Block.
    boolean
    equals(Object o)
     
    boolean
    equals(SparseBlock o, double eps)
    Verify if the values in this sparse block is equivalent to that sparse block, not taking into account the dimensions of the contained values.
    abstract SparseRow
    get(int r)
    Get values of row r in the format of a sparse row.
    abstract double
    get(int r, int c)
    Get value of matrix cell (r,c).
    abstract long
    getExactSizeInMemory()
    Computes the exact size in memory of the materialized block
    Iterator<IJV>
    getIterator()
    Get a non-zero iterator over the entire sparse block.
    Iterator<IJV>
    getIterator(int ru)
    Get a non-zero iterator over the partial sparse block [0,ru).
    Iterator<IJV>
    getIterator(int rl, int ru)
    Get a non-zero iterator over the subblock [rl, ru).
    Iterator<IJV>
    getIterator(int rl, int ru, int cl, int cu)
    Get a non-zero iterator over the subblock [rl/cl, ru/cu).
    Iterable<Integer>
    getNonEmptyRows()
    Get an iterator over the indices of non-empty rows within the entire sparse block.
    Iterable<Integer>
    getNonEmptyRows(int rl, int ru)
    Get an iterator over the indices of non-zero rows within the sub-block [rl,ru).
    abstract Iterator<Integer>
    getNonEmptyRowsIterator(int rl, int ru)
     
    abstract SparseBlock.Type
    getSparseBlockType()
    Get the type of the sparse block.
    abstract int[]
    indexes(int r)
    Get the sorted array of column indexes of all non-zero entries in row r.
    boolean
    isAligned(int r, SparseBlock that)
    Indicates if all non-zero values of row r are aligned with the same row of the given second sparse block instance, which can be exploited for more efficient operations.
    boolean
    isAligned(SparseBlock that)
    Indicates if all non-zero values are aligned with the given second sparse block instance, which can be exploited for more efficient operations.
    abstract boolean
    isAllocated(int r)
    Indicates if the underlying data structure for a given row is already allocated.
    abstract boolean
    isContiguous()
    Indicates if the underlying data structures returned by values and indexes are contiguous arrays, which can be exploited for more efficient operations.
    abstract boolean
    isEmpty(int r)
    Get information if row r is empty, i.e., does not contain non-zero values.
    abstract boolean
    isThreadSafe()
    Indicates if the underlying implementation allows thread-safe row updates if concurrent threads update disjoint rows.
    abstract int
    numRows()
    Get the number of rows in the sparse block.
    abstract int
    pos(int r)
    Get the starting position of row r in the indexes/values arrays returned by indexes(r) and values(r).
    abstract int
    posFIndexGT(int r, int c)
    Get position of first column index greater than column c in row r.
    abstract int
    posFIndexGTE(int r, int c)
    Get position of first column index greater than or equal column c in row r.
    abstract int
    posFIndexLTE(int r, int c)
    Get position of first column index lower than or equal column c in row r.
    abstract void
    reset()
    Clears the sparse block by deleting non-zero values.
    abstract void
    reset(int ennz, int maxnnz)
    Clears the sparse block by deleting non-zero values.
    abstract void
    reset(int r, int ennz, int maxnnz)
    Clears row r of the sparse block by deleting non-zero values.
    abstract boolean
    set(int r, int c, double v)
    Set the value of a matrix cell (r,c).
    abstract void
    set(int r, SparseRow row, boolean deep)
    Set the values of row r to the given sparse row.
    abstract void
    setIndexRange(int r, int cl, int cu, double[] v, int[] vix, int vpos, int vlen)
    Sets a sparse array of non-zeros values and indexes into the column range [cl,cu) in row r.
    abstract void
    setIndexRange(int r, int cl, int cu, double[] v, int vix, int vlen)
    Sets a dense array of non-zeros values into the column range [cl,cu) in row r.
    abstract long
    size()
    Get the number of non-zero values in the sparse block.
    abstract int
    size(int r)
    Get the number of non-zero values in row r.
    abstract long
    size(int rl, int ru)
    Get the number of non-zeros values in the row range of [rl, ru).
    abstract long
    size(int rl, int ru, int cl, int cu)
    Get the number of non-zeros values in the row and column range of [rl/cl, ru/cu);
    abstract void
    sort()
    Sort all non-zero value/index pairs of the sparse block by row and column index.
    abstract void
    sort(int r)
    Sort all non-zero value/index pairs of row r column index.
    abstract String
    toString()
     
    abstract double[]
    values(int r)
    Get the array of all non-zero entries in row r, sorted by their column indexes.

    Methods inherited from class java.lang.Object

    getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • SparseBlock

      public SparseBlock()

  • Method Details

    • allocate

      public abstract void allocate(int r)
      Allocate the underlying data structure holding non-zero values of row r if necessary.
      Parameters:
      r - row index

    • allocate

      public abstract void allocate(int r, int nnz)
      Allocate the underlying data structure holding non-zero values of row r if necessary, w/ given size.
      Parameters:
      r - row index
      nnz - number of non-zeros

    • allocate

      public abstract void allocate(int r, int ennz, int maxnnz)
      Allocate the underlying data structure holding non-zero values of row r w/ the specified estimated nnz and max nnz.
      Parameters:
      r - row index
      ennz - estimated non-zeros
      maxnnz - max non-zeros

    • compact

      public abstract void compact(int r)
      Re-allocate physical row if physical size exceeds logical size plus resize factor.
      Parameters:
      r - row index

    • compact

      public abstract void compact()
      In-place compaction of non-zero-entries; removes zero entries and shifts non-zero entries to the left if necessary.

    • getSparseBlockType

      public abstract SparseBlock.Type getSparseBlockType()
      Get the type of the sparse block.
      Returns:
      sparse block type

    • numRows

      public abstract int numRows()
      Get the number of rows in the sparse block.
      Returns:
      number of rows

    • isThreadSafe

      public abstract boolean isThreadSafe()
      Indicates if the underlying implementation allows thread-safe row updates if concurrent threads update disjoint rows.
      Returns:
      true if thread-safe row updates

    • isContiguous

      public abstract boolean isContiguous()
      Indicates if the underlying data structures returned by values and indexes are contiguous arrays, which can be exploited for more efficient operations.
      Returns:
      true if underlying data structures are contiguous arrays

    • isAligned

      public boolean isAligned(SparseBlock that)
      Indicates if all non-zero values are aligned with the given second sparse block instance, which can be exploited for more efficient operations. Two non-zeros are aligned if they have the same column index and reside in the same array position.
      Parameters:
      that - sparse block
      Returns:
      true if all non-zero values are aligned with the given second sparse block

    • isAligned

      public boolean isAligned(int r, SparseBlock that)
      Indicates if all non-zero values of row r are aligned with the same row of the given second sparse block instance, which can be exploited for more efficient operations. Two non-zeros are aligned if they have the same column index and reside in the same array position.
      Parameters:
      r - row index starting at 0
      that - sparse block
      Returns:
      true if all non-zero values of row r are aligned with the same row of the given second sparse block instance

    • isAllocated

      public abstract boolean isAllocated(int r)
      Indicates if the underlying data structure for a given row is already allocated.
      Parameters:
      r - row index
      Returns:
      true if already allocated

    • reset

      public abstract void reset()
      Clears the sparse block by deleting non-zero values. After this call all size() calls are guaranteed to return 0.

    • reset

      public abstract void reset(int ennz, int maxnnz)
      Clears the sparse block by deleting non-zero values. After this call all size() calls are guaranteed to return 0.
      Parameters:
      ennz - estimated non-zeros
      maxnnz - max non-zeros

    • reset

      public abstract void reset(int r, int ennz, int maxnnz)
      Clears row r of the sparse block by deleting non-zero values. After this call size(r) is guaranteed to return 0.
      Parameters:
      r - row index
      ennz - estimated non-zeros
      maxnnz - max non-zeros

    • size

      public abstract long size()
      Get the number of non-zero values in the sparse block.
      Returns:
      number of non-zero values in sparse block

    • size

      public abstract int size(int r)
      Get the number of non-zero values in row r.
      Parameters:
      r - row index starting at 0
      Returns:
      number of non-zero values in row r

    • size

      public abstract long size(int rl, int ru)
      Get the number of non-zeros values in the row range of [rl, ru).
      Parameters:
      rl - row lower index
      ru - row upper index
      Returns:
      number of non-zero values in the row range

    • size

      public abstract long size(int rl, int ru, int cl, int cu)
      Get the number of non-zeros values in the row and column range of [rl/cl, ru/cu);
      Parameters:
      rl - row lower index
      ru - row upper index
      cl - column lower index
      cu - column upper index
      Returns:
      number of non-zero values in the row and column range

    • isEmpty

      public abstract boolean isEmpty(int r)
      Get information if row r is empty, i.e., does not contain non-zero values. Equivalent to size(r)==0. Users should do this check if it is unknown if the underlying row data structure is allocated.
      Parameters:
      r - row index starting at 0
      Returns:
      true if row does not contain non-zero values

    • checkValidity

      public abstract boolean checkValidity(int rlen, int clen, long nnz, boolean strict)
      Validate the correctness of the internal data structures of the different sparse block implementations.
      Parameters:
      rlen - number of rows
      clen - number of columns
      nnz - number of non zeros
      strict - enforce optional properties
      Returns:
      true if the sparse block is valid wrt the corresponding format such as COO, CSR, MCSR.

    • getExactSizeInMemory

      public abstract long getExactSizeInMemory()
      Computes the exact size in memory of the materialized block
      Returns:
      the exact size in memory

    • indexes

      public abstract int[] indexes(int r)
      Get the sorted array of column indexes of all non-zero entries in row r. Note that - for flexibility of the implementing format - the returned array may be larger, where the range for row r is given by [pos(r),pos(r)+size(r)).
      Parameters:
      r - row index starting at 0
      Returns:
      sorted array of column indexes

    • values

      public abstract double[] values(int r)
      Get the array of all non-zero entries in row r, sorted by their column indexes. Note that - for flexibility of the implementing format - the returned array may be larger, where the range for row r is given by [pos(r),pos(r)+size(r)).
      Parameters:
      r - row index starting at 0
      Returns:
      array of all non-zero entries in row r sorted by column indexes

    • pos

      public abstract int pos(int r)
      Get the starting position of row r in the indexes/values arrays returned by indexes(r) and values(r).
      Parameters:
      r - row index starting at 0
      Returns:
      starting position of row r

    • set

      public abstract boolean set(int r, int c, double v)
      Set the value of a matrix cell (r,c). This might update an existing non-zero value, insert a new non-zero value, or delete a non-zero value.
      Parameters:
      r - row index starting at 0
      c - column index starting at 0
      v - zero or non-zero value
      Returns:
      true, if number of non-zeros changed

    • set

      public abstract void set(int r, SparseRow row, boolean deep)
      Set the values of row r to the given sparse row. This might update existing non-zero values, insert a new row, or delete a row. NOTE: This method exists for incremental runtime integration and might be deleted in the future.
      Parameters:
      r - row index starting at 0
      row - sparse row
      deep - indicator to create deep copy of sparse row

    • add

      public abstract boolean add(int r, int c, double v)
      Add a value to a matrix cell (r,c). This might update an existing non-zero value, or insert a new non-zero value.
      Parameters:
      r - row index starting at 0
      c - column index starting at 0
      v - zero or non-zero value
      Returns:
      true, if number of non-zeros changed

    • append

      public abstract void append(int r, int c, double v)
      Append a value to the end of the physical representation. This should only be used for operations with sequential write pattern or if followed by a sort() operation. Note that this operation does not perform any matrix cell updates.
      Parameters:
      r - row index starting at 0
      c - column index starting at 0
      v - zero or non-zero value

    • setIndexRange

      public abstract void setIndexRange(int r, int cl, int cu, double[] v, int vix, int vlen)
      Sets a dense array of non-zeros values into the column range [cl,cu) in row r. The passed value array may be larger and the relevant range is given by [vix,vix+len).
      Parameters:
      r - row index starting at 0
      cl - lower column index starting at 0
      cu - upper column index starting at 0
      v - value array
      vix - start index in value array
      vlen - number of relevant values

    • setIndexRange

      public abstract void setIndexRange(int r, int cl, int cu, double[] v, int[] vix, int vpos, int vlen)
      Sets a sparse array of non-zeros values and indexes into the column range [cl,cu) in row r. The passed value array may be larger.
      Parameters:
      r - row index starting at 0
      cl - lower column index starting at 0
      cu - upper column index starting at 0
      v - value array
      vix - column index array
      vpos - start index in value and index arrays
      vlen - number of relevant values

    • deleteIndexRange

      public abstract void deleteIndexRange(int r, int cl, int cu)
      Deletes all non-zero values of the given column range [cl,cu) in row r.
      Parameters:
      r - row index starting at 0
      cl - lower column index starting at 0
      cu - upper column index starting at 0

    • sort

      public abstract void sort()
      Sort all non-zero value/index pairs of the sparse block by row and column index.

    • sort

      public abstract void sort(int r)
      Sort all non-zero value/index pairs of row r column index.
      Parameters:
      r - row index starting at 0

    • get

      public abstract double get(int r, int c)
      Get value of matrix cell (r,c). In case of non existing values this call returns 0.
      Specified by:
      get in interface Block
      Parameters:
      r - row index starting at 0
      c - column index starting at 0
      Returns:
      value of cell at position (r,c)

    • get

      public abstract SparseRow get(int r)
      Get values of row r in the format of a sparse row.
      Parameters:
      r - row index starting at 0
      Returns:
      values of row r as a sparse row

    • posFIndexLTE

      public abstract int posFIndexLTE(int r, int c)
      Get position of first column index lower than or equal column c in row r. The position is relative to the indexes/values arrays returned by indexes(r) and values(r). If no such value exists, this call returns -1.
      Parameters:
      r - row index starting at 0
      c - column index starting at 0
      Returns:
      position of the first column index lower than or equal to column c in row r

    • posFIndexGTE

      public abstract int posFIndexGTE(int r, int c)
      Get position of first column index greater than or equal column c in row r. The position is relative to the indexes/values arrays returned by indexes(r) and values(r). If no such value exists, this call returns -1. Note if CSR the pos(r) is subtracted from the result.
      Parameters:
      r - row index starting at 0
      c - column index starting at 0
      Returns:
      position of the first column index greater than or equal to column c in row r

    • posFIndexGT

      public abstract int posFIndexGT(int r, int c)
      Get position of first column index greater than column c in row r. The position is relative to the indexes/values arrays returned by indexes(r) and values(r). If no such value exists, this call returns -1.
      Parameters:
      r - row index starting at 0
      c - column index starting at 0
      Returns:
      position of the first column index greater than column c in row r

    • contains

      public boolean contains(double pattern, int rl, int ru)
      Checks if the block contains at least one value of the given pattern. Implementations need to handle NaN patterns as well (note that NaN==NaN yields false).
      Parameters:
      pattern - checked pattern
      rl - row lower bound (inclusive)
      ru - row upper bound (exclusive)
      Returns:
      true if pattern appears at least once, otherwise false

    • contains

      public List<Integer> contains(double[] pattern, boolean earlyAbort)

    • getIterator

      public Iterator<IJV> getIterator()
      Get a non-zero iterator over the entire sparse block. Note that the returned IJV object is reused across next calls and should be directly consumed or deep copied.
      Returns:
      IJV iterator

    • getIterator

      public Iterator<IJV> getIterator(int ru)
      Get a non-zero iterator over the partial sparse block [0,ru). Note that the returned IJV object is reused across next calls and should be directly consumed or deep copied.
      Parameters:
      ru - exclusive upper row index starting at 0
      Returns:
      IJV iterator

    • getIterator

      public Iterator<IJV> getIterator(int rl, int ru)
      Get a non-zero iterator over the subblock [rl, ru). Note that the returned IJV object is reused across next calls and should be directly consumed or deep copied.
      Parameters:
      rl - inclusive lower row index starting at 0
      ru - exclusive upper row index starting at 0
      Returns:
      IJV iterator

    • getIterator

      public Iterator<IJV> getIterator(int rl, int ru, int cl, int cu)
      Get a non-zero iterator over the subblock [rl/cl, ru/cu). Note that the returned IJV object is reused across next calls and should be directly consumed or deep copied.
      Parameters:
      rl - inclusive lower row index starting at 0
      ru - exclusive upper row index starting at 0
      cl - inclusive lower column index starting at 0
      cu - exclusive upper column index starting at 0
      Returns:
      IJV iterator

    • getNonEmptyRows

      public Iterable<Integer> getNonEmptyRows()
      Get an iterator over the indices of non-empty rows within the entire sparse block. This iterator facilitates traversal over rows that contain at least one non-zero element, skipping entirely zero rows. The returned integers represent the indexes of non-empty rows.
      Returns:
      iterable

    • getNonEmptyRows

      public Iterable<Integer> getNonEmptyRows(int rl, int ru)
      Get an iterator over the indices of non-zero rows within the sub-block [rl,ru). This iterator facilitates traversal over rows that contain at least one non-zero element, skipping entirely zero rows. The returned integers represent the indexes of non-empty rows.
      Parameters:
      rl - inclusive lower row index starting at 0
      ru - exclusive upper row index starting at 0
      Returns:
      iterable

    • getNonEmptyRowsIterator

      public abstract Iterator<Integer> getNonEmptyRowsIterator(int rl, int ru)

    • toString

      public abstract String toString()
      Overrides:
      toString in class Object

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Object

    • equals

      public boolean equals(SparseBlock o, double eps)
      Verify if the values in this sparse block is equivalent to that sparse block, not taking into account the dimensions of the contained values.
      Parameters:
      o - Other block
      eps - Epsilon allowed
      Returns:
      If the blocs are equivalent.

    • equals

      public boolean equals(double[] denseValues, int nCol)
      Get if the dense double array is equivalent to this sparse Block.
      Parameters:
      denseValues - row major double values same dimensions of sparse Block.
      nCol - Number of columns in dense values (and hopefully in this sparse block)
      Returns:
      If the dense array is equivalent

    • equals

      public boolean equals(double[] denseValues, int nCol, double eps)
      Get if the dense double array is equivalent to this sparse Block.
      Parameters:
      denseValues - row major double values same dimensions of sparse Block.
      nCol - Number of columns in dense values (and hopefully in this sparse block)
      eps - Epsilon allowed to be off. Note we treat zero differently and it must be zero.
      Returns:
      If the dense array is equivalent