doc/mcc/fir/benchmarks.tex

   1 %
   2 %
   3 %
   4
   5 \ifpaper
   6
   7 \sectionA{Benchmarks}
   8
   9 System benchmarks are shown in Figure~\ref{figure:benchmarks} for version 0.5.0 of the \mojave{}
  10 compiler, which was released in May 2002, about a year after the \mojave{} project started.  The
  11 performance numbers measure total real execution time on an unloaded 700MHz Intel Pentium III.  The
  12 \mojave{} system is freely available at \texttt{mojave.caltech.edu} under the GNU General Public License.
  13
  14 The \mojave{} system is currently under development, and benchmark performance varies widely.
  15 Performance numbers are given for several compilers.  The {\tt gcc} column uses the GNU compiler
  16 collection, version 2.96; {\tt gcc2} uses the {\tt -O2} optimization.  The {\tt mcc2} columns list performance
  17 numbers for the \mojave{} compiler.  For comparison purposes (only), the {\tt mcc2u} column lists
  18 performance without runtime safety checks.  In the current state of development, the {\tt mcc2}
  19 compiler performs only minimal optimization, including dead-code elimination, function inlining, and
  20 assembly peephole optimization.  Advanced \fir{} optimizations are fairly easy to implement, and the
  21 {\tt mcc6u} column lists performance numbers using an optimizer under development that implements
  22 alias analysis and partial redundancy elimination.  Naml benchmarks are similar, and include numbers
  23 for the INRIA OCaml compiler~\cite{remy:ocaml}, version 3.04.
  24
  25 The specific benchmarks include the following.  The {\tt fib} program computes the $n^\ms{th}$
  26 Fibonacci number (using the naive algorithm).  This benchmark is highly recursive, and the
  27 performance numbers reflect the use of continuation-passing style.  The {\tt mcc} programs allocate
  28 an exponential number of closures \emph{on the heap}, and much of the time is spent in garbage
  29 collection.
  30
  31 The {\tt mandel} benchmark computes a Mandelbrot set.  This is a corner case where {\tt mcc} C
  32 compiler, using the standard optimizations, happens to perform significantly better than {\tt gcc
  33 -O2} (performance numbers for {\tt gcc -O3} are shown in parentheses).  In contrast, the performance
  34 for Naml reflects the use of minimal optimization.  The {\tt mandel.ml} is implemented with
  35 fixed-point numbers, and each arithmetic operation is a function call.  The {\tt ocamlopt} compiler
  36 inlines the function calls, while {\tt mcc2} and {\tt ocamlc} do not.
  37
  38 The {\tt msort} benchmarks implement a bubble-sort algorithm, {\tt imat1} performs integer matrix
  39 multiplication, and {\tt fmat1} tests floating-point matrix multiplication.
  40
  41 The {\tt migrate} benchmark measures the ``minimal'' process migration time.  The program consists
  42 of a single migration call.  Nearly all of the time is spent in recompilation on the target machine.
  43
  44 The {\tt regex} algorithm is shown in Figure~\ref{figure:regex}, and represents a naive Unix-style
  45 regular-expression matcher, using transactions to simulate functional programming.  The function
  46 $\mb{atomic\_entry}(i)$ enters a transaction, with parameter $i$, $\mb{atomic\_commit}()$ commits
  47 the most recent transaction, and $\mb{atomic\_rollback}(i)$ rolls-back the most recent transaction
  48 with parameter $i$.  The time listed is for determining that the pattern
  49 \verb+*h*e*l*l*o*w*o*r*l*d*+ does \emph{not} occur in the text of the introduction to this paper.
  50 The benchmark enters 945341 transactions with a maximum transaction nesting depth of 6833.
  51
  52 \makefigure{figure:benchmarks}{Mojave benchmarks}{%
  53 \begin{center}
  54 \begin{tabular}{|l|lllll|}
  55 \hline
  56 \multicolumn{6}{|l|}{C benchmarks (time in seconds)}\\
  57 \hline\hline
  58 Name            & gcc  & gcc2 & mcc2 & mcc2u & mcc6u\\
  59 \hline
  60 fib 35          & 1.0  & 0.78 & 4.6  & 4.6  & 4.32\\
  61 mandel          & 54.7 & 42.1 (5.5) & 7.2  & 7.3  & 6.0\\
  62 msort1          & 3.83 & 1.15 & 5.92 & 3.01 & \\
  63 msort4          & 5.4  & 1.15 & 8.22 & 4.13 & \\
  64 imat1           & 37.1 & 6.27 & 27.9 & 17.3 & 7.6\\
  65 fmat1           & 8.9  & 2.98 & 10.2 & 8.33 & 4.86\\
  66 migrate         &      &      & 1.77 &      &\\
  67 regex           &      &      & 2.87 &      &\\
  68 \hline
  69 \multicolumn{6}{c}{}\\
  70 \hline
  71 \multicolumn{6}{|l|}{Naml benchmarks (time in seconds)}\\
  72 \hline\hline
  73 Name            & ocamlc & ocamlopt & mcc2 & mcc2u &\\
  74 \hline
  75 fib 35          & 3.89   & 0.61     & 8.33    & 7.81 & \\
  76 mandel          & 545    & 8.1      & 183     & 160 & \\
  77 \hline
  78 \end{tabular}
  79 \end{center}}
  80
  81 \makefigure{figure:regex}{Unix-style pattern matching using transactions}{%
  82 \begin{center}
  83 \begin{code}
  84 \mb{int} match(\mb{const char} *ppat, \mb{const char} *pbuf)\\
  85 \{\+\\
  86    \mb{if}(\mb{atomic\_entry}(0) != 0) \{\+\\
  87       print\_string("Pattern did not match");\\
  88       \mb{return}(FALSE);\-\\
  89    \}\\
  90    \mb{while}(*ppat != 0) \{\+\\
  91       \mb{if}(*ppat == '*') \{\+\\
  92          if(*pbuf == 0) \{ ppat++; \}\\
  93         \mb{else if}(\mb{atomic\_entry}(0) == 0) \{ pbuf++; \}\\
  94         \mb{else} \{ \mb{atomic\_commit}(); ppat++; \}\-\\
  95       \} \mb{else if}(*pbuf == *ppat) \{ ppat++; pbuf++; \}\\
  96       else \{ \mb{atomic\_rollback}(1); \}\-\\
  97    \}\\
  98    \mb{if}(*pbuf != 0) \{ \mb{atomic\_rollback}(1); \}\\
  99    print\_string("Pattern matched");\\
 100    return(TRUE);\-\\
 101 \}
 102 \end{code}
 103 \end{center}}
 104
 105 \ifpaper
 106 \section{Conclusion}
 107
 108 The \mojave{} compiler is in an early stage of development, but we believe that it demonstrates the
 109 feasibility of practical process migration and transactional computing.
 110 We intend the \mojave{} compiler to be a testbed for the development of distributed
 111 algorithms, as well as the application of domain-specific formal
 112 methods~\cite{aydemir:mojave-metaprl,granicz:hicss36-03}.
 113 The intermediate language has served as a solid foundation for safe multi-language compilation.
 114 \fi
 115
 116 \fi   % POPL paper?
 117
 118 % -*-
 119 % Local Variables:
 120 % Mode: LaTeX
 121 % fill-column: 100
 122 % TeX-master: "paper"
 123 % TeX-command-default: "LaTeX/dvips Interactive"
 124 % End:
 125 % -*-