17763, "bradcray", "How should we express per-dimension iterations over sparse domains/arrays", "2021-05-17T23:11:36Z"
Users of sparse domains and arrays in Chapel frequently want to iterate over (the nonzeroes of) a single dimension of a sparse domain or array, but we don't currently expose an official way for doing this. This issue is designed to kick off design discussions around this.
As motivation, in 2D, two obvious patterns to support are:
- dense outer loop; sparse inner loop
for r in every row in the sparse domain's/array's dense bounding box
for c in each column of row r representing a nonzero
- sparse outer loop; sparse inner loop
for r in every row containing nonzeroes
for c in each column of row r representing a nonzero
A challenge to creating a per-dimension iterator like this is that in order to be used at depth 'i' in a loop nest, it needs the i-1 indices corresponding to the loops that preceded it. For example, in the sketches above, note that the inner loop refers to the r value yielded by the outer loop. To be efficient, it may also be useful for the iterator to be able to reason about which dimensions have already been traversed vs. not. For 2D, the combinatorial space of how these might be expressed is not too bad, but for higher-dimensional sparse domains, it starts to get ugly.
There's also a question as to whether a given sparse domain implementation should support any iteration order (productivity!) or whether they should only support iteration styles that happen to map well to their storage format (e.g., row-major-iteration for CSR; column-major-order iteration for CSC).
[Internally, we have a dimIter() routine for this, but it is fairly weak—it's limited to 2D sparse domains only, and probably only some of the domain maps. It only supports iteration over the "easy" dimensions. It's never been properly exposed to users due to these limitations.]
Another way to express the inner loop iterations might be to use slicing. For example, you might imagine:
for r in ...however we want to traverse rows...
for c in MySparseThing[r, ..] do
...