[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3062341.3062381acmconferencesArticle/Chapter ViewAbstractPublication PagespldiConference Proceedingsconference-collections
research-article

Practical partial evaluation for high-performance dynamic language runtimes

Published: 14 June 2017 Publication History

Abstract

Most high-performance dynamic language virtual machines duplicate language semantics in the interpreter, compiler, and runtime system. This violates the principle to not repeat yourself. In contrast, we define languages solely by writing an interpreter. The interpreter performs specializations, e.g., augments the interpreted program with type information and profiling information. Compiled code is derived automatically using partial evaluation while incorporating these specializations. This makes partial evaluation practical in the context of dynamic languages: It reduces the size of the compiled code while still compiling all parts of an operation that are relevant for a particular program. When a speculation fails, execution transfers back to the interpreter, the program re-specializes in the interpreter, and later partial evaluation again transforms the new state of the interpreter to compiled code. We evaluate our approach by comparing our implementations of JavaScript, Ruby, and R with best-in-class specialized production implementations. Our general-purpose compilation system is competitive with production systems even when they have been heavily optimized for the one language they support. For our set of benchmarks, our speedup relative to the V8 JavaScript VM is 0.83x, relative to JRuby is 3.8x, and relative to GNU R is 5x.

References

[1]
R. Affeldt, H. Masuhara, E. Sumii, and A. Yonezawa. Supporting objects in run-time bytecode specialization. In Proceedings of the ASIAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 50–60. ACM Press, 2002.
[2]
O. Agesen and D. Detlefs. Mixed-mode bytecode execution. Technical report, Sun Microsystems, Inc., 2000.
[3]
B. Alpern, S. Augart, S. M. Blackburn, M. Butrico, A. Cocchi, P. Cheng, J. Dolby, S. Fink, D. Grove, M. Hind, K. S. McKinley, M. Mergen, J. E. B. Moss, T. Ngo, and V. Sarkar. The Jikes Research Virtual Machine project: Building an opensource research community. IBM Systems Journal, 44(2):399– 417, 2005.
[4]
M. Arnold, S. J. Fink, D. Grove, M. Hind, and P. F. Sweeney. Adaptive optimization in the Jalape˜no JVM. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 47– 65. ACM Press, 2000.
[5]
G. Benson. Zero and Shark: a zero-assembly port of Open-JDK, 2009.
[6]
C. F. Bolz and A. Rigo. How to not write virtual machines for dynamic languages. In Proceedings of the Workshop on Dynamic Languages and Applications, 2007.
[7]
C. F. Bolz and L. Tratt. The impact of meta-tracing on VM design and implementation. Science of Computer Programming, 98(3):408–421, 2015.
[8]
C. F. Bolz, A. Cuni, M. Fijałkowski, and A. Rigo. Tracing the meta-level: PyPy’s tracing JIT compiler. In Proceedings of the Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems, pages 18–25. ACM Press, 2009.
[9]
C. F. Bolz, M. Leuschel, and A. Rigo. Towards just-in-time partial evaluation of Prolog. In Proceedings of the International Conference on Logic-Based Program Synthesis and Transformation, pages 158–172. Springer-Verlag, 2010.
[10]
C. F. Bolz, A. Cuni, M. Fijałkowski, M. Leuschel, S. Pedroni, and A. Rigo. Runtime feedback in a meta-tracing JIT for efficient dynamic languages. In Proceedings of the Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems, pages 9:1– 9:8. ACM Press, 2011.
[11]
M. Chevalier-Boisvert, L. Hendren, and C. Verbrugge. Optimizing MATLAB through just-in-time specialization. In Proceedings of the International Conference on Compiler Construction, pages 46–65. Springer-Verlag, 2010.
[12]
B. Daloze, S. Marr, D. Bonetta, and H. Mössenböck. Efficient and thread-safe objects for dynamically-typed languages. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 642–659. ACM Press, 2016.
[13]
G. Duboscq, L. Stadler, T. Würthinger, D. Simon, C. Wimmer, and H. Mössenböck. Graal IR: An extensible declarative intermediate representation. In Proceedings of the Asia-Pacific Programming Languages and Compilers Workshop, 2013.
[14]
G. Duboscq, T. Würthinger, L. Stadler, C. Wimmer, D. Simon, and H. Mössenböck. An intermediate representation for speculative optimizations in a dynamic compiler. In Proceedings of the ACM Workshop on Virtual Machines and Intermediate Languages, 2013.
[15]
Y. Futamura. Partial evaluation of computation process–an approach to a compiler-compiler. Systems, Computers, Controls, 2(5):721–728, 1971.
[16]
N. Geoffray, G. Thomas, J. Lawall, G. Muller, and B. Folliot. VMKit: A substrate for managed runtime environments. In Proceedings of the International Conference on Virtual Execution Environments, pages 51–62, 2010.
[17]
GitHub. Graal multi-language VM, 2016.
[18]
I. Gouy. The computer language benchmarks game, 2016.
[19]
M. Grimmer, M. Rigger, R. Schatz, L. Stadler, and H. Mössenböck. TruffleC: Dynamic execution of C on a Java virtual machine. In Proceedings of the International Conference on the Principles and Practice of Programming in Java, pages 17–26. ACM Press, 2014.
[20]
M. Grimmer, R. Schatz, C. Seaton, T. Würthinger, and H. Mössenböck. Memory-safe execution of C on a Java VM. In Proceedings of the ACM Workshop on Programming Languages and Analysis for Security, pages 16–27. ACM Press, 2015.
[21]
M. Grimmer, C. Seaton, R. Schatz, T. Würthinger, and H. Mössenböck. High-performance cross-language interoperability in a multi-language runtime. In Proceedings of the Dynamic Languages Symposium, pages 78–90. ACM Press, 2015.
[22]
M. Grimmer, C. Seaton, T. Würthinger, and H. Mössenböck. Dynamically composing languages in a modular way: Supporting C extensions for dynamic languages. In Proceedings of the International Conference on Modularity, pages 1–13. ACM Press, 2015.
[23]
U. Hölzle and D. Ungar. A third-generation SELF implementation: Reconciling responsiveness with performance. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 229–243. ACM Press, 1994.
[24]
U. Hölzle, C. Chambers, and D. Ungar. Optimizing dynamically-typed object-oriented languages with polymorphic inline caches. In Proceedings of the European Conference on Object-Oriented Programming, pages 21–38. Springer-Verlag, 1991.
[25]
U. Hölzle, C. Chambers, and D. Ungar. Debugging optimized code with dynamic deoptimization. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 32–43. ACM Press, 1992.
[26]
C. Humer, C. Wimmer, C. Wirth, A. Wöß, and T. Würthinger. A domain-specific language for building self-optimizing AST interpreters. In Proceedings of the International Conference on Generative Programming and Component Engineering, pages 123–132. ACM Press, 2014.
[27]
N. D. Jones and A. J. Glenstrup. Program generation, termination, and binding-time analysis. In Generative Programming and Component Engineering, volume 2487 of Lecture Notes in Computer Science, pages 1–31. Springer-Verlag, 2002.
[28]
T. Kotzmann and H. Mössenböck. Run-time support for optimizations based on escape analysis. In Proceedings of the International Symposium on Code Generation and Optimization, pages 49–60. IEEE Computer Society, 2007.
[29]
C. Lattner and V. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In Proceedings of the International Symposium on Code Generation and Optimization, pages 75–86. IEEE Computer Society, 2004.
[30]
MacRuby. MacRuby, 2013.
[31]
S. Marr, B. Daloze, and H. Mössenböck. Cross-language compiler benchmarking: Are we fast yet? In Proceedings of the Dynamic Languages Symposium, pages 120–131. ACM Press, 2016.
[32]
H. Masuhara and A. Yonezawa. A portable-approach to dynamic optimization in run-time specialization. New Generation Computing, 20(1):101–124, 2002.
[33]
F. Morandat, B. Hill, L. Osvald, and J. Vitek. Evaluating the design of the R language: Objects and functions for data analysis. In Proceedings of the European Conference on Object-Oriented Programming, pages 104–131. Springer-Verlag, 2012.
[34]
C. Nutter. So you want to optimize Ruby, 2012.
[35]
Optcarrot. Optcarrot: A NES emulator for Ruby benchmark, 2016.
[36]
Oracle. Oracle Labs GraalVM downloads, 2016.
[37]
M. Paleczny, C. Vick, and C. Click. The Java HotSpot TM server compiler. In Proceedings of the Java Virtual Machine Research and Technology Symposium, pages 1–12. USENIX, 2001.
[38]
M. Rigger, M. Grimmer, C. Wimmer, T. Würthinger, and H. Mössenböck. Bringing low-level languages to the JVM: Efficient execution of LLVM IR on Truffle. In Proceedings of the ACM Workshop on Virtual Machines and Intermediate Languages, pages 6–15. ACM Press, 2016.
[39]
A. Rigo and S. Pedroni. PyPy’s approach to virtual machine construction. In Companion to the ACM SIGPLAN Conference on Object Oriented Programming Systems, Languages, and Applications, pages 944–953. ACM Press, 2006.
[40]
T. Rompf, A. K. Sujeeth, K. J. Brown, H. Lee, H. Chafi, and K. Olukotun. Surgical precision JIT compilers. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 41–52. ACM Press, 2014.
[41]
Rubinius. Rubinius: Use Ruby, 2013.
[42]
G. Savrun-Yenic¸eri, M. L. Van de Vanter, P. Larsen, S. Brunthaler, and M. Franz. An efficient and generic event-based profiler framework for dynamic languages. In Proceedings of the International Conference on the Principles and Practice of Programming in Java, pages 102–112. ACM Press, 2015.
[43]
U. P. Schultz, J. L. Lawall, C. Consel, and G. Muller. Towards automatic specialization of Java programs. In Proceedings of the European Conference on Object-Oriented Programming, pages 367–390. Springer-Verlag, 1999.
[44]
U. P. Schultz, J. L. Lawall, and C. Consel. Automatic program specialization for Java. In ACM Transactions on Programming Languages and Systems, pages 452–499. ACM Press, 2003.
[45]
C. Seaton. AST specialisation and partial evaluation for easy high-performance metaprogramming. In Workshop on Meta-Programming Techniques and Reflection, 2016.
[46]
C. Seaton, M. L. Van De Vanter, and M. Haupt. Debugging at full speed. In Proceedings of the Workshop on Dynamic Languages and Applications, pages 2:1–2:13. ACM Press, 2014.
[47]
A. Shali and W. R. Cook. Hybrid partial evaluation. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 375–390. ACM Press, 2011.
[48]
Y. Shi, K. Casey, M. A. Ertl, and D. Gregg. Virtual machine showdown: Stack versus registers. ACM Transactions on Architecture and Code Optimization, 4(4), 2008.
[49]
D. Simon, C. Wimmer, B. Urban, G. Duboscq, L. Stadler, and T. Würthinger. Snippets: Taking the high road to a low level. ACM Transactions on Architecture and Code Optimization, 12 (2):20:1–20:25, 2015.
[50]
L. Stadler, C. Wimmer, T. Würthinger, H. Mössenböck, and J. Rose. Lazy continuations for Java virtual machines. In Proceedings of the International Conference on the Principles and Practice of Programming in Java, pages 143–152. ACM Press, 2009.
[51]
L. Stadler, T. Würthinger, and C. Wimmer. Efficient coroutines for the Java platform. In Proceedings of the International Conference on the Principles and Practice of Programming in Java, pages 20–28. ACM Press, 2010.
[52]
L. Stadler, T. Würthinger, and H. Mössenböck. Partial escape analysis and scalar replacement for java. In Proceedings of the International Symposium on Code Generation and Optimization, pages 165–174. ACM Press, 2014.
[53]
L. Stadler, A. Welc, C. Humer, and M. Jordan. Optimizing R language execution via aggressive speculation. In Proceedings of the Dynamic Languages Symposium, pages 84–95. ACM Press, 2016.
[54]
TC39. Official ecmascript conformance test suite, 2016.
[55]
Unladen Swallow. unladen-swallow, 2009.
[56]
S. Urbanek. R benchmarks 2.5, 2008.
[57]
M. L. Van De Vanter. Building debuggers and other tools: We can ”have it all”. In Proceedings of the Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems, pages 2:1–2:3. ACM Press, 2015.
[58]
C. Wimmer, M. Haupt, M. L. Van De Vanter, M. Jordan, L. Daynès, and D. Simon. Maxine: An approachable virtual machine for, and in, Java. ACM Transactions on Architecture and Code Optimization, 9(4):30:1–30:24, 2013.
[59]
C. Wimmer, V. Jovanovic, E. Eckstein, and T. Würthinger. One compiler: Deoptimization to optimized code. In Proceedings of the International Conference on Compiler Construction, pages 55–64. ACM Press, 2017.
[60]
A. Wöß, C. Wirth, D. Bonetta, C. Seaton, C. Humer, and H. Mössenböck. An object storage model for the truffle language implementation framework. In Proceedings of the International Conference on the Principles and Practice of Programming in Java, pages 133–144. ACM Press, 2014.
[61]
T. Würthinger, C. Wimmer, A. Wöß, L. Stadler, G. Duboscq, C. Humer, G. Richards, D. Simon, and M. Wolczko. One VM to rule them all. In Proceedings of Onward! ACM Press, 2013.
[62]
W. Zhang, P. Larsen, S. Brunthaler, and M. Franz. Accelerating iterators in optimizing AST interpreters. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 727–743. ACM Press, 2014.

Cited By

View all
  • (2024)Incremental Specialization of Network ProgramsProceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696870(264-272)Online publication date: 18-Nov-2024
  • (2024)BIFROST: A Future Graph Database Runtime2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00448(5605-5613)Online publication date: 13-May-2024
  • (2024)ClangOz: Parallel constant evaluation of C++ map and reduce operationsJournal of Computer Languages10.1016/j.cola.2024.10129881(101298)Online publication date: Nov-2024
  • Show More Cited By

Index Terms

  1. Practical partial evaluation for high-performance dynamic language runtimes

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    PLDI 2017: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation
    June 2017
    708 pages
    ISBN:9781450349888
    DOI:10.1145/3062341
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 14 June 2017

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. dynamic languages
    2. language implementation
    3. optimization
    4. partial evaluation
    5. virtual machine

    Qualifiers

    • Research-article

    Conference

    PLDI '17
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 406 of 2,067 submissions, 20%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)80
    • Downloads (Last 6 weeks)18
    Reflects downloads up to 18 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Incremental Specialization of Network ProgramsProceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696870(264-272)Online publication date: 18-Nov-2024
    • (2024)BIFROST: A Future Graph Database Runtime2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00448(5605-5613)Online publication date: 13-May-2024
    • (2024)ClangOz: Parallel constant evaluation of C++ map and reduce operationsJournal of Computer Languages10.1016/j.cola.2024.10129881(101298)Online publication date: Nov-2024
    • (2024)Partial program analysis for staged compilation systemsFormal Methods in System Design10.1007/s10703-024-00458-xOnline publication date: 13-Jun-2024
    • (2024)Performance Analysis of Compiler Support for Parallel Evaluation of C++ Constant ExpressionsSoftware, System, and Service Engineering10.1007/978-3-031-51075-5_6(129-152)Online publication date: 3-Jan-2024
    • (2023)Beehive SPIR-V Toolkit: A Composable and Functional API for Runtime SPIR-V Code GenerationProceedings of the 15th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3623507.3623555(61-72)Online publication date: 18-Oct-2023
    • (2023)TASTyTruffle: Just-in-Time Specialization of Parametric PolymorphismProceedings of the ACM on Programming Languages10.1145/36228537:OOPSLA2(1561-1588)Online publication date: 16-Oct-2023
    • (2023)AST vs. Bytecode: Interpreters in the Age of Meta-CompilationProceedings of the ACM on Programming Languages10.1145/36228087:OOPSLA2(318-346)Online publication date: 16-Oct-2023
    • (2023)Exploiting Partially Context-sensitive Profiles to Improve Performance of Hot CodeACM Transactions on Programming Languages and Systems10.1145/361293745:4(1-64)Online publication date: 13-Sep-2023
    • (2023)Collecting Cyclic Garbage across Foreign Function Interfaces: Who Takes the Last Piece of Cake?Proceedings of the ACM on Programming Languages10.1145/35912447:PLDI(591-614)Online publication date: 6-Jun-2023
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media