BB-71: Filling GraphBLAS matrices without calling GrB_Matrix_build()

[mcmillan03]

Ben and Aydin were discussing about a zero-copy interface for GraphBLAS matrices. This is something Tim D. wanted and he probably hacked it by giving CSR pointers, which is something Ben is also doing in his RDMA work.

However, going forward, Aydin recommends a more storage agnostic solution that works with many different sparse matrix formats. All efficient sparse matrix formats I am aware of are composed of a bunch of arrays so what I had done with CombBLAS is to have each matrix class implement two functions: GetArrays() and GetEssentials() (Page 22, Figure 2 here: https://people.eecs.berkeley.edu/~aydin/combblas-r2.pdf). It doesn't matter what the actual arrays are or their sizes as long as we have a way to query and fill them.

We think a more carefully designed version of these two functions should be added to the spec.

Thoughts?

[DrTimothyAldenDavis]

Yes, to do the zero-copy, I allow the 3 pointers to the 3 CSR arrays to be taken over into my GrB_Matrix A, for a GxB_Matrix_import_CSR. TO make this work I have to agree with the user application on what malloc/calloc/realloc/free to use (#3 ) . The use must malloc the 3 pointers, which then can be freed by the free function by GrB_free (&A).

I don't follow the discussion on page 22 of Aydin & John's document. But that might be compatible with what I'm doing.

My matrices (and vectors & scalars, which to me are the same thing) consist of at most 5 arrays, assuming no pending work, A->[p,h,b,i,x].

CSR and CSC use Ap, Ai, and Ax, just like the MATLAB CSC matrix.

Hyper sparse by row and by col use Ap, Ah, Ai and Ax, where Ah gives the names of the vectors in the list Ap.

Bitmap uses Ab and Ax, both dense m-by-n arrays (Ab is bool, Ax is whatever the type is).

Full uses just Ax.

My "move constructors" are GxB_Matrix_import_[8 variants here]. where the 8 variants are the 4 methods above, each by row and by col. So yes, I just have a few arrays, each with their own sizes. I have a few more things to import/export, like the type, the by-row/by-col orientation, dimensions, iso propery, jumbled property (I allow that pending work to be imported/exported).

If I had a way to define a set of functions that registers these formats, then this kind of thing might work. Assuming it can be done in C, not C++, of course.

[DrTimothyAldenDavis]

I still have GxB_Matrix_import/export and also for vectors, but that approach is not ideal. It's not a good fit for LAGraph for example. A better approach, only slightly different than my GxB import/export approach, is my new GxB pack/unpack methods. These are like move-constructor variants of build/extractTuples, respectively, in the sense that the matrix itself is not created/destroyed. Example:

GrB_Matrix_new (&A, type, nrows, ncols) ;
GxB_Matrix_pack_CSR (A, &Ap, &Aj, &Ax, Ap_size, Aj_size, Ax_size, iso, jumbled, descriptor) ;

The arrays Ap, Aj, and Ax are the CSR format on input. The bool iso says Ax holds just one entry. The bool jumbled says the col indices in Aj can be out of order, if true, or sorted in ascending order if false. On input, the matrix A already exists (just like GrB_Matrix_build). On output, A is a matrix which has been filled with the CSR format arrays Ap, Aj, and Ax. I could if I like reformat the matrix internally to any format I like, but regardless of what I do, I now "own" the arrays Ap, Aj, and Ax. So on output the 3 pointers are set to NULL to indicate that the user application doesn't have access to them anymore.

In practice, this "pack" takes O(1) time and requires absolutely no malloc to occur. I just transplant the 3 pointers into the matrix A. Unlike GrB_Matrix_build, if A already has any entries I just clear them first.

This method for constructing a matrix is incredibly fast, even faster than a single call to GrB_Matrix_extractElement for example. No malloc or free need occur.

I do not like my prior GxB_Matrix_import / export, since they must construct a new matrix A on import, and free it on export. GxB_Matrix_import_CSR basically does both lines listed in the code above. So if the matrix already exists then there is no need to create it with GrB_Matrix_new. Then GxB_Matrix_import_CSR is not needed in my API. If you want that behavior, just use the 2 lines shown above.

"pack" is like packing an empty suitcase. It does not create the empty suitcase first. "unpack" is like unpacking a suitcase; after "unpack" you are left with the contents of the matrix in non-opaque form, and an empty suitcase. That is, the matrix A is not destroyed by "unpack", just left with no entries. Its type and dimension are unchanged.