[thxg]

This representation of jagged array is literally the "Compressed Sparse Row" (CSR) format for sparse matrices [1]:

- a single array of floats with all the nonzero matrix entries, ordered row-by-row:

  double values[nnz];

- a single array of ints with the corresponding column index:

  int columns[nnz];

- a single array of ints, of length (m+1), with the start of each row in the two other arrays (the (m+1)th element stores nnz, which will be useful later):

  int start[m + 1];

So to print a whole matrix, you do this:

  for (int i = 0; i < m; i++) {
    index = start[i]; // where
    count = start[i + 1] - start[i]; // number of nonzeros in row i
    
    for (int t = 0; t < count; t++) {
       j = columns[index + t];
       v = values[index + t];
       printf("element (%d, %d) has value %g\n", i, j, v);
    }

To a modern programmer, this may look very old-fashioned (Fortran-ish), but I have tried many alternatives (like grouping columns and values together in a struct, or using pointers), and in my numerical codes, nothing gets even close in terms of performance. It must be said that CSR and CSC (its transpose) are very compact in memory, which is often a bottleneck. Also, since so many sparse numerical codes in benchmarks have used this representation for decades, it could be that CPU designers make sure that it works well.

[1] https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_spars...

[gautamcgoel]

Thanks for this comment, was super interesting! Apparently Matlab uses a similar format (Compressed Sparse Column) to represent sparse matrices.

[dataflow]

Have you tried using precomputed byte offsets rather than indices for all the integers? Those would definitely speed up the non-power-of-2-sized case, but I'd be curious if they might speed this up a little bit too, since they should remove some bit shifting instructions.

[patagurbon]

You often need the indices for other operations (indexing into other arrays). CSC it's transpose CSR, and the doubly compressed forms DCSC/DCSR, are optimized for linear algebra for the most part.

[jjgreen]

A very nice (and fast) C implementation in CSparse (now part of SuiteSparse) https://people.engr.tamu.edu/davis/suitesparse.html

[hinkley]

I’m fairly sure anecdotes like this inform the conversation about structs of arrays versus arrays of structs.

There are a couple of languages that let you treat them the same way. Having list comprehensions (plural) over multidimensional data would be handy.

[xeonmc]

How do you insert elements at the end of a row?