Even Wiik Thomassen committed dacf70c

Finished conclusion.

  • Participants
  • Parent commits 12d49a3

Comments (0)

Files changed (1)

 The RPython translation toolchain from the PyPy project can be used to write
 \glspl{vm} in a high-level programming language, RPython. To reduce the
-overhead from the many abstractions provided by RPython,
-\eg garbage collection, excetions the toolchain provides a meta-tracing
-\gls{jit}. The meta-tracer can be used by any \gls{vm} written in RPython,
-almost automatically.
+overhead from the many abstractions provided by high-level languages, the
+toolchain provides a meta-tracing \gls{jit} compiler. The meta-tracer can be
+used by any \gls{vm} written in RPython, with little or no work
 The \glspl{vm} written in RPython cover many programming languages, most of
 them object-oriented, but none yet that are purely functional or lazy.
-Therefore this report posed the following question: \emph{Is the RPython
+Therefore this report asked the following question: \emph{Is the RPython
 translation toolchain suitable for purely functional and lazy languages, \eg
 the Haskell language?}
+The Haskell language has achieved great speed with ahead-of-time compilation,
+and attempts at trace-based \gls{jit} optimizations of Haskell have not yet
+been able to beat static compilation. Hence this report also questioned whether
+\emph{Haskell can benefit from trace-based \gls{jit} optimization techniques?}
+To answer these two questions a prototype Haskell \gls{vm} called PyHaskell was
+created. As PyHaskell is written in RPython, it includes the RPython
+meta-tracing\gls{jit}. The focus of this report has been to improve, optimize,
+and benchmark PyHaskell, with the hope of achieving performance comparable to
-, such as automatic
-memory management, inheritance, exceptions, and more.
+With the use of hints placed in the source code of \glspl{vm}, the meta-tracer
+can enable optimization techniques that should improve runtime performance.
+Many of these hints and techniques were undocumented before this report, hence
+the report should have practical utility for anyone with interest in writing a
+\gls{vm} in RPython.
-I set out to answer two specific research questions:
-    \item \emph{Can Haskell benefit from trace-based \gls{jit} optimization
-            techniques?}
+Unfortunately, issues with \gls{ghc}'s external Core functionality limits
+PyHaskell's support of the Haskell language and Haskell Prelude. These
+limitations prevented evaluation of PyHaskell with the standard Haskell
+benchmark suite, \textit{nofib}~\cite{partain}. Instead I have created a small
+collection of micro-benchmarks, to compare PyHaskell's runtime performance with
-PyHaskell, a prototype Haskell \gls{vm} with a meta-tracing \gls{jit} compiler,
+PyHaskell is slower than \gls{ghc} (with both -O0 and -O2) on thee of the
+benchmarks. On the \textit{Math} benchmark, PyHaskell is actually faster than
+\gls{ghc} -O0, and only 11.5\% slower than \gls{ghc} -O2. On the naive
+implementation of the Fibonacci sequence PyHaskell is 21.7\% slower than
+GHC-O0, and almost nine times slower than GHC-O2.
+As PyHaskell's performance is quite close to \gls{ghc}'s, the answer to the
+first question is \emph{yes}: the RPython translation toolchain
+\emph{is suitable} for purely functional, lazy languages.
-The conclusion should briefly summarize the problem
-statement and the general content of the work and the
-emphasize on the main contribution of the work.
-When writing the conclusion keep in mind that some
-readers may not have gone through the whole paper, but
-have jumped directly to the conclusion after having read
-the abstract in order the decide on the personal relevance
-of the paper. Therefore, the conclusion should be self-
-contained, which means that a reader should be able to
-understand the essence of the conclusion without having
-to read the whole paper.
-The conclusion typically ends with an outlook that de-
-scribes possible extensions of the presented approaches
-and of planned future work.
-% Utility
-% Is the work practically or theoretically useful? Although care should be
-% taken to assess the utility with respect to the potential of the assignment, not
-% the assignment itself, the candidate has a co-responsibility for the formulation
-% of the assignment, and her/his ability to pose adequate research questions and
-% formulate a technical approach should be taken into account.
-%TODO: Describe the utility of my results, maybe rather in conclusion?
+While the meta-tracer greatly speeds up PyHaskell, it does not yet beat
+\gls{ghc}. I cannot therefore answer the second question. More work is required
+to further improve PyHaskell, before a conclusion can be reached.
 \section{Future work}
-- Maybe suggest that the whole PyHaskell pipeline be scrapped.
-- extcore package does weird things, and is no longer maintained.
-- core2js is to verbose.
-- external Core to incomplete and outdated.
-- jscparser to incomplete, and hard to debug.
+Possible extensions of the work described in this report should be further
+attempts at optimizing PyHaskell. Some of the other \glspl{vm} written in
+RPython use optimization strategies in their object model, where they are
+able to use unboxed data structures. For PyHaskell, this could mean that
+instead of lists that are head-tail, it could use RPython lists that can be
+converted to arrays.
-The constructs created by PyHaskell is far from optimal.
+As mentioned in \autoref{sec:extcore-discussion}, I believe the current
+PyHaskell pipeline should be scrapped. A better approach might be to use the
+\gls{ghc} \gls{api} with more invariants. The \extcore package is no longer
+maintained, and it has some unwanted behavior (for example splitting up
+lambdas), a new pipeline should not depend on it. Furthermore, I would suggest
+writing a new parser, as the \gls{json} representation of external Core is too
-Instead use GHC-API, based on Lambdachine's work, to serialize
-Core (without types and kinds). Parse serialized Core directly, with
-an RPython parser.
+The constructs based on \citeauthor{launchbury}'s semantics for lazy languages
+perform well, but the mapping from Core to the constructs are far from optimal.
+For example, my changes to unboxed constructors described in
+\autoref{sec:pyhaskell-traces}, reduced the number of constructs and gave
+decent improvements.
-Still problem of GHC extensions and C code in Haskell Prelude, but
-much better than today's solution.