Package org.apache.sysds.runtime.data

Class SparseBlockCSC

java.lang.Object
org.apache.sysds.runtime.data.SparseBlock
org.apache.sysds.runtime.data.SparseBlockCSC
All Implemented Interfaces:
Serializable, Block
public class SparseBlockCSC extends SparseBlock
SparseBlock implementation that realizes a traditional 'compressed sparse column' representation, where the entire sparse block is stored as three arrays: ptr of length clen+1 to store offsets per column, and indexes/values of length nnz to store row indexes and values of non-zero entries. This format is very memory efficient for sparse (but not ultra-sparse) matrices and provides very good performance for common operations, partially due to lower memory bandwidth requirements. However, this format is slow on incremental construction (because it does not allow append/sort per row) without reshifting. For these types of operations, the 'modified compressed sparse row/column' representations are better suited since they are update friendlier. Further, this representation implements both the row oriented and the column oriented one. By implementing the row-oriented API, we ensure interoperability with existing operators. Finally, the total nnz is limited to INTEGER_MAX, whereas for SparseBlockMCSR only the nnz per row are limited to INTEGER_MAX. TODO performance - currently this sparse block is very slow and this slows down even the component tests
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    class 
    SparseBlockCSC.NonEmptyColumnsIteratorCSC
     
    class 
    SparseBlockCSC.NonEmptyRowsIteratorCSC
     

    Nested classes/interfaces inherited from class org.apache.sysds.runtime.data.SparseBlock

    SparseBlock.Type

  • Constructor Summary

    Constructors
    Constructor
    Description
    SparseBlockCSC(int[] colPtr, int[] rowInd, double[] values, int nnz)
     
    SparseBlockCSC(int rlen, int clen)
     
    SparseBlockCSC(int cols, int[] rowInd, int[] colInd, double[] values)
     
    SparseBlockCSC(int rlen, int clen, int capacity)
     
    SparseBlockCSC(SparseBlock sblock)
     
    SparseBlockCSC(SparseBlock sblock, int clen)
     
    SparseBlockCSC(SparseRow[] cols, int nnz)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add(int r, int c, double v)
    Add a value to a matrix cell (r,c).
    void
    allocate(int r)
    Allocate the underlying data structure holding non-zero values of row r if necessary.
    void
    allocate(int r, int nnz)
    Allocate the underlying data structure holding non-zero values of row r if necessary, w/ given size.
    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.
    void
    append(int r, int c, double v)
    Append a value to the end of the physical representation.
    boolean
    checkValidity(int rlen, int clen, long nnz, boolean strict)
    Validate the correctness of the internal data structures of the different sparse block implementations.
    int[]
    colPointers()
    Get raw access to underlying array of column pointers For use in GPU code
    void
    compact()
    In-place compaction of non-zero-entries; removes zero entries and shifts non-zero entries to the left if necessary.
    void
    compact(int r)
    Re-allocate physical row if physical size exceeds logical size plus resize factor.
    void
    deleteIndexRange(int r, int cl, int cu)
    Deletes all non-zero values of the given column range [cl,cu) in row r.
    void
    deleteIndexRangeCol(int c, int rl, int ru)
     
    static long
    estimateSizeInMemory(long nrows, long ncols, double sparsity)
    Get the estimated in-memory size of the sparse block in CSC with the given dimensions w/o accounting for overallocation.
    SparseRow
    get(int r)
    Get values of row r in the format of a sparse row.
    double
    get(int r, int c)
    Get value of matrix cell (r,c).
    SparseRow
    getCol(int c)
     
    long
    getExactSizeInMemory()
    Computes the exact size in memory of the materialized block
    Iterator<Integer>
    getNonEmptyColumnsIterator(int cl, int cu)
     
    Iterator<Integer>
    getNonEmptyRowsIterator(int rl, int ru)
     
    SparseBlock.Type
    getSparseBlockType()
    Get the type of the sparse block.
    int[]
    indexes()
    Get raw access to underlying array of row indices For use in GPU code
    int[]
    indexes(int r)
    Get the sorted array of column indexes of all non-zero entries in row r.
    int[]
    indexesCol(int c)
     
    void
    initSparse(int clen, int nnz, DataInput in)
    Initializes the CSC sparse block from an ordered input stream of sparse columns (colnnz, iv-pairs*).
    void
    initUltraSparse(int nnz, DataInput in)
    Initializes the CSC sparse block from an ordered input stream of ultra-sparse ijv triples.
    boolean
    isAllocated(int r)
    Indicates if the underlying data structure for a given row is already allocated.
    boolean
    isContiguous()
    Indicates if the underlying data structures returned by values and indexes are contiguous arrays, which can be exploited for more efficient operations.
    boolean
    isEmpty(int r)
    Get information if row r is empty, i.e., does not contain non-zero values.
    boolean
    isEmptyCol(int c)
     
    boolean
    isThreadSafe()
    Indicates if the underlying implementation allows thread-safe row updates if concurrent threads update disjoint rows.
    int
    numCols()
    Get the number of columns in the CSC block
    int
    numRows()
    Get the number of rows in the sparse block.
    int
    pos(int r)
    Get the starting position of row r in the indexes/values arrays returned by indexes(r) and values(r).
    int
    posCol(int c)
     
    int
    posFIndexGT(int r, int c)
    Get position of first column index greater than column c in row r.
    int
    posFIndexGTCol(int r, int c)
     
    int
    posFIndexGTE(int r, int c)
    Get position of first column index greater than or equal column c in row r.
    int
    posFIndexGTECol(int r, int c)
     
    int
    posFIndexLTE(int r, int c)
    Get position of first column index lower than or equal column c in row r.
    int
    posFIndexLTECol(int r, int c)
     
    void
    reset()
    Clears the sparse block by deleting non-zero values.
    void
    reset(int ennz, int maxnnz)
    Clears the sparse block by deleting non-zero values.
    void
    reset(int r, int ennz, int maxnnz)
    Clears row r of the sparse block by deleting non-zero values.
    void
    resetCol(int c)
     
    boolean
    set(int r, int c, double v)
    Set the value of a matrix cell (r,c).
    void
    set(int r, SparseRow row, boolean deep)
    Set the values of row r to the given sparse row.
    void
    setCol(int c, SparseRow col, boolean deep)
     
    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.
    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.
    void
    setIndexRangeCol(int c, int rl, int ru, double[] v, int[] vix, int vpos, int vlen)
     
    void
    setIndexRangeCol(int c, int rl, int ru, double[] v, int vix, int vlen)
     
    long
    size()
    Get the number of non-zero values in the sparse block.
    int
    size(int r)
    Get the number of non-zero values in row r.
    long
    size(int rl, int ru)
    Get the number of non-zeros values in the row range of [rl, ru).
    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);
    int
    sizeCol(int c)
     
    long
    sizeCol(int cl, int cu)
     
    void
    sort()
    Sort all non-zero value/index pairs of the sparse block by row and column index.
    void
    sort(int r)
    Sort all non-zero value/index pairs of row r column index.
    void
    sortCol(int c)
     
    String
    toString()
     
    double[]
    values()
    Get raw access to underlying array of values For use in GPU code
    double[]
    values(int r)
    Get the array of all non-zero entries in row r, sorted by their column indexes.
    double[]
    valuesCol(int c)
     

    Methods inherited from class org.apache.sysds.runtime.data.SparseBlock

    contains, contains, equals, equals, equals, equals, getIterator, getIterator, getIterator, getIterator, getNonEmptyRows, getNonEmptyRows, isAligned, isAligned

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • SparseBlockCSC

      public SparseBlockCSC(int rlen, int clen)

    • SparseBlockCSC

      public SparseBlockCSC(int rlen, int clen, int capacity)

    • SparseBlockCSC

      public SparseBlockCSC(int[] colPtr, int[] rowInd, double[] values, int nnz)

    • SparseBlockCSC

      public SparseBlockCSC(SparseBlock sblock, int clen)

    • SparseBlockCSC

      public SparseBlockCSC(SparseBlock sblock)

    • SparseBlockCSC

      public SparseBlockCSC(SparseRow[] cols, int nnz)

    • SparseBlockCSC

      public SparseBlockCSC(int cols, int[] rowInd, int[] colInd, double[] values)

  • Method Details

    • initUltraSparse

      public void initUltraSparse(int nnz, DataInput in) throws IOException
      Initializes the CSC sparse block from an ordered input stream of ultra-sparse ijv triples.
      Parameters:
      nnz - number of non-zeros to read
      in - data input stream of ijv triples, ordered by column and row indices
      Throws:
      IOException - if deserialization error occurs

    • initSparse

      public void initSparse(int clen, int nnz, DataInput in) throws IOException
      Initializes the CSC sparse block from an ordered input stream of sparse columns (colnnz, iv-pairs*).
      Parameters:
      clen - number of columns
      nnz - number of non-zeros to read
      in - data input stream of sparse columns, ordered by column index
      Throws:
      IOException - if deserialization error occurs

    • estimateSizeInMemory

      public static long estimateSizeInMemory(long nrows, long ncols, double sparsity)
      Get the estimated in-memory size of the sparse block in CSC with the given dimensions w/o accounting for overallocation.
      Parameters:
      nrows - number of rows
      ncols - number of columns
      sparsity - sparsity ratio
      Returns:
      memory estimate

    • colPointers

      public int[] colPointers()
      Get raw access to underlying array of column pointers For use in GPU code
      Returns:
      array of column pointers

    • indexes

      public int[] indexes()
      Get raw access to underlying array of row indices For use in GPU code
      Returns:
      array of row indexes

    • values

      public double[] values()
      Get raw access to underlying array of values For use in GPU code
      Returns:
      array of values

    • allocate

      public void allocate(int r)
      Description copied from class: SparseBlock
      Allocate the underlying data structure holding non-zero values of row r if necessary.
      Specified by:
      allocate in class SparseBlock
      Parameters:
      r - row index

    • allocate

      public void allocate(int r, int nnz)
      Description copied from class: SparseBlock
      Allocate the underlying data structure holding non-zero values of row r if necessary, w/ given size.
      Specified by:
      allocate in class SparseBlock
      Parameters:
      r - row index
      nnz - number of non-zeros

    • allocate

      public void allocate(int r, int ennz, int maxnnz)
      Description copied from class: SparseBlock
      Allocate the underlying data structure holding non-zero values of row r w/ the specified estimated nnz and max nnz.
      Specified by:
      allocate in class SparseBlock
      Parameters:
      r - row index
      ennz - estimated non-zeros
      maxnnz - max non-zeros

    • compact

      public void compact(int r)
      Description copied from class: SparseBlock
      Re-allocate physical row if physical size exceeds logical size plus resize factor.
      Specified by:
      compact in class SparseBlock
      Parameters:
      r - row index

    • compact

      public void compact()
      Description copied from class: SparseBlock
      In-place compaction of non-zero-entries; removes zero entries and shifts non-zero entries to the left if necessary.
      Specified by:
      compact in class SparseBlock

    • getSparseBlockType

      public SparseBlock.Type getSparseBlockType()
      Description copied from class: SparseBlock
      Get the type of the sparse block.
      Specified by:
      getSparseBlockType in class SparseBlock
      Returns:
      sparse block type

    • numRows

      public int numRows()
      Description copied from class: SparseBlock
      Get the number of rows in the sparse block.
      Specified by:
      numRows in class SparseBlock
      Returns:
      number of rows

    • numCols

      public int numCols()
      Get the number of columns in the CSC block
      Returns:
      number of columns

    • isThreadSafe

      public boolean isThreadSafe()
      Description copied from class: SparseBlock
      Indicates if the underlying implementation allows thread-safe row updates if concurrent threads update disjoint rows.
      Specified by:
      isThreadSafe in class SparseBlock
      Returns:
      true if thread-safe row updates

    • isContiguous

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

    • isAllocated

      public boolean isAllocated(int r)
      Description copied from class: SparseBlock
      Indicates if the underlying data structure for a given row is already allocated.
      Specified by:
      isAllocated in class SparseBlock
      Parameters:
      r - row index
      Returns:
      true if already allocated

    • reset

      public void reset()
      Description copied from class: SparseBlock
      Clears the sparse block by deleting non-zero values. After this call all size() calls are guaranteed to return 0.
      Specified by:
      reset in class SparseBlock

    • reset

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

    • reset

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

    • resetCol

      public void resetCol(int c)

    • size

      public long size()
      Description copied from class: SparseBlock
      Get the number of non-zero values in the sparse block.
      Specified by:
      size in class SparseBlock
      Returns:
      number of non-zero values in sparse block

    • size

      public int size(int r)
      Description copied from class: SparseBlock
      Get the number of non-zero values in row r.
      Specified by:
      size in class SparseBlock
      Parameters:
      r - row index starting at 0
      Returns:
      number of non-zero values in row r

    • sizeCol

      public int sizeCol(int c)

    • size

      public long size(int rl, int ru)
      Description copied from class: SparseBlock
      Get the number of non-zeros values in the row range of [rl, ru).
      Specified by:
      size in class SparseBlock
      Parameters:
      rl - row lower index
      ru - row upper index
      Returns:
      number of non-zero values in the row range

    • sizeCol

      public long sizeCol(int cl, int cu)

    • size

      public long size(int rl, int ru, int cl, int cu)
      Description copied from class: SparseBlock
      Get the number of non-zeros values in the row and column range of [rl/cl, ru/cu);
      Specified by:
      size in class SparseBlock
      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 boolean isEmpty(int r)
      Description copied from class: SparseBlock
      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.
      Specified by:
      isEmpty in class SparseBlock
      Parameters:
      r - row index starting at 0
      Returns:
      true if row does not contain non-zero values

    • isEmptyCol

      public boolean isEmptyCol(int c)

    • checkValidity

      public boolean checkValidity(int rlen, int clen, long nnz, boolean strict)
      Description copied from class: SparseBlock
      Validate the correctness of the internal data structures of the different sparse block implementations.
      Specified by:
      checkValidity in class SparseBlock
      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 long getExactSizeInMemory()
      Description copied from class: SparseBlock
      Computes the exact size in memory of the materialized block
      Specified by:
      getExactSizeInMemory in class SparseBlock
      Returns:
      the exact size in memory

    • indexes

      public int[] indexes(int r)
      Description copied from class: SparseBlock
      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)).
      Specified by:
      indexes in class SparseBlock
      Parameters:
      r - row index starting at 0
      Returns:
      sorted array of column indexes

    • indexesCol

      public int[] indexesCol(int c)

    • values

      public double[] values(int r)
      Description copied from class: SparseBlock
      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)).
      Specified by:
      values in class SparseBlock
      Parameters:
      r - row index starting at 0
      Returns:
      array of all non-zero entries in row r sorted by column indexes

    • valuesCol

      public double[] valuesCol(int c)

    • pos

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

    • posCol

      public int posCol(int c)

    • set

      public boolean set(int r, int c, double v)
      Description copied from class: SparseBlock
      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.
      Specified by:
      set in class SparseBlock
      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 void set(int r, SparseRow row, boolean deep)
      Description copied from class: SparseBlock
      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.
      Specified by:
      set in class SparseBlock
      Parameters:
      r - row index starting at 0
      row - sparse row
      deep - indicator to create deep copy of sparse row

    • setCol

      public void setCol(int c, SparseRow col, boolean deep)

    • add

      public boolean add(int r, int c, double v)
      Description copied from class: SparseBlock
      Add a value to a matrix cell (r,c). This might update an existing non-zero value, or insert a new non-zero value.
      Specified by:
      add in class SparseBlock
      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 void append(int r, int c, double v)
      Description copied from class: SparseBlock
      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.
      Specified by:
      append in class SparseBlock
      Parameters:
      r - row index starting at 0
      c - column index starting at 0
      v - zero or non-zero value

    • setIndexRange

      public void setIndexRange(int r, int cl, int cu, double[] v, int vix, int vlen)
      Description copied from class: SparseBlock
      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).
      Specified by:
      setIndexRange in class SparseBlock
      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

    • setIndexRangeCol

      public void setIndexRangeCol(int c, int rl, int ru, double[] v, int vix, int vlen)

    • setIndexRange

      public void setIndexRange(int r, int cl, int cu, double[] v, int[] vix, int vpos, int vlen)
      Description copied from class: SparseBlock
      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.
      Specified by:
      setIndexRange in class SparseBlock
      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

    • setIndexRangeCol

      public void setIndexRangeCol(int c, int rl, int ru, double[] v, int[] vix, int vpos, int vlen)

    • deleteIndexRange

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

    • deleteIndexRangeCol

      public void deleteIndexRangeCol(int c, int rl, int ru)

    • sort

      public void sort()
      Description copied from class: SparseBlock
      Sort all non-zero value/index pairs of the sparse block by row and column index.
      Specified by:
      sort in class SparseBlock

    • sort

      public void sort(int r)
      Description copied from class: SparseBlock
      Sort all non-zero value/index pairs of row r column index.
      Specified by:
      sort in class SparseBlock
      Parameters:
      r - row index starting at 0

    • sortCol

      public void sortCol(int c)

    • get

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

    • get

      public SparseRow get(int r)
      Description copied from class: SparseBlock
      Get values of row r in the format of a sparse row.
      Specified by:
      get in class SparseBlock
      Parameters:
      r - row index starting at 0
      Returns:
      values of row r as a sparse row

    • getCol

      public SparseRow getCol(int c)

    • posFIndexLTE

      public int posFIndexLTE(int r, int c)
      Description copied from class: SparseBlock
      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.
      Specified by:
      posFIndexLTE in class SparseBlock
      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

    • posFIndexLTECol

      public int posFIndexLTECol(int r, int c)

    • posFIndexGTE

      public int posFIndexGTE(int r, int c)
      Description copied from class: SparseBlock
      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.
      Specified by:
      posFIndexGTE in class SparseBlock
      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

    • posFIndexGTECol

      public int posFIndexGTECol(int r, int c)

    • posFIndexGT

      public int posFIndexGT(int r, int c)
      Description copied from class: SparseBlock
      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.
      Specified by:
      posFIndexGT in class SparseBlock
      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

    • posFIndexGTCol

      public int posFIndexGTCol(int r, int c)

    • toString

      public String toString()
      Specified by:
      toString in class SparseBlock

    • getNonEmptyRowsIterator

      public Iterator<Integer> getNonEmptyRowsIterator(int rl, int ru)
      Specified by:
      getNonEmptyRowsIterator in class SparseBlock

    • getNonEmptyColumnsIterator

      public Iterator<Integer> getNonEmptyColumnsIterator(int cl, int cu)