Object equality profiling

ABSTRACT

We present Object Equality Profiling (OEP), a new technique for helping programmers discover optimization opportunities in programs. OEP discovers opportunities for replacing a set of equivalent object instances with a single representative object. Such a set represents an opportunity for automatically or manually applying optimizations such as hash consing, heap compression, lazy allocation, object caching, invariant hoisting, and more. To evaluate OEP, we implemented a tool to help programmers reduce the memory usage of Java programs. Our tool performs a dynamic analysis that records all the objects created during a particular program run. The tool partitions the objects into equivalence classes, and uses collected timing information to determine when elements of an equivalence class could have been safely collapsed into a single representative object without affecting the behavior of that program run. We report the results of applying this tool to benchmarks, including two widely used Web application servers. Many benchmarks exhibit significant amounts of object equivalence, and in most benchmarks our profiler identifies optimization opportunities clustered around a small number of allocation sites. We present a case study of using our profiler to find simple manual optimizations that reduce the average space used by live objects in two SpecJVM benchmarks by 47% and 38% respectively.

REFERENCES

• 1: Umut A. A. Acar , Guy E. Blelloch , Robert Harper, Selective memoization, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.14-25, January 15-17, 2003, New Orleans, Louisiana, USA
• 2: 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
• 3: Ole Agesen , David Detlefs , J. Eliot Moss, Garbage collection and local variable type-precision and liveness in Java virtual machines, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.269-279, June 17-19, 1998, Montreal, Quebec, Canada
• 4: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 5: John Allen, Anatomy of LISP, McGraw-Hill, Inc., New York, NY, 1978
• 6: B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
• 7: C. Scott Ananian , Martin Rinard, Data size optimizations for java programs, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 8: A. W. Appel and M. J. R. Goncalves. Hash-consing garbage collection. Technical Report TR-412-93, Princeton University, Computer Science Department, Feb. 1993.
• 9: 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
• 10: 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
• 11: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 12: R. S. Bird, An introduction to the theory of lists, Proceedings of the NATO Advanced Study Institute on Logic of programming and calculi of discrete design, p.5-42, June 1987, Marktoberdorf, Germany
• 13: Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.20-34, November 01-05, 1999, Denver, Colorado, United States
• 14: 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
• 15: A. Cardon and M. Crochemore. Partitioning a graph in O(|A|log2|V|). Theoretical Computer Science, 19(1):85--98, 1982.
• 16: G. Chen , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , B. Mathiske , M. Wolczko, Heap compression for memory-constrained Java environments, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 17: 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
• 18: Sylvia Dieckmann , Urs Hölzle, The allocation behavior of the SPECjvm98 Java benchmarks, Performance evaluation and benchmarking with realistic applications, MIT Press, Cambridge, MA, 2001
• 19: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 20: David Gay , Bjarne Steensgaard, Fast Escape Analysis and Stack Allocation for Object-Based Programs, Proceedings of the 9th International Conference on Compiler Construction, p.82-93, March 25-April 02, 2000
• 21: Ovidiu Gheorghioiu , Alexandru Salcianu , Martin Rinard, Interprocedural compatibility analysis for static object preallocation, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.273-284, January 15-17, 2003, New Orleans, Louisiana, USA
• 22: E. Goto. Monocopy and associative algorithms in an extended Lisp. Technical Report 74-03, Information Science Laboratory, University of Tokyo, Tokyo, Japan, May 1974.
• 23: Matthew Hertz , Stephen M Blackburn , J Eliot B Moss , Kathryn S. McKinley , Darko Stefanović, Error-free garbage collection traces: how to cheat and not get caught, ACM SIGMETRICS Performance Evaluation Review, v.30 n.1, June 2002
• 24: J. E. Hopcroft. An n log n algorithm for minimizing the states in a finite automaton. In The Theory of Machines and Computations, pages 189--196. Academic Press, 1971.
• 25: Barbara H. Liskov , Jeannette M. Wing, A behavioral notion of subtyping, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1811-1841, Nov. 1994 [doi>10.1145/197320.197383]
• 26: D. Michie. "memo" functions and machine learning. Nature, 218, Apr. 1968.
• 27: T. Murphy, B. Harper, and K. Crary. The wizard of tilt: Efficient?, convenient and abstract type representations. Technical Report CMU-CS-02-120, School of Computer Science, Carnegie Mellon University, Mar. 2002. http://www-2.cs.cmu.edu/~tom7/papers/wizard.ps.gz.
• 28: William Pugh, An improved replacement strategy for function caching, Proceedings of the 1988 ACM conference on LISP and functional programming, p.269-276, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62719]
• 29: Niklas Röjemo , Colin Runciman, Lag, drag, void and use—heap profiling and space-efficient compilation revisited, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.34-41, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 30: 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
• 31: Ran Shaham , Elliot K. Kolodner , Mooly Sagiv, On effectiveness of GC in Java, Proceedings of the 2nd international symposium on Memory management, p.12-17, October 15-16, 2000, Minneapolis, Minnesota, United States
• 32: Ran Shaham , Elliot K. Kolodner , Mooly Sagiv, Heap profiling for space-efficient Java, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.104-113, June 2001, Snowbird, Utah, United States
• 33: Yefim Shuf , Manish Gupta , Rajesh Bordawekar , Jaswinder Pal Singh, Exploiting prolific types for memory management and optimizations, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.295-306, January 16-18, 2002, Portland, Oregon
• 34: 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
• 35: Peter F. Sweeney , Frank Tip, A study of dead data members in C++ applications, ACM SIGPLAN Notices, v.33 n.5, p.324-332, May 1998
• 36: The Standard Performance Evaluation Corporation. SPEC JVM98 Benchmarks. http://www.spec.org/osg/jvm98/, 1998.
• 37: Frank Tip , Peter F. Sweeney, Class hierarchy specialization, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.271-285, October 05-09, 1997, Atlanta, Georgia, United States
• 38: Package java.lang.ref. http://java.sun.com/j2se/1.4/docs/api/java/lang/ref/package-summary.html.
• 39: WebSphere application server development best practices for performance and scalability. White paper available from http://www-3.ibm.com/software/webservers/appserv/ws_bestpractices.pdf, Sept. 2000.
• 40: 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
• 41: Byung-Sun Yang , Junpyo Lee , Jinpyo Park , Soo-Mook Moon , Kemal Ebcioğlu , Erik Altman, Lightweight monitor for Java VM, ACM SIGARCH Computer Architecture News, v.27 n.1, p.35-38, March 1999 [doi>10.1145/309758.309773]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection); Optimization

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Measurement, Performance

Keywords:
Java language, object equality, object mergeability, profile-guided optimization, profiling, space savings