Compiling scheme to JVM bytecode:: a performance study

ABSTRACT

We have added a Java virtual machine (henceforth JVM) bytecode generator to the optimizing Scheme-to-C compiler Bigloo. We named this new compiler BiglooJVM. We have used this new compiler to evaluate how suitable the JVM bytecode is as a target for compiling strict functional languages such as Scheme. In this paper, we focus on the performance issue. We have measured the execution time of many Scheme programs when compiled to C and when compiled to JVM. We found that for each benchmark, at least one of our hardware platforms ran the BiglooJVM version in less than twice the time taken by the Bigloo version. In order to deliver fast programs the generated JVM bytecode must be carefully crafted in order to benefit from the speedup of just-in-time compilers.

REFERENCES

• 1: Ali-Reza Adl-Tabatabai , Michał Cierniak , Guei-Yuan Lueh , Vishesh M. Parikh , James M. Stichnoth, Fast, effective code generation in a just-in-time Java compiler, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.280-290, June 17-19, 1998, Montreal, Quebec, Canada
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.47-65, October 2000, Minneapolis, Minnesota, United States
• 4: Henry G. Baker, CONS should not CONS its arguments, part II: Cheney on the M.T.A., ACM SIGPLAN Notices, v.30 n.9, p.17-20, Sept. 1995 [doi>10.1145/214448.214454]
• 5: Nick Benton , Andrew Kennedy , George Russell, Compiling standard ML to Java bytecodes, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.129-140, September 26-29, 1998, Baltimore, Maryland, United States
• 6: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 7: P. Botner. Kawa: Compiling Scheme to Java. In Lisp users conference, Berkeley, California, USA, November 1998.
• 8: Wim De Pauw , Gary Sevitsky, Visualizing Reference Patterns for Solving Memory Leaks in Java, Proceedings of the 13th European Conference on Object-Oriented Programming, p.116-134, June 14-18, 1999
• 9: M. DePristo. SINTL: A Strongly-Typed Generic Intermediate Language for Scheme. Northwestern University, Computer Science Honors Thesis, 2000.
• 10: P. H. Hartel et al. Pseudoknot: a Float-Intensive Benchmark for Functional Compilers. Journal of Functional Programming, 6(4):621--655, 1996.
• 11: M. Feeley, J. Miller, G. Rozas, and J. Wilson. Compiling Higher-Order Languages into Fully Tail-Recursive Portable C. Technical Report Rapport technique 1078, Université de Montréal, Département d'informatique et r.o., August 1997.
• 12: E. Gagnon and L. Hendren. SableVM: A Research Framework for the Efficient Execution of Java Bytecode. Technical Report 2000-3, McGill University, School of Computer Science, November 2000.
• 13: D. Gudeman. Representing Type Information in Dynamically Typed Languages. Technical report, University of Arizona, Departement of Computer Science, Gould-Simpson Building, The University of Arizona, Tucson, AZ 85721, April 1993.
• 14: U. Hölzle. Adaptive Optimization for Self: Reconciling High Performance with Exploratory Programming. PhD thesis, Stanford University, August 1994.
• 15: 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]
• 16: M. Honeyford. Weighing in on Java native compilation. Technical Report developerWorks, IBM, January 2002.
• 17: Cheng-Hsueh A. Hsieh , John C. Gyllenhaal , Wen-mei W. Hwu, Java bytecode to native code translation: the caffeine prototype and preliminary results, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.90-99, December 02-04, 1996, Paris, France
• 18: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams Iv , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand, Revised Report on the Algorithmic Language Scheme, Higher-Order and Symbolic Computation, v.11 n.1, p.7-105, August 1998 [doi>10.1023/A:1010051815785]
• 19: A. Krall, Efficient JavaVM Just-in-Time Compilation, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.205, October 12-18, 1998
• 20: Xavier Leroy, Unboxed objects and polymorphic typing, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.177-188, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143205]
• 21: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 22: O. Pinali Doederlein. The Java Performance Report -- Part IIA. http://www.javalobby.org/features/jpr, August 2000.
• 23: Christian Queinnec, The influence of browsers on evaluators or, continuations to program web servers, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.23-33, September 2000
• 24: M. Schinz and M. Odersky. Tail call elimination of the Java Virtual Machine. In Proceedings of Babel'01, Florence, Italy, September 2001.
• 25: N. Séniak. Théorie et pratique de Sqil: un langage intermédiaire pour la compilation des langages fonctionnels. PhD thesis, Universitée Pierre et Marie Curie (Paris VI), November 1991.
• 26: Manuel Serrano, Control flow analysis: a functional languages compilation paradigm, Proceedings of the 1995 ACM symposium on Applied computing, p.118-122, February 26-28, 1995, Nashville, Tennessee, United States [doi>10.1145/315891.315934]
• 27: Manuel Serrano, Inline Expansion: When and How?, Proceedings of the9th International Symposium on Programming Languages: Implementations, Logics, and Programs: Including a Special Trach on Declarative Programming Languages in Education, p.143-157, September 03-05, 1997
• 28: Manuel Serrano , Marc Feeley, Storage use analysis and its applications, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.50-61, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 29: Manuel Serrano , Pierre Weis, Bigloo: A Portable and Optimizing Compiler for Strict Functional Languages, Proceedings of the Second International Symposium on Static Analysis, p.366-381, September 25-27, 1995
• 30: O. Shivers, Control flow analysis in scheme, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.164-174, June 20-24, 1988, Atlanta, Georgia, United States
• 31: T. Suganuma , T. Ogasawara , M. Takeuchi , T. Yasue , M. Kawahito , K. Ishizaki , H. Komatsu , T. Nakatani, Overview of the IBM Java just-in-time compiler, IBM Systems Journal, v.39 n.1, p.175-193, January 2000
• 32: Sun Microsystems. The Java HotSpot Performance Engine, April 1999.
• 33: David Tarditi , Peter Lee , Anurag Acharya, No assembly required: compiling standard ML to C, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.2, p.161-177, June 1992 [doi>10.1145/151333.151343]
• 34: Tolksdorf. Compiling to JVM. http://grunge.cs.tu-berlin.de/-tolk, 2000.
• 35: T. VanDrunen, A. Hosking, and J. Palsberg. Reducing loads and stores in stack architectures, 2000.
• 36: David Wakeling, Compiling lazy functional programs for the Java Virtual Machine, Journal of Functional Programming, v.9 n.6, p.579-603, November 1999 [doi>10.1017/S0956796899003603]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

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

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems
          Subjects: Evaluation strategies

General Terms:
Experimentation, Languages, Measurement, Performance

Keywords:
Java virtual machine, compilation, functional languages, scheme