The Long Way to Deforestation: A Type Inference and Elaboration Technique for Removing Intermediate Data Structures

Deforestation is a compiler optimization that removes intermediate data structure allocations from functional programs to improve their efficiency. This is an old idea, but previous approaches have proved limited or impractical — they either only worked on compositions of predefined combinators (shortcut fusion), or involved the aggressive unfolding of recursive definitions until a depth limit was reached or a reoccurring pattern was found to tie the recursive knot, resulting in impractical algorithmic complexity and large amounts of code duplication. We present Lumberhack, a general-purpose deforestation approach for purely functional call-by-need and call-by-value programs. Lumberhack uses subtype inference to reason about data structure production and consumption and uses an elaboration pass to fuse the corresponding recursive definitions. It fuses large classes of mutually recursive definitions while avoiding much of the unproductive (and sometimes counter-productive) code duplication inherent in previous approaches. We prove the soundness of Lumberhack using step-indexed logical relations and experimentally demonstrate significant speedups in the standard nofib benchmark suite. We manually adapted nofib programs to call-by-value semantics and compiled them using the OCaml compiler. The average speedup over the 38 benchmarked programs is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mrow> <mml:mn>8.2</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> while the average code size increases by just about <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mn>1</mml:mn> <mml:mo>.</mml:mo> <mml:mn>79</mml:mn> <mml:mtext>x</mml:mtext> </mml:math> . In particular, 19 programs see their performance mostly unchanged, 17 programs improve significantly (by an average speedup of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mrow> <mml:mn>16.6</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> ), and only two programs visibly worsen (by an average slowdown of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mrow> <mml:mn>1.8</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> ). As a point of comparison, we measured that the well-proven but semi-manual list fusion technique of the Glasgow Haskell Compiler (GHC), which only works for call-by-need programs, had an average speedup of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mrow> <mml:mn>6.5</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> . Our technique is still in its infancy and misses some deforestation opportunities. We are confident that further refinements will yield greater performance improvements in the future.