5

Tracing the meta-level: PyPy's tracing JIT compiler

 3 years ago
source link: https://dl.acm.org/doi/10.1145/1565824.1565827
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

ABSTRACT

We attempt to apply the technique of Tracing JIT Compilers in the context of the PyPy project, i.e., to programs that are interpreters for some dynamic languages, including Python. Tracing JIT compilers can greatly speed up programs that spend most of their time in loops in which they take similar code paths. However, applying an unmodified tracing JIT to a program that is itself a bytecode interpreter results in very limited or no speedup. In this paper we show how to guide tracing JIT compilers to greatly improve the speed of bytecode interpreters. One crucial point is to unroll the bytecode dispatch loop, based on two kinds of hints provided by the implementer of the bytecode interpreter. We evaluate our technique by applying it to two PyPy interpreters: one is a small example, and the other one is the full Python interpreter.

References

  1. D. Ancona, M. Ancona, A. Cuni, and N. D. Matsakis. RPython: a step towards reconciling dynamically and statically typed OO languages. In Proceedings of the 2007 Symposium on Dynamic Languages, pages 53--64, Montreal, Quebec, Canada, 2007. ACM.
  2. V. Bala, E. Duesterwald, and S. Banerjia. Dynamo: a transparent dynamic optimization system. ACM SIGPLAN Notices, 35(5):1--12, 2000.
  3. C. F. Bolz. Automatic JIT Compiler Generation with Runtime Partial Evaluation. Master thesis, Heinrich-Heine-Universität Düsseldorf, 2008.
  4. C. F. Bolz, A. Kuhn, A. Lienhard, N. Matsakis, O. Nierstrasz, L. Renggli, A. Rigo, and T. Verwaest. Back to the Future in One Week --- Implementing a Smalltalk VM in PyPy, pages 123--139. 2008.
  5. C. F. Bolz and A. Rigo. How to not write a virtual machine. In Proceedings of the 3rd Workshop on Dynamic Languages and Applications (DYLA), 2007.
  6. C. Bruni and T. Verwaest. PyGirl: generating Whole-System VMs from High-Level prototypes using PyPy. In Tools, accepted for publication, 2009.
  7. S. Brunthaler. Virtual-Machine abstraction and optimization techniques. In Proceedings of the 4th International Workshop on Bytecode Semantics, Verification, Analysis and Transformation, 2009. to appear.
  8. M. Chang, M. Bebenita, A. Yermolovich, A. Gal, and M. Franz. Efficient Just-In-Time execution of dynamically typed languages via code specialization using precise runtime type inference. Technical Report ICS-TR-07-10, Donald Bren School of Information and Computer Science, University of California, Irvine, 2007.
  9. M. Chang, E. Smith, R. Reitmaier, M. Bebenita, A. Gal, C. Wimmer, B. Eich, and M. Franz. Tracing for Web 3.0: Trace compilation for the next generation web applications. In Proceedings of the 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, pages 71--80, Washington, DC, USA, 2009. ACM.
  10. C. Consel, L. Hornof, F. Noël, J. Noyé, and N. Volanschi. A uniform approach for compile-time and run-time specialization. Dagstuhl Seminar on Partial Evaluation, pages 54--72, 1996.
  11. C. Consel and F. Noël. A general approach for run-time specialization and its application to C. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 145--156, St. Petersburg Beach, Florida, United States, 1996. ACM.
  12. A. Cuni, D. Ancona, and A. Rigo. Faster than C#: Efficient implementation of dynamic languages on .NET. Accepted at ICOOOLPS'09.
  13. R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451--490, Oct. 1991.
  14. M. A. Ertl and D. Gregg. Retargeting JIT compilers by using C-Compiler generated executable code. In Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, pages 41--50. IEEE Computer Society, 2004.
  15. Y. Futamura. Partial evaluation of computation process - an approach to a Compiler-Compiler. Higher-Order and Symbolic Computation, 12(4):381--391, 1999.
  16. A. Gal, B. Eich, M. Shaver, D. Anderson, B. Kaplan, G. Hoare, D. Mandelin, B. Zbarsky, J. Orendorff, M. Bebenita, M. Chang, M. Franz, E. Smith, R. Reitmaier, and M. Haghighat. Trace-based Just-in-Time type specialization for dynamic languages. In PLDI, 2009.
  17. A. Gal and M. Franz. Incremental dynamic code generation with trace trees. Technical Report ICS-TR-06-16, University of California, Irvine, Nov. 2006.
  18. A. Gal, C. W. Probst, and M. Franz. HotpathVM: an effective JIT compiler for resource-constrained devices. In Proceedings of the 2nd International Conference on Virtual Execution Environments, pages 144--153, Ottawa, Ontario, Canada, 2006. ACM.
  19. B. Grant, M. Mock, M. Philipose, C. Chambers, and S. J. Eggers. DyC: an expressive annotation-directed dynamic compiler for C. Theoretical Computer Science, 248(1--2):147--199, 2000.
  20. U. Hölzle. Adaptive optimization for SELF: reconciling high performance with exploratory programming. Technical report, Stanford University, 1994.
  21. N. D. Jones, C. K. Gomard, and P. Sestoft. Partial evaluation and Automatic Program Generation. Prentice-Hall, Inc., 1993.
  22. I. Piumarta and F. Riccardi. Optimizing direct threaded code by selective inlining. SIGPLAN Not., 33(5):291--300, 1998.
  23. A. Rigo. Representation-based just-in-time specialization and the Psyco prototype for Python. In Proceedings of the 2004 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 15--26, Verona, Italy, 2004. ACM.
  24. A. Rigo and S. Pedroni. PyPy's approach to virtual machine construction. In Companion to the 21st ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 944--953, Portland, Oregon, USA, 2006. ACM.
  25. A. Rigo and S. Pedroni. JIT compiler architecture. Technical Report D08.2, PyPy, May 2007.
  26. G. T. Sullivan. Dynamic partial evaluation. In Proceedings of the Second Symposium on Programs as Data Objects, pages 238--256. Springer-Verlag, 2001.
  27. G. T. Sullivan, D. L. Bruening, I. Baron, T. Garnett, and S. Amarasinghe. Dynamic native optimization of interpreters. In Proceedings of the 2003 Workshop on Interpreters, Virtual Machines and Emulators, pages 50--57, San Diego, California, 2003. ACM.

Reviews

Reviewer: R. Clayton

Making sure that the cobbler's children are well shod has been a fruitful research line in programming language processing. Bolz et al. consider in this paper … (More)

Comments

0 Comments


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK