Deep Fusion for Efficient Nested Recursive Computations
summary
The compiler turns high-level functional programs over lists, sets, bags and maps into imperative code that removes intermediate collections in three steps: translate immutable collections to mutable using destination-passing style, let inner recursion reuse outer destinations, and avoid tiny per-depth allocations. The prototype targets nested flatMap, sparse tensor contractions and worst-case optimal joins, models collections as monoids, and demonstrates up to 4x performance improvement versus the standard Scala library on sparse-matrix transpose.
AI-written summary · about
chapters (6)
- 0:00Introduction
- 2:49Common Frameworks
- 3:21Loop Fusion
- 9:41Nested recursive computation
- 16:56Summary
- 17:56Questions
related talks
55mDeforestation and Program Fusion
18mLoop Fusion in Matrix Multiplications with Sparse Dependence
40mSuperfusion: Eliminating Intermediate Data Structures via Inductive Synthesis
19mCompile-Time Java Stream Fusion via mapMulti
14mAchieving High-Performance the Functional Way - A Functional Pearl on Expressing High...
19mCompiling Recurrences over Dense and Sparse Arrays
16mA Compiler for Fused Relational Operations on Multisets
16mCompile-Time Java Stream Fusion via mapMulti