First draft of a short section about performance and design choices that affect it.
authorNorman Ramsey <nr@cs.tufts.edu>
Fri, 11 Jun 2010 16:33:47 +0000 (12:33 -0400)
committerNorman Ramsey <nr@cs.tufts.edu>
Fri, 11 Jun 2010 16:33:47 +0000 (12:33 -0400)
paper/dfopt.tex

index c445e3c..b695f16 100644 (file)
@@ -2820,6 +2820,76 @@ as the previous version, which is part of GHC, version 6.12.
 
 
 
+\section{Performance considerations}
+
+Our work on \hoopl\ is too preliminary for us to be able to say much
+about performance.
+It's~important to know how well \hoopl\ performs, but this is a
+comparative question, and there isn't much available to compare
+\hoopl\ with.
+For example, \hoopl\ is not a drop-in  replacement for an existing
+component of GHC; instead we introduced \hoopl\ to GHC as part of a
+major refactoring of \hoopl's back end.
+The version of GHC with \hoopl\ seems on the order of 10\%~slower than
+the previous version, but the is a property of the entire back end,
+not just of~\hoopl.
+
+What we can say is that the costs of using \hoopl\ seem reasonable;
+there is no ``big performance hit.''
+And~a somewhat similar library, written in an \emph{impure} functional
+language, actually improved performance in an apples-to-apples
+comparison with a library using a mutable control-flow graph
+\cite{ramsey-dias:applicative-flow-graph}. 
+
+A~thorough evaluation of \hoopl's performance must await future work.
+Here we enumerate some of the design decisions that affect
+performance.
+\begin{itemize}
+\item
+In \figref{graph}, we show a single concatenation operator for blocks.
+Using this representation, a block of $N$~nodes is represented using
+$2N-1$ heap objects.
+We~have also implemented a representation of blocks that include
+``cons-like'' and ``snoc-like'' constructors;
+this representation requires only $N+1$ heap objects.
+We~don't know what difference this choice makes to performance.
+\item
+In \secref{engine}, the @body@ function analyzes and (speculatively)
+rewrites the body of a control-flow graph, and @fixpoint@ iterates
+this analysis until it reaches a fixed point.
+The decorated graphs computed on earlier iterations are thrown away.
+But for each decorated graph of $N$~nodes, it is necessary to allocate
+at least $2N-1$~thunks.
+We~have written a version of \hoopl\ in which this overhead is
+eliminated by defining two separate functions: one to compute the
+fixed point, and the other to produce the rewritten graph.
+The version we present in \secref{engine} is much simpler and easier
+to maintain, but we don't know the real cost of the additional
+allocations.
+\item
+The representation of a forward-transfer function is private to
+\hoopl.
+Two representations are possible:
+we may store a triple of functions, one for each shape a node may
+have;
+or we may store a single, polymorphic function.
+If~we use triples throughout, the costs are straightforward, but the
+code is complex.
+If~we use a single, polymorphic function, we also have to use a
+\emph{shape classifier} (supplied by the client) when composing these
+functions in a way that is independent of the node type.
+Using a shape classifier may introduce extra @case@ discriminations
+every time a transfer function or rewrite function is applied to a
+node.
+We~don't know what effect these extra discriminations might have on
+performance.
+\end{itemize}
+In summary, \hoopl\ performs well enough for use in~GHC,
+but there is a great deal we don't know, and systematic investigation
+will be required.
+
+
+
 \section{Discussion}
 
 Regarding use cases, we do support other control-flow algorithms; for