Dynamic metrics for java

ABSTRACT

In order to perform meaningful experiments in optimizing compilation and run-time system design, researchers usually rely on a suite of benchmark programs of interest to the optimization technique under consideration. Programs are described as numeric, memory-intensive, concurrent, or object-oriented, based on a qualitative appraisal, in some cases with little justification. We believe it is beneficial to quantify the behaviour of programs with a concise and precisely defined set of metrics, in order to make these intuitive notions of program behaviour more concrete and subject to experimental validation. We therefore define and measure a set of unambiguous, dynamic, robust and architecture-independent metrics that can be used to categorize programs according to their dynamic behaviour in five areas: size, data structure, memory use, concurrency, and polymorphism. A framework computing some of these metrics for Java programs is presented along with specific results demonstrating how to use metric data to understand a program's behaviour, and both guide and evaluate compiler optimizations.

REFERENCES

• 1: Ole Agesen , David Detlefs , Alex Garthwaite , Ross Knippel , Y.S. Ramakrishna , Derek White, An Efficient Meta-lock for Implementing Ubiquitous Synchronization, Sun Microsystems, Inc., Mountain View, CA, 1999
• 2: K. K. Aggarwal , Yogesh Singh , Jitender Kumar Chhabra, A dynamic software metric and debugging tool, ACM SIGSOFT Software Engineering Notes, v.28 n.2, March 2003 [doi>10.1145/638750.638773]
• 3: Gerald Aigner , Urs Hölzle, Eliminating Virtual Function Calls in C++ Programs, Proceedings of the 10th European Conference on Object-Oriented Programming, p.142-166, July 08-12, 1996
• 4: A. N. Eden , T. Mudge, The YAGS branch prediction scheme, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.69-77, November 1998, Dallas, Texas, United States
• 5: David F. Bacon , Clement R. Attanasio , Han B. Lee , V. T. Rajan , Stephen Smith, Java without the coffee breaks: a nonintrusive multiprocessor garbage collector, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.92-103, June 2001, Snowbird, Utah, United States
• 6: 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
• 7: 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
• 8: Brendon Cahoon , Kathryn S. McKinley, Data Flow Analysis for Software Prefetching Linked Data Structures in Java, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.280-291, September 08-12, 2001
• 9: Po-Yung Chang , Eric Hao , Yale N. Patt, Target prediction for indirect jumps, Proceedings of the 24th annual international symposium on Computer architecture, p.274-283, June 01-04, 1997, Denver, Colorado, United States
• 10: Ben-Chung Cheng , Wen-Mei W. Hwu, Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.57-69, June 18-21, 2000, Vancouver, British Columbia, Canada
• 11: Trishul M. Chilimbi, Efficient representations and abstractions for quantifying and exploiting data reference locality, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.191-202, June 2001, Snowbird, Utah, United States
• 12: Charles Daly , Jane Horgan , James Power , John Waldron, Platform independent dynamic Java virtual machine analysis: the Java Grande Forum Benchmark suite, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.106-115, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376826]
• 13: Manuvir Das, Unification-based pointer analysis with directional assignments, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.35-46, June 18-21, 2000, Vancouver, British Columbia, Canada
• 14: Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
• 15: L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
• 16: 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
• 17: Karel Driesen , Urs Hölzle, Multi-stage Cascaded Prediction, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.1312-1321, August 31-September 03, 1999
• 18: Karl Driesen , Karel Driesen, Efficient Polymorphic Calls, Kluwer Academic Publishers, Norwell, MA, 2001
• 19: Norman Fenton , Shari Lawrence Pfleeger, Software metrics (2nd ed.): a rigorous and practical approach, PWS Publishing Co., Boston, MA, 1997
• 20: Sanjay Ghemawat , Keith H. Randall , Daniel J. Scales, Field analysis: getting useful and low-cost interprocedural information, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.334-344, June 18-21, 2000, Vancouver, British Columbia, Canada
• 21: Rakesh Ghiya , Daniel Lavery , David Sehr, On the importance of points-to analysis and other memory disambiguation methods for C programs, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.47-58, June 2001, Snowbird, Utah, United States
• 22: John L. Hennessy , David A. Patterson, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 02
• 23: Kiyokuni Kawachiya , Akira Koseki , Tamiya Onodera, Lock reservation: Java locks can mostly do without atomic operations, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 24: Chandra Krintz , Brad Calder, Using annotations to reduce dynamic optimization time, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.156-167, June 2001, Snowbird, Utah, United States
• 25: Tao Li , Lizy Kurian John , Vijaykrishnan Narayanan , Anand Sivasubramaniam , Jyotsna Sabarinathan , Anupama Murthy, Using complete system simulation to characterize SPECjvm98 benchmarks, Proceedings of the 14th international conference on Supercomputing, p.22-33, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335234]
• 26: Feng Qian , Laurie J. Hendren , Clark Verbrugge, A Comprehensive Approach to Array Bounds Check Elimination for Java, Proceedings of the 11th International Conference on Compiler Construction, p.325-342, April 08-12, 2002
• 27: 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
• 28: Yefim Shuf , Mauricio J. Serrano , Manish Gupta , Jaswinder Pal Singh, Characterizing the memory behavior of Java workloads: a structured view and opportunities for optimizations, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.194-205, June 2001, Cambridge, Massachusetts, United States
• 29: Vijay Sundaresan , Laurie Hendren , Chrislain Razafimahefa , Raja Vallée-Rai , Patrick Lam , Etienne Gagnon , Charles Godin, Practical virtual method call resolution for Java, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.264-280, October 2000, Minneapolis, Minnesota, United States
• 30: David Michael Ungar, The design and evaluation of a high performance Smalltalk system, MIT Press, Cambridge, MA, 1987
• 31: N. Vijaykrishnan and N.Ranganathan. Tuning branch predictors to support virtual method invocation in Java. In Proceedings of the 5th USENIX Conference on Object-Oriented Technologies ans Systems, May 1999.
• 32: Tse-Yu Yeh , Yale N. Patt, Alternative implementations of two-level adaptive branch prediction, Proceedings of the 19th annual international symposium on Computer architecture, p.124-134, May 19-21, 1992, Queensland, Australia
• 33: Javier Zalamea , Josep Llosa , Eduard Ayguadé , Mateo Valero, Improved spill code generation for software pipelined loops, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.134-144, June 18-21, 2000, Vancouver, British Columbia, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Experimentation, Languages, Measurement, Performance, Standardization

Keywords:
Java, dynamic metrics, execution traces, optimization, profiling, program analysis, software metrics