Representation-based just-in-time specialization and the psyco prototype for python

ABSTRACT

A powerful application of specialization is to remove interpretative overhead: a language can be implemented with an interpreter, whose performance is then improved by specializing it for a given program source. This approach is only moderately successful with very high level languages, where the operation of each single step can be highly dependent on run-time data and context. In the present paper, the Psyco prototype for the Python language is presented. It introduces two novel techniques. The first is just-in-time specialization, or specialization by need, which introduces the "unlifting" ability for a value to be promoted from run-time to compile-time during specialization -- the inverse of the lift operator of partial evaluation. Its presence gives an unusual and powerful perspective on the specialization process. The second technique is representations, a theory of data-oriented specialization generalizing the traditional specialization domains (i.e. the compile-time/run-time dichotomy).

REFERENCES

• 1: John Aycock, A brief history of just-in-time, ACM Computing Surveys (CSUR), v.35 n.2, p.97-113, June 2003 [doi>10.1145/857076.857077]
• 2: Mathias Braux , Jacques Noyé, Towards partially evaluating reflection in Java, Proceedings of the 2000 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.2-11, January 22-23, 2000, Boston, Massachusetts, United States
• 3: Craig Chambers, Staged compilation, Proceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, January 14-15, 2002, Portland, Oregon
• 4: Craig David Chambers, The design and implementation of the self compiler, an optimizing compiler for object-oriented programming languages, Stanford University, Stanford, CA, 1992
• 5: Charles Consel , Siau Cheng Khoo, Parameterized partial evaluation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.3, p.463-493, July 1993 [doi>10.1145/169683.174155]
• 6: Jeffrey Dean , Craig Chambers , David Grove, Selective specialization for object-oriented languages, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.93-102, June 18-21, 1995, La Jolla, California, United States
• 7: Dawson R. Engler, VCODE: a retargetable, extensible, very fast dynamic code generation system, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.160-170, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 8: A. Haraldsson. A program manipulation system based on partial evaluation. PhD thesis, Linköping Univ., Sweden, Linköping Studies in Science and Technology Dissertations 14, 1977.
• 9: Urs Hölzle , David Ungar, Reconciling responsiveness with performance in pure object-oriented languages, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.355-400, July 1996 [doi>10.1145/233561.233562]
• 10: Dan Ingalls , Ted Kaehler , John Maloney , Scott Wallace , Alan Kay, Back to the future: the story of Squeak, a practical Smalltalk written in itself, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.318-326, October 05-09, 1997, Atlanta, Georgia, United States
• 11: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 12: Gregor Kiczales , Jim Des Rivieres, The Art of the Metaobject Protocol, MIT Press, Cambridge, MA, 1991
• 13: C. Lattner. LLVM: An Infrastructure for Multi-Stage Optimization. Master's thesis, Computer Science Dept., University of Illinois at Urbana-Champaign, Urbana, IL, Dec 2002. See http://llvm.cs.uiuc.edu.
• 14: Peter Lee , Mark Leone, Optimizing ML with run-time code generation, ACM SIGPLAN Notices, v.39 n.4, April 2004 [doi>10.1145/989393.989448]
• 15: Hidehiko Masuhara , Satoshi Matsuoka , Kenichi Asai , Akinori Yonezawa, Compiling away the meta-level in object-oriented concurrent reflective languages using partial evaluation, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.300-315, October 15-19, 1995, Austin, Texas, United States
• 16: I. Piumarta. J3 for squeak. http://www-sor.inria.fr/~piumarta/squeak/unix/zip/j3-2.6.0/doc/j3/.
• 17: C. Pu, H. Massalin, and J. Ioannidis. The synthesis kernel. USENIX Association, editor, Computing Systems, 1(Winter):11--32, 1988.
• 18: A. Rigo. The ultimate psyco guide. http://psyco.sourceforge.net/psycoguide.ps.gz.
• 19: M. Salib. Starkiller: A static type inferencer and compiler for python. In Proceedings of the EuroPython conference, 2004. http://web.mit.edu/msalib/www/writings/talks/.
• 20: Gregory T. Sullivan, Dynamic Partial Evaluation, Proceedings of the Second Symposium on Programs as Data Objects, p.238-256, May 21-23, 2001
• 21: G. van Rossum. Python reference manual. http://docs.python.org/ref/ref.html.
• 22: John Whaley, Partial method compilation using dynamic profile information, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.166-179, October 14-18, 2001, Tampa Bay, FL, USA

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Keywords:
just-in-time specialization, python, representation, unlift