%!TEX root = ../Main.tex
\section{Introduction}
\label{s:Introduction}
Consider the following @filterMax@ function that increments a vector of integers and then selects just the positive results, while also determining the maximum value among the positive results. 
%
\begin{code}
  filterMax :: Vector Int -> (Vector Int, Int)
  filterMax vec1
   = let vec2    = map    (+ 1) vec1
         vec3    = filter (> 0) vec2
         n       = fold max 0 vec3
     in  (vec3, n)
\end{code}
%
A client programmer would rightfully expect this code to be fused into a single loop, one that keeps track of the maximum value while it builds the result vector. Unfortunately, existing fusion methods, such as @build@ / @fold@ fusion \cite{Gill:short-cut} and stream fusion \cite{Coutts:stream-fusion}, cannot completely fuse this code. Existing methods can eliminate the construction of @vec2@, but cannot fuse the production of @vec3@ into both of its consumers.  As a result, the entire intermediate @vec3@ will be materialized in memory by @filter@, before being read back by @fold@, requiring a second loop and superfluous memory traffic. If the input vector @vec1@ is large, then @filterMax@ is likely to be memory bound. For this reason, an incompletely fused @filterMax@ will be about 50\% slower than handwritten code that combines the @filter@ and @fold@ into a single loop.

Functions like @filterMax@ are common. For example, the core operation of the QuickHull algorithm is a @filterMax@-like computation (\S\ref{s:Benchmarks}). Branching data flows with multiple consumers are encountered whenever a function uses an array combinator that produces multiple result arrays, like with @unzip@, as the two results are typically fed into distinct consumers.

This problem of branching data flows is related to another problem with stream fusion, the standard in Haskell array fusion systems. Specifically, stream fusion of @zipWith@-like functions results in loops with duplicate loop counters, wasting precious processor registers and leading to redundant loop-counter arithmetic. This problem is especially severe in code produced by Data Parallel Haskell's vectorization transform~\cite{PeytonJones:harnessing-the-multicores} --- we have seen loops with eight duplicate loop counters! 

Our new fusion system solves these problems.  Our main contributions are the following:
\begin{itemize}
\item   We present a new fusion system, which we name \emph{flow fusion}. Our new system is based on Waters's series expressions~\cite{Waters:series-expressions}, extended to be useful in a functional setting. This system completely fuses functions like @filterMax@ and avoids the duplicate loop counters that are common to stream fusion (\S\ref{s:LoopGeneration}).

\item   We show how to use rank-2 quantified rate type variables and rate conversion witnesses to satisfy the \emph{online criteria} of the series expressions framework. Rate variables and the online criteria  are related to the clock calculi used in synchronous data-flow languages (\S\ref{s:RatesAndContexts}).

\item   We present key benchmarks showing performance improvement over existing array fusion systems. Properly fused QuickHull has a runtime half that of the stream fusion version, as its @filterMax@-like core requires only one array traversal instead of two (\S\ref{s:Benchmarks}).
\end{itemize} 

We have implemented flow fusion as a GHC optimization plugin that rewrites intermediate code generated by a user-facing library of Haskell source code. This Haskell library includes a fallback implementation of our array combinators, based on stream fusion, that is used if the plugin is not enabled. The code is available via \url{http://repa.ouroborus.net}.
