CompressedSparseLayout

Usage

use CompressedSparseLayout;

or

import CompressedSparseLayout;

Warning

‘CompressedSparseLayout’ is unstable and may change in the future

This module supports Compressed Sparse Row/Column (CSR/CSC) memory layouts for sparse domains and the arrays declared over them. It does this via a pair of records, csrLayout and cscLayout, which correspond to the CSR and CSC approaches, respectively. These two records are duals of one another, where the CSR format supports efficient iteration over rows while the CSC format is better for column-wise traversals.

A sparse domain can be declared using these layouts using syntax like the following:

use CompressedSparseLayout;

const D = {1..m, 1..n},  // a dense domain defining a bounding box
      CSRDomain: sparse subdomain(D) dmapped new csrLayout() = ...;

var CSRArray: [CSRDomain] real;

In addition to the standard methods and operators defined on sparse domains and arrays in Chapel, these layouts also support the following methods:

• Domains and arrays support .rows()/.cols() queries, which return a range value representing the indices of the rows or columns over which the domain is defined. Note that some of these rows or columns may be empty in practice.

• CSR/CSC arrays support .colsAndVals(row)/.rowsAndVals(col) iterators, which take a given row/column index as input and yield 2-tuples corresponding the column/row index and value at that index, respectively. Note that CSR only supports .colsAndVals() and CSC only supports .rowsAndVals().

config param csLayoutSortByDefault = true

Indicates whether the indices within a row/column of a CSR/CSC layout should be sorted by default or not. Note that this default can be overridden on a per-instance basis using the sortedIndices initializer arguments below.

record csrLayout

This record implements a 2D compressed sparse row layout (CSR, for short).

Each domain declared over this layout represents its sparse index set using an .size-element vector to store the column indices and a ~#rows-element vector indicating the offset where each row starts. The sortedIndices argument in the initializer indicates whether the column indices within each row are stored in sorted order or not.

Arrays declared over such domains store their elements corresponding to the domain’s indices using a dense .size-element vector.

As a result of this storage format, CSR domains and arrays support efficient iteration over rows, but not over columns.

param sortedIndices : bool = csLayoutSortByDefault

proc init(param sortedIndices: bool = csLayoutSortByDefault)

record cscLayout

This record implements a 2D compressed sparse column layout (CSC, for short). It is the dual of the csrLayout layout above, simply swapping rows and columns in its representation and operators. As a result, it effectively stores its arrays’ values in column-major order, supporting efficient iteration over rows, but not over columns.

param sortedIndices : bool = csLayoutSortByDefault

proc init(param sortedIndices: bool = csLayoutSortByDefault)