2022/09/08 by Willow Ahrens, Daniel Donenfeld, Ahrens, Willow +5 · 3 citations
Computer Science · #Algorithms and Data Compression #Computer Graphics and Visualization Techniques #FOS: Computer and information sciences #Mathematical Software (cs.MS) #Parallel Computing and Optimization Techniques #Programming Languages (cs.PL)
paper · pdf · doi:10.48550/arxiv.2209.05250
openalex publication_date 2022/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Real world arrays often contain underlying structure, such as sparsity, runs of repeated values, or symmetry. Specializing for structure yields significant speedups. But automatically generating efficient code for structured data is challenging, especially when arrays with different structure interact. We show how to abstract over array structures so that the compiler can generate code to coiterate over any combination of them. Our technique enables new array formats (such as 1DVBL for irregular clustered sparsity), new iteration strategies (such as galloping intersections), and new operations over structured data (such as concatenation or convolution).