Fast Collection Operations from Indexed Stream Fusion
Scott Kovach, Praneeth Kolichala, Kyle A. Miller, David Broman, Fredrik Kjolstad · 2025
Read Fast Collection Operations from Indexed Stream Fusion by Scott Kovach, Praneeth Kolichala, Kyle A. Miller, David Broman, Fredrik Kjolstad (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-06456.txt.
Introduction
Scott Kovach and four co-authors present fast tools for work on grouped data sets in code. Their tools walk and merge groups with no wasted spare copies in memory. Unlike past fast sets, they need no special build steps or staged tricks.
A form based on indexed streams lets them state hard merges in a clean way. They built the tools for three coding tongues, from a proof based one to a fast systems one. A machine checked proof in one tongue backs the claim that results are right. Speed and ease can coexist, they argue.
Catalog record
| CREATOR | Scott Kovach, Praneeth Kolichala, Kyle A. Miller, David Broman, Fredrik Kjolstad |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-06456
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fast Collection Operations from Indexed Stream Fusion Scott Kovach, Praneeth Kolichala, Kyle A. Miller, David Broman, Fredrik Kjolstad Abstract . We present a system of efficient methods for traversing and combining associative collection data structures. A distinguishing feature of the system is that, like traditional sequential iterator libraries, it does not require specialized compiler infrastructure or staged compilation for efficiency and composability. By using a representation based on indexed streams, the library can express complex joins over input collections while using no intermediate allocations. We implement the library for the Lean, Morphic, and Rust programming languages and provide a mechanized proof of functional correctness in Lean. Indexed Iterators for Everyone 1. Introduction Many contemporary programming languages include an iterator interface that provides a uniform way of sequentially traversing any data type that implements it. This approach powers the for -loop syntax available in Python, Javascript, Rust, and many other popular languages. Some standard libraries additionally provide combinators such as map, filter, fold, and zip to combine and transform iterators. Compilers can leverage deforestation techniques such as stream fusion ( Wadler 1990 ; Gill et al. 1993 ; Svenningsson 2002 ; Coutts et al. 2007 ) to dramatically improve the performance of such programs by eliminating redundant traversals and memory allocations. Similar combinators can be defined for data structures that represent associative arrays , which encode finite maps from keys to values. However, performance trade-offs arise when using these combinators as they are traditionally defined. We can see this with a simple example task: given a set ( s : Set k ) and a map ( m : Map k v ), find the set of keys that are present in s and associated with a value v in m that satisfies v > 10 . Consider the following API for sets and maps in the functional language Lean ( Moura and Ullrich 2021 ) and three natural ways of implementing the program: ⬇ lookup : Map k v → k → Option v contains : Set k → k → Bool select : Map k v → ( k → v → Bool ) → Set k filter : Set k → ( k → Bool ) → Set k intersect : Set k → Set k → Set k variable ( s : Set k ) ( m : Map k v ) -- three equivalent programs : def p1 := intersect s ( select m ( fun _ v => v > 10)) def p2 := select m ( fun k v => v > 10 && contains s k ) def p3 := filter s ( fun k => case lookup m k of | None => False | Just v => v > 10) In the definition p1 , we filter m before intersecting it with s . This uses a potentially optimized function intersect for intersecting sets, but comes at the cost of reifying the filtered version of m as a set and traversing it twice. The other two programs are manually fused: they combine all operations within one traversal. In p2 , we traverse m while using contains to query s , and in p3 , we traverse s while using lookup to query m . Although p2 and p3 avoid the unnecessary memory allocations of p1 , they have different performance depending on the relative sizes of s and m . Identifying the superior choice may be difficult to do statically or require runtime size checks that grow more complex for larger examples. Although p1 is more modular, achieving fusion seems to require either implementations of intersect for all pairs of data structures, or restriction to a single data structure for collections. The latter approach is often made internally within software such as database engines, but is awkward for general purpose programs. This situation suggests that a desirable interface is missing. In this work, we propose such an interface and implement it within three general purpose languages (Lean ( Moura and Ullrich 2021 ) , Rust ( Matsakis and Klock II 2014 ) , and Morphic ( Brandon et al. 2023 ) ). Our methods achieve fusion by internally using a data structure based on indexed streams ( Kovach et al. 2023 ) . Our key contribution is a fold function for indexed streams that can be ported and reliably optimized by general purpose language compilers capable of specialization. This function elegantly ties together the essential components of an iterator library: methods to define iterators for new data types, methods for transforming and combining iterators, and methods for collecting the values of an iterator into a concrete data structure of the user’s choice. We design and implement (for each language) these library components using an interface that is only mildly more complex than traditional iterators, while enabling asymptotic speedups in computation time and greater expressiveness. In addition to performance benefits, the small set of data concepts used in the library simplify the programming experience. All underying data structures are wrapped in a Map-like type that we denote ( k →ₛ v ) . Notationally, this emphasizes that a structure maps keys to values, just as a function does. Sets are represented with the type k →ₛ Bool , and hierarchical data structure types are akin to curried functions: k ₁ →ₛ k ₂ →ₛ v . We give several examples later to clarify and demonstrate the expressiveness of the library API. Here, we show that intersect and select can be defined in terms of two more primitive API functions: ⬇ -- new API : map : ( k → a → b ) → ( k →ₛ a ) → ( k →ₛ b ) zipWith : ( a → b → c ) → ( k →ₛ a ) → ( k →ₛ b ) → ( k →ₛ c ) variable ( s ₁ s ₂ : k →ₛ Bool ) ( m : k →ₛ v ) intersect s ₁ s ₂ := zipWith ( fun x y => x && y ) s ₁ s ₂ select m f := map f m def p1 := intersect s ( select m ( fun _ v => v > 10)) Thus, p1 , written exactly as before, encodes an algorithm that is fused (the use of map and zipWith does not allocate or perform extra traversals), and that achieves worst-case optimal performance ( Ngo et al. 2018 ) no matter which argument is smaller. Moreover, if its continuation is another stream operation, it avoids allocating the unnecessary Set that all three previous programs would allocate. Our contributions: • An indexed stream fold method that simplifies and generalizes previous approaches to compiling indexed streams that avoid intermediate memory allocations. • A design for the interfaces and methods needed to embed this in a practical library for working with associative container types (implemented in Lean, Morphic, and Rust). • Computer-checked proofs of correctness for the Lean library. As evaluation, we demonstrate that the generality of the approach does not introduce a detrimental performance overhead by comparing stream-based programs to idiomatic baselines in each language. Additionally, we give proofs of correctness for