GraphBLAS: C++ Iterators for Sparse Matrices

Abstract

Iteration over opaque, generic data structures is an important feature of many C++ libraries. Aggressive compiler optimization and inlining enables generic C++ iterators to iterate over complex data structures with performance comparable to that of hand-tuned code with C-language (raw) pointers. In this paper, we describe the sparse matrix iterators in the current draft of the C++ GraphBLAS API, their support for a variety of backend data formats, and implementation strategies we have considered. We compare performance of these iterators to that of hand-tuned iteration with raw pointers, showing that our iterators introduce minimal overhead. We consider extensions to our iterator design for interoperability with the draft C++ Graph Library proposal and to support different semantics for iterating over sparse matrices (by row, by column, by specific diagonals, etc.).