HN Reader

These approaches may be nice to demonstrate the concept in brief but I'm a bit sad the article didn't take the opportunity to go into a design that only stores the triangular data since it's pretty trivial to overload operators in C++. If this is meant to be a demonstration of the performance advantage of mdspan over nested vector creation (which certainly is the case for large multidimensional arrays) it'd be good to dial that up.

It's an interesting exploration of ideas, but there are some issues with this article. Worth noting that it does describe it's approach as "simple and naive", so take my comments below to be corrections and/or pointers into the practical and complex issues on this topic.

- The article says adjacency matrices are "usually dense" but that's not true at all, most graph are sparse to very sparse. In a social network with billions of people, the average out degree might be 100. The internet is another example of a very sparse graph, billions of nodes but most nodes have at most one or maybe two direct connections.

- Storing a dense matrix means it can only work with very small graphs, a graph with one million nodes would require one-million-squared memory elements, not possible.

- Most of the elements in the matrix would be "zero", but you're still storing them, and when you do matrix multiplication (one step in a BFS across the graph) you're still wasting energy moving, caching, and multiplying/adding mostly zeros. It's very inefficient.

- Minor nit, it says the diagonal is empty because nodes are already connected to themselves, this isn't correct by theory, self edges are definitely a thing. There's a reason the main diagonal is called "the identity".

- Not every graph algebra uses the numeric "zero" to mean zero, for tropical algebras (min/max) the additive identity is positive/negative infinity. Zero is a valid value in those algebras.

I don't mean to diss on the idea, it's a good way to dip a toe into the math and computer science behind algebraic graph theory, but in production or for anything but the smallest (and densest) graphs, a sparse graph algebra library like SuiteSparse would be the most appropriate.

SuiteSparse is used in MATLAB (A .* B calls SuiteSparse), FalkorDB, python-graphblas, OneSparse (postgres library) and many other libraries. The author Tim Davis from TAMU is a leading expert in this field of research.

(I'm a GraphBLAS contributor and author of OneSparse)

When the article mentioned “more efficient”, I was expecting some actual measurements.

Instead, it seems to just assert that allocating (dense) matrices in a big block is better than the usual array of pointers that you would get in older C/C++.

Note that GCC/libstdc++ (as of v15.2) does not yet implement std::mdspan [1], so it needs to be imported from another reference implementation like Kokkos [2].

[1] Merged in for v16: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107761

[2] https://github.com/kokkos/mdspan

On a related note, there's currently a lot of work towards adding graph structures to the upcoming c++ standard. https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/

I can see a use for this. It would be nice to not have to write the typical indexing boilerplate when dealing with multidimensional data. One less area to make a mistake. Feels less kludgy.

I wonder if this has any benefit of row vs column memory access, which I always forget to bother with unless suddenly my performance crawls.

Are the adjacency matrices in graph theory really usually dense?

One important thing to keep in mind when using std::mdspan: There is no stable version of GCC with official support. Not even version 15.2. You need to use the latest trunk. I discovered this after I had already written a significant amount of code using std::mdspan that compiled in Clang and MSVC.