Tracing for web 3.0: trace compilation for the next generation web applications

ABSTRACT

Today's web applications are pushing the limits of modern web browsers. The emergence of the browser as the platform of choice for rich client-side applications has shifted the use of in-browser JavaScript from small scripting programs to large computationally intensive application logic. For many web applications, JavaScript performance has become one of the bottlenecks preventing the development of even more interactive client side applications. While traditional just-in-time compilation is successful for statically typed virtual machine based languages like Java, compiling JavaScript turns out to be a challenging task. Many JavaScript programs and scripts are short-lived, and users expect a responsive browser during page loading. This leaves little time for compilation of JavaScript to generate machine code.

We present a trace-based just-in-time compiler for JavaScript that uses run-time profiling to identify frequently executed code paths, which are compiled to executable machine code. Our approach increases execution performance by up to 116% by decomposing complex JavaScript instructions into a simple Forth-based representation, and then recording the actually executed code path through this low-level IR. Giving developers more computational horsepower enables a new generation of innovative web applications.

REFERENCES

• 1: Adobe Systems Inc. ActionScript 3 Language Specification, 2006. http://livedocs.adobe.com/specs/actionscript/3/wwhelp/wwhimpl/js/html/wwhelp.htm.
• 2: Adobe Systems Inc. ActionScript Virtual Machine 2 Overview, 2007. http://www.adobe.com/devnet/actionscript/articles/avm2overview.pdf.
• 3: Adobe Systems Inc. Adobe Flex SDK, 2008. http://www.adobe.com/products/flex/flexdownloads/#sdk.
• 4: Ole Agesen , Jens Palsberg , Michael I. Schwartzbach, Type inference of SELF: analysis of objects with dynamic and multiple inheritance, Software—Practice & Experience, v.25 n.9, p.975-995, Sept. 1995 [doi>10.1002/spe.4380250903]
• 5: Alex Aiken , Brian Murphy, Static type inference in a dynamically typed language, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.279-290, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99621]
• 6: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 7: James R. Bell, Threaded code, Communications of the ACM, v.16 n.6, p.370-372, June 1973 [doi>10.1145/362248.362270]
• 8: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
• 9: Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
• 10: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 11: ECMA. Standard ECMA-262: ECMAScript Language Specification, 3rd edition, 1999. http://www.ecma-international.org/publications/standards/Ecma-262.htm.
• 12: M. Ertl and D. Gregg. The Structure and Performance of Efficient Interpreters. Journal of Instruction-Level Parallelism, 5:1--25, 2003.
• 13: Andreas Gal , Christian W. Probst , Michael Franz, HotpathVM: an effective JIT compiler for resource-constrained devices, Proceedings of the 2nd international conference on Virtual execution environments, June 14-16, 2006, Ottawa, Ontario, Canada [doi>10.1145/1134760.1134780]
• 14: C. Garrett, J. Dean, D. Grove, and C. Chambers. Measurement and Application of Dynamic Receiver Class Distributions. Technical Report CSE-TR-94-03-05, University of Washington, 1994.
• 15: Justin O. Graver , Ralph E. Johnson, A type system for Smalltalk, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.136-150, December 1989, San Francisco, California, United States [doi>10.1145/96709.96722]
• 16: Urs Hölzle , Craig Chambers , David Ungar, Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches, Proceedings of the European Conference on Object-Oriented Programming, p.21-38, July 15-19, 1991
• 17: Urs Hölzle , David Ungar, Optimizing dynamically-dispatched calls with run-time type feedback, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.326-336, June 20-24, 1994, Orlando, Florida, United States
• 18: JavaScript:TraceMonkey - Mozilla Wiki, 2008. https://wiki.mozilla.org/JavaScript:TraceMonkey.
• 19: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 20: Microsoft Developer Network. JScript (Windows Script Technologies), 2008. http://msdn.microsoft.com/en-us/library/hbxc2t98(VS.85).aspx.
• 21: R. Milner. A Theory of Type Polymorphism in Programming. Journal of Computer and System Sciences, 17(3):348--375, 1978.
• 22: Mozilla Foundation. SpiderMonkey (JavaScript-C) Engine, 2008. http://www.mozilla.org/js/spidermonkey/.
• 23: Mozilla Foundation. Tamarin Central, 2008. http://hg.mozilla.org/tamarin-central/.
• 24: Flemming Nielson, Program transformations in a denotational setting, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.359-379, July 1985 [doi>10.1145/3916.3917]
• 25: M. Pall. LuaJIT Roadmap, 2008. http://lua-users.org/lists/lua-l/2008-02/msg00051.html.
• 26: Yunhe Shi , Kevin Casey , M. Anton Ertl , David Gregg, Virtual machine showdown: Stack versus registers, ACM Transactions on Architecture and Code Optimization (TACO), v.4 n.4, p.1-36, January 2008 [doi>10.1145/1328195.1328197]
• 27: SunSpider JavaScript Benchmark, 2008. http://webkit.org/perf/sunspider-0.9/sunspider.html.
• 28: Surfin' Safari -- Blog Archive -- Announcing SquirrelFish, 2008. http://webkit.org/blog/189/announcing-squirrelfish/.
• 29: Satish Thatte, Type Inference with Partial Types, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.615-629, July 11-15, 1988
• 30: Mathew Zaleski , Angela Demke Brown , Kevin Stoodley, YETI: a graduallY extensible trace interpreter, Proceedings of the 3rd international conference on Virtual execution environments, June 13-15, 2007, San Diego, California, USA [doi>10.1145/1254810.1254823]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Design, Languages, Performance

Keywords:
dynamic compilation, dynamically typed languages, forth, javascript, tamarin, trace trees, tracing, type specialization