Data Flow Fusion with Series Expressions in Haskell

Ben Lippmeier, Manuel M. T. Chakravarty, Gabriele Keller, and Amos Robinson.

In Proceedings of ACM SIGPLAN Haskell Symposium 2013, ACM Press, 2013.

Existing approaches to array fusion can deal with straight-line producer consumer pipelines, but cannot fuse branching data flows where a generated array is consumed by several different consumers. Branching data flows are common and natural to write, but a lack of fusion leads to the creation of an intermediate array at every branch point. We present a new array fusion system that handles branches, based on Waters's series expression framework, but extended to work in a functional setting. Our system also solves a related problem in stream fusion, namely the introduction of duplicate loop counters. We demonstrate speedup over existing fusion systems for several key examples.

PDF (12 pages)

This page is part of Manuel Chakravarty's WWW-stuff.