Compilation of Shape Operators on Sparse Arrays

Abstract

We show how to build a compiler for a sparse array language that supports shape operators (e.g. reshaping or concatenating arrays) in addition to compute operators. Existing sparse array programming systems implement generic shape operators for only some sparse data structures, reduce shape operators on other data structures to those, and do not support fusion. Our system compiles sparse array expressions to code that efficiently iterates over reshaped views of irregular sparse data structures, without needing to materialize temporary storage for intermediates. Our evaluation shows that our approach generates sparse array code competitive with popular sparse array libraries: our generated shape operators achieve geometric mean speed-ups ranging from 1.66x to 15.3x when compared to hand-written kernels in scipy.sparse and 1.67x to 651x when compared to generic implementations in pydata/sparse. For operators that require data structure conversions in these libraries, our generated code achieves geometric mean speed ups ranging from 7.29x to 13.0x when compared to scipy.sparse and 21.3x to 511x when compared to pydata/sparse. Finally, our evaluation also shows that fusing shape and compute operators improves the performance of several expressions (geometric means 1.22x-2.23x).

Article

BibTeX

@article{ajroot2024,
  title={Compilation of Shape Operators on Sparse Arrays},
  author={Alexander J Root and Bobby Yan and Peiming Liu and Christophe Gyurgyik and Aart J.C Bik and Fredrik Kjolstad},
  journal={Proceedings of the ACM on Programming Languages},
  volume={8},
  issue={OOPSLA},
  year={2024},
  month={October}
}