Data size optimizations for java programs

ABSTRACT

We present a set of techniques for reducing the memory consumption of object-oriented programs. These techniques include analysis algorithms and optimizations that use the results of these analyses to eliminate fields with constant values, reduce the sizes of fields based on the range of values that can appear in each field, and eliminate fields with common default values or usage patterns. We apply these optimizations both to fields declared by the programmer and to implicit fields in the runtime object header. Although it is possible to apply these techniques to any object-oriented program, we expect they will be particularly appropriate for memory-limited embedded systems.We have implemented these techniques in the MIT FLEX compiler system and applied them to the programs in the SPECjvm98 benchmark suite. Our experimental results show that our combined techniques can reduce the maximum live heap size required for the programs in our benchmark suite by as much as 40%. Some of the optimizations reduce the overall execution time; others may impose modest performance penalties.

REFERENCES

• 1: Ole Agesen , David Detlefs , Alex Garthwaite , Ross Knippel , Y. S. Ramakrishna , Derek White, An efficient meta-lock for implementing ubiquitous synchronization, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.207-222, November 01-05, 1999, Denver, Colorado, United States
• 2: Aneesh Aggarwal , Keith H. Randall, Related field analysis, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.214-220, June 2001, Snowbird, Utah, United States
• 3: Jonathan Aldrich , Craig Chambers , Emin Gün Sirer , Susan J. Eggers, Static Analyses for Eliminating Unnecessary Synchronization from Java Programs, Proceedings of the 6th International Symposium on Static Analysis, p.19-38, September 22-24, 1999
• 4: C. Scott Ananian. Silicon C: A hardware backend for SUIF. Available from http://flexc.lcs.mit.edu/SiliconC/paper.pdf, May 1998.
• 5: C. Scott Ananian. The static single information form. Technical Report MIT-LCS-TR-801, Massachusetts Institute of Technology, 1999. Available from http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-801.pdf.
• 6: David F. Bacon , Stephen J. Fink , David Grove, Space- and Time-Efficient Implementation of the Java Object Model, Proceedings of the 16th European Conference on Object-Oriented Programming, p.111-132, June 10-14, 2002
• 7: David F. Bacon , Ravi Konuru , Chet Murthy , Mauricio Serrano, Thin locks: featherweight synchronization for Java, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.258-268, June 17-19, 1998, Montreal, Quebec, Canada
• 8: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
• 9: Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.35-46, November 01-05, 1999, Denver, Colorado, United States
• 10: Mihai Budiu , Majd Sakr , Kip Walker , Seth Copen Goldstein, BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.969-979, August 29-September 01, 2000
• 11: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 12: Sylvia Dieckmann , Urs Hölzle, A Study of the Allocation Behavior of the SPECjvm98 Java Benchmark, Proceedings of the 13th European Conference on Object-Oriented Programming, p.92-115, June 14-18, 1999
• 13: Nevin Heintze , Olivier Tardieu, Ultra-fast aliasing analysis using CLA: a million lines of C code in a second, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.254-263, June 2001, Snowbird, Utah, United States
• 14: Darko Marinov , Robert O'Callahan, Object equality profiling, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 15: Tamiya Onodera , Kiyokuni Kawachiya, A study of locking objects with bimodal fields, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.223-237, November 01-05, 1999, Denver, Colorado, United States
• 16: Erik Ruf, Effective synchronization removal for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.208-218, June 18-21, 2000, Vancouver, British Columbia, Canada
• 17: Radu Rugina , Martin Rinard, Symbolic bounds analysis of pointers, array indices, and accessed memory regions, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.182-195, June 18-21, 2000, Vancouver, British Columbia, Canada
• 18: Vugranam C. Sreedhar , Michael Burke , Jong-Deok Choi, A framework for interprocedural optimization in the presence of dynamic class loading, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.196-207, June 18-21, 2000, Vancouver, British Columbia, Canada
• 19: Mark Stephenson , Jonathan Babb , Saman Amarasinghe, Bidwidth analysis with application to silicon compilation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.108-120, June 18-21, 2000, Vancouver, British Columbia, Canada
• 20: Alexandru Salcianu , Martin Rinard, Pointer and escape analysis for multithreaded programs, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.12-23, June 2001, Snowbird, Utah, United States
• 21: Peter F. Sweeney , Frank Tip, A study of dead data members in C++ applications, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.324-332, June 17-19, 1998, Montreal, Quebec, Canada
• 22: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
• 23: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States
• 24: Youtao Zhang , Rajiv Gupta, Data Compression Transformations for Dynamically Allocated Data Structures, Proceedings of the 11th International Conference on Compiler Construction, p.14-28, April 08-12, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages
      D.3.4 Processors
          Subjects: Optimization; Compilers

  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Object representation

General Terms:
Algorithms, Experimentation, Languages, Performance

Keywords:
bitwidth analysis, embedded systems, field externalization, field packing, size optimizations, static specialization