skip to main content
10.1145/1869631.1869633acmconferencesArticle/Chapter ViewAbstractPublication PagessplashConference Proceedingsconference-collections
research-article

Efficient interpretation using quickening

Published:18 October 2010Publication History

ABSTRACT

Just-in-time compilers offer the biggest achievable payoff performance-wise, but their implementation is a non-trivial, time-consuming task affecting the interpreter's maintenance for years to come, too. Recent research addresses this issue by providing ways of leveraging existing just-in-time compilation infrastructures.

Though there has been considerable research on improving the efficiency of just-in-time compilers, the area of optimizing interpreters has gotten less attention as if the implementation of a dynamic translation system was the "ultima ratio" for efficiently interpreting programming languages. We present optimization techniques for improving the efficiency of interpreters without requiring just-in-time compilation thereby maintaining the ease-of-implementation characteristic that brought many people to implementing an interpreter in the first place.

References

  1. }}Scott B. Baden. High performance storage reclamation in an object-based memory system. Technical report, Berkeley, CA, USA, 1982. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. }}Jeffrey M. Barth. Shifting garbage collection overhead to compile time. Communications of the ACM, 20(7):513--518, July 1977. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. }}Carl Friedrich Bolz, Antonio Cuni, Maciej Fijalkowski, and Armin Rigo. Tracing the meta-level: PyPy's tracing JIT compiler. In Proceedings of the 4th Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems (ICOOOLPS '09), Lecture Notes in Computer Science, pages 18--25. Springer, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. }}James R. Bell. Threaded code. Communications of the ACM, 16(6):370--372, 1973. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. }}Stefan Brunthaler. Virtual-machine abstraction and optimization techniques. In Proceedings of the 4th International Workshop on Bytecode Semantics, Verification, Analysis and Transformation (BYTECODE '09), volume 253(5) of Electronic Notes in Theoretical Computer Science, pages 3--14, Amsterdam, The Netherlands, December 2009. Elsevier. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. }}Stefan Brunthaler. Efficient inline caching without dynamic translation. In Proceedings of the 2010 ACM Symposium on Applied Computing (SAC '10), pages 2155--2156, New York, NY, USA, March 2010. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. }}Stefan Brunthaler. Inline caching meets quickening. In Proceedings of the 24th European Conference on Object-Oriented Programming, Maribor, Slovenia, June 21-25, 2010 (ECOOP '10), volume 6183/2010 of Lecture Notes in Computer Science, pages 429--451. Springer, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. }}George E. Collins. A method for overlapping and erasure of lists. Communications of the ACM, 3(12):655--657, December 1960. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. }}Dalvik VM Instruction Formats. Online, (checked: May 2010) 2007.Google ScholarGoogle Scholar
  10. }}L. Peter Deutsch and Daniel G. Bobrow. An efficient, incremental, automatic garbage collector. Communications of the ACM, 19(9):522--526, 1976. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. }}M. Anton Ertl and David Gregg. Optimizing indirect branch prediction accuracy in virtual machine interpreters. In Proceedings of the SIGPLAN '03 Conference on Programming Language Design and Implementation (PLDI '03), pages 278--288, New York, NY, USA, 2003. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. }}M. Anton Ertl and David Gregg. The structure and performance of efficient interpreters. Journal of Instruction-Level Parallelism, 5:1--25, November 2003.Google ScholarGoogle Scholar
  13. }}M. Anton Ertl and David Gregg. Combining stack caching with dynamic superinstructions. In Proceedings of the 2004 Workshop on Interpreters, virtual machines and emulators (IVME '04), pages 7--14, New York, NY, USA, 2004. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. }}M. Anton Ertl. Stack caching for interpreters. In Proceedings of the SIGPLAN '95 Conference on Programming Language Design and Implementation (PLDI '95), pages 315--327, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. }}Brent Fulgham. The computer language benchmarks game. http://shootout.alioth.debian.org/.Google ScholarGoogle Scholar
  16. }}Intel. Intel turbo boost technology in Intel core microarchitecture (nehalem) based processors. online, November 2008.Google ScholarGoogle Scholar
  17. }}Pramod G. Joisha. Compiler optimizations for nondeferred reference counting garbage collection. In Proceedings of the 5th International Symposium on Memory Management (ISMM '06), pages 150--161, New York, NY, USA, 2006. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. }}Pramod G. Joisha. A principled approach to nondeferred reference-counting garbage collection. In Proceedings of the 4th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments (VEE '08), pages 131--140, New York, NY, USA, March 2008. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. }}Glenn Krasner, editor. Smalltalk-80: Bits of History, Words of Advice. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1983, reprinted with corrections 1984. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. }}Xavier Leroy. Java bytecode verification: Algorithms and formalizations. Journal of Automated Reasoning, 30(3-4):235--269, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. }}Steven Pemberton and Martin Daniels. Pascal Implementation: The P4 Compiler and Interpreter. Ellis Horwood, 1982.Google ScholarGoogle Scholar
  22. }}Yunhe Shi, Kevin Casey, M. Anton Ertl, and David Gregg. Virtual machine showdown: Stack versus registers. ACM Transactions on Architecture and Code Optimization, 4(4):1--36, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. }}David M. Ungar and David A. Patterson. chapter 11, Berkeley Smalltalk: Who Knows Where the Time Goes?, pages 189--206. September 1982.Google ScholarGoogle Scholar
  24. }}Allen Wirfs-Brock. Smalltalk-80: Bits of History, Words of Advice, chapter 4, Design Decisions for Smalltalk-80 Implementors, pages 41--56. In Krasner {Kra84}, 1982.Google ScholarGoogle Scholar
  25. }}David Wheeler. sloccount. http://www.dwheeler.com/sloccount/, May 2010.Google ScholarGoogle Scholar
  26. }}Kevin Williams, Jason McCandless, and David Gregg. Dynamic interpretation for dynamic scripting languages. In Proceedings of the 8th annual IEEE/ACM SIGMICRO/SIGPLAN International Symposium on Code Generation and Optimization (CGO '10), pages 278--287, April 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. }}Phil Winterbottom and Rob Pike. The design of the Inferno virtual machine. In Proceedings of the 42nd IEEE Computer Society International Conference, San Jose, California, US (COMPCON '97), pages 241--244, 1997.Google ScholarGoogle Scholar
  28. }}Alexander Yermolovich, Christian Wimmer, and Michael Franz. Optimization of dynamic languages using hierarchical layering of virtual machines. In Proceedings of the 5th Symposium on Dynamic Languages (DLS '09), pages 79--88, New York, NY, USA, 2009. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Efficient interpretation using quickening

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      DLS '10: Proceedings of the 6th symposium on Dynamic languages
      October 2010
      120 pages
      ISBN:9781450304054
      DOI:10.1145/1869631
      • cover image ACM SIGPLAN Notices
        ACM SIGPLAN Notices  Volume 45, Issue 12
        DLS '10
        December 2010
        107 pages
        ISSN:0362-1340
        EISSN:1558-1160
        DOI:10.1145/1899661
        Issue’s Table of Contents

      Copyright © 2010 ACM

      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 ACM 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]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 18 October 2010

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      Overall Acceptance Rate32of77submissions,42%

      Upcoming Conference

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader