diff options
Diffstat (limited to 'docs/paper.tex')
| -rw-r--r-- | docs/paper.tex | 37 |
1 files changed, 25 insertions, 12 deletions
diff --git a/docs/paper.tex b/docs/paper.tex index f3272557..453e1d66 100644 --- a/docs/paper.tex +++ b/docs/paper.tex @@ -153,11 +153,20 @@ language into JavaScript. For example, if compiling Java into JavaScript (as the Google Web Toolkit does), then one can benefit from the fact that Java's loops, ifs and so forth generally have a very direct parallel in JavaScript. But of course the downside in that approach is it yields a -compiler only for Java. We will also see in Section~\ref{sec:relooper} that it is in fact possible to reconstruct -a substantial part of the original high-level structure of the original code, -so that compiling LLVM assembly, while more difficult, can still yield good results. - -Another challenge in Emscripten is to achieve good performance. LLVM assembly +compiler only for Java. In Section~\ref{sec:relooper} +we present the `Relooper' algorithm, which generates high-level loop structures from the low-level +branching data present in LLVM assembly. It is similar to loop recovery algorithms used in decompilation +(see, for example, \cite{Cifuentes98assemblyto}, \cite{pro97}). +The main difference between the Relooper and standard loop recovery algorithms +is that the Relooper generates loops in a different language than that which was compiled originally, whereas +decompilers generally assume they are returning to the original language. The Relooper's +goal is not to accurately recreate the original source code, but rather to generate +native JavaScript control flow structures, which can then be implemented +efficiently in modern JavaScript engines. + +Another challenge in Emscripten is to maintain accuracy (that is, to +keep the results of the compiled code the same as the original) +while not sacrificing performance. LLVM assembly is an abstraction of how modern CPUs are programmed for, and its basic operations are not all directly possible in JavaScript. For example, if in LLVM we are to add two unsigned 8-bit numbers $x$ and $y$, with overflowing (e.g., 255 @@ -172,7 +181,7 @@ We conclude this introduction with a list of this paper's main contributions: \begin{itemize} \item We describe Emscripten itself, during which we detail its approach in compiling LLVM into JavaScript. -\item We give details of Emscripten's `Relooper' algorithm, which generates +\item We give details of Emscripten's Relooper algorithm, mentioned earlier, which generates high-level loop structures from low-level branching data, and prove its validity. \end{itemize} @@ -622,7 +631,7 @@ We will now take a look at some performance benchmarks: fannkuch (10) & 1.158 & \textbf{0.931} & 0.231 & 4.04 \\ fasta (2100000) & \textbf{1.115} & 1.128 & 0.452 & 2.47 \\ primes & \textbf{1.443} & 3.194 & 0.438 & 3.29 \\ - raytrace (7,256) & \textbf{1.930} & 2.944 & 0.228 & 8.47 \\ + raytrace (7,256) & \textbf{1.930} & 2.944 & 0.228 & 8.46 \\ dlmalloc (400,400) & 5.050 & \textbf{1.880} & 0.315 & 5.97 \\ \hline \end{tabular} @@ -657,7 +666,7 @@ using GCC 4.4.4. The last column is the ratio, that is, how much slower the Java when compared to gcc. All the tests were run on a MacBook Pro with an Intel i7 CPU clocked at 2.66GHz, running on Ubuntu 10.04. -Clearly the results greatly vary by the benchmark, with the generated JavaScript running from 2.47 to 8.47 times +Clearly the results greatly vary by the benchmark, with the generated JavaScript running from 2.47 to 8.46 times slower. There are also significant differences between the two JavaScript engines, with each better at some of the benchmarks. It appears that code that does simple numerical operations -- like @@ -666,10 +675,8 @@ accesses, for example due to using structures -- like the raytrace test -- will be slower. (The main issue with structures is that Emscripten does not `nativize' them yet, as it does to simple local variables.) -Code that has a mix of simple numerical operations and memory accesses -tends to run around 5-10 times slower than the most-optimized C++ code, -as we can see above. While this is a significant slowdown compared to -optimized native code, it is still more than fast enough for +Being 2.47 to 8.46 times slower than the most-optimized C++ code +is a significant slowdown, but it is still more than fast enough for many purposes, and the main point of course is that the code can run anywhere the web can be accessed. Further work on Emscripten is expected to improve the speed as well, as are improvements to LLVM, the Closure @@ -1072,6 +1079,9 @@ We thank the following people for their contributions to Emscripten: David LaPal List of languages that compile into JavaScript. Available at \url{https://github.com/jashkenas/coffee-script/wiki/List-of-languages-that-compile-to-JS}. Retrieved April 2011. +\bibitem[Cifuentes et~al. (1998)]{Cifuentes98assemblyto} C. Cifuentes, D. Simon and A. Fraboulet. +Assembly to High-Level Language Translation. In Int. Conf. on Softw. Maint, pp. 228--237, IEEE-CS Press, 1998. + \bibitem[Cooper et~al. (2006)]{links} E. Cooper, S. Lindley, P. Wadler and J. Yallop. Links: Web programming without tiers. In 5th International Symposium on Formal Methods for Components and Objects (FMCO), 2006. @@ -1091,6 +1101,9 @@ AFAX: Rich client/server web applications in F\#. Draft. Available at \url{http: \bibitem[Prabhakar (2007)]{gwt} C. Prabhakar. Google Web Toolkit: GWT Java Ajax Programming. Packt Publishing, 2007. +\bibitem[Proebsting et~al. (1997)]{pro97} T.A. Proebsting and S. A. Watterson. +Krakatoa: Decompilation in Java (Does Bytecode Reveal Source?) In Third USENIX Conference on Object-Oriented Technologies and Systems (COOTS), 1997. + \bibitem[Yee et~al. (2009)]{nacl} B. Yee, D. Sehr, G. Dardyk, J. B. Chen, R. Muth, T. Ormandy, S. Okasaka, N. Narula, and N. Fullagar. Native Client: A Sandbox for Portable, Untrusted x86 Native Code. In IEEE Symposium on |