Adding tuples to Java: a study in lightweight data structures

ABSTRACT

Java classes are very flexible, but this comes at a price. The main cost is that every class instance must be dynamically allocated. Their access by reference introduces pointer dereferences and complicates program analysis. These costs are particularly burdensome for small, ubiquitous data structures such as coordinates and state vectors. For such data structures a lightweight representation is desirable, allowing such data to be handled directly, similar to primitive types. A number of proposals introduce restricted or mutated variants of standard Java classes that could serve as lightweight representation, but the impact of these proposals has never been studied.Since we have implemented a Java compiler with lightweight data structures we are in a good position to do this evaluation. Our lightweight data structures are tuples. As we will show, their use can result in significant performance gains: for a number of existing benchmark programs using tuples we gain more than 50% in performance relative to our own compiler, and more than 20% relative to Sun's Hotspot 1.4 compiler. We expect similar performance gains for other implementations of lightweight data structures.With respect to the expressiveness of Java, lightweight variants of standard Java classes have little impact. In contrast, tuples add a different language construct that, as we will show, can lead to substantially more concise program code.

REFERENCES

• 1: David F. Bacon, Kava: a Java dialect with a uniform object model for lightweight classes, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.68-77, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376812]
• 2: Gilad Bracha , Martin Odersky , David Stoutamire , Philip Wadler, Making the future safe for the past: adding genericity to the Java programming language, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.183-200, October 18-22, 1998, Vancouver, British Columbia, Canada
• 3: J. M. Bull , L. A. Smith , L. Pottage , R. Freeman, Benchmarking Java against C and Fortran for scientific applications, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.97-105, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376823]
• 4: J.M. Bull, L.A. Smith, M.D. Westhead, D.S. Henty, and R.A. Davey. A benchmark suite for high performance Java. Concurrency -- Practice and Experience, 12(6):375--388, May 2000.
• 5: James Gosling. The evolution of numerical computing in Java. webpage.
• 6: James Gosling , Bill Joy , Guy Steele , Gilad Bracha, Java Language Specification, Second Edition: The Java Series, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 7: Java Grande forum benchmarks website. www.epcc.ed.ac.uk/javagrande.
• 8: Peeter Laud. Analysis for object inlining in Java. In Proceedings of the Joses Workshop, 2001.
• 9: X. Leroy. The effectiveness of type-based unboxing. In Proceedings of the Workshop "Types in Compilation", Amsterdam, June 1997.
• 10: J. E. Moreira , S. P. Midkiff , M. Gupta , P. V. Artigas , M. Snir , R. D. Lawrence, Java programming for high-performance numerical computing, IBM Systems Journal, v.39 n.1, p.21-56, January 2000
• 11: Michael Philippsen and Edwin Günthner. Complex numbers for Java. Concurrency: Practice and Experience, 12(6):477--491, May 2000.
• 12: C. van Reeuwijk. Timber download site. www.pds.twi.tudelft.nl/timber/downloading.html.
• 13: C. van Reeuwijk , F. Kuijlman , H. J. Sips, Spar: a set of extensions Java for scientific computation, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.58-67, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376811]
• 14: D. A. Turner, Miranda: a non-strict functional language with polymorphic types, Proc. of a conference on Functional programming languages and computer architecture, p.1-16, January 1985, Nancy, France
• 15: K. Yelick, G. Pike, C. Miyamoto, B. Liblit, A. Krishnamurthy, P. Hilfinger, S. Graham, D. Gay, Phil C., and A. Aiken. Titanium: a high-performance Java dialect. In ACM Workshop on Java for High-Performance Network Computing, pages 1--13, February 1998.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

General Terms:
Design, Languages, Performance

Keywords:
Java, lightweight data structures, tuple