CCCP: complete calling context profiling in virtual execution environments

ABSTRACT

Calling context profiling is an important technique for locating hotspots in programs. The prevailing data structure is the Calling Context Tree (CCT) that provides dynamic metrics for each calling context. Existing approaches to calling context profiling in Java either limit portability due to the use of native code or of a modified Java Virtual Machine, create incomplete and inaccurate CCTs, or cause excessive overhead. In this paper, we introduce Complete Calling Context Profiling (CCCP), a new approach that reconciles completeness and accuracy of the created CCTs, portability, and moderate overhead. CCCP relies on a generic bytecode instrumentation framework ensuring comprehensive bytecode coverage, including also the standard Java class library. In order to reduce the overhead of accessing the current CCT node, CCCP transforms code such that the caller passes its CCT node to the callee as a special method argument, while ensuring compatibility with native code, reflection, and stack introspection. We use the resulting CCTs for a detailed analysis of the dynamic behavior of Java systems and present a thorough analysis of the origin of runtime overheads.

REFERENCES

• 1: B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 2: Glenn Ammons , Thomas Ball , James R. Larus, Exploiting hardware performance counters with flow and context sensitive profiling, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.85-96, June 16-18, 1997, Las Vegas, Nevada, United States
• 3: Matthew Arnold , Barbara G. Ryder, A framework for reducing the cost of instrumented code, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.168-179, June 2001, Snowbird, Utah, United States
• 4: M. Arnold and P. F. Sweeney. Approximating the calling context tree via sampling. Research report, IBM, July 2000.
• 5: Walter Binder , Jarle Hulaas , Philippe Moret, Advanced Java bytecode instrumentation, Proceedings of the 5th international symposium on Principles and practice of programming in Java, September 05-07, 2007, Lisboa, Portugal [doi>10.1145/1294325.1294344]
• 6: Walter Binder , Jarle Hulaas , Philippe Moret , Alex Villazón, Platform-independent profiling in a virtual execution environment, Software—Practice & Experience, v.39 n.1, p.47-79, January 2009 [doi>10.1002/spe.v39:1]
• 7: Walter Binder , Alex Villazón , Martin Schoeberl , Philippe Moret, Cache-aware cross-profiling for java processors, Proceedings of the 2008 international conference on Compilers, architectures and synthesis for embedded systems, October 19-24, 2008, Atlanta, GA, USA [doi>10.1145/1450095.1450116]
• 8: Stephen M. Blackburn , Robin Garner , Chris Hoffmann , Asjad M. Khang , Kathryn S. McKinley , Rotem Bentzur , Amer Diwan , Daniel Feinberg , Daniel Frampton , Samuel Z. Guyer , Martin Hirzel , Antony Hosking , Maria Jump , Han Lee , J. Eliot B. Moss , B. Moss , Aashish Phansalkar , Darko Stefanović , Thomas VanDrunen , Daniel von Dincklage , Ben Wiedermann, The DaCapo benchmarks: java benchmarking development and analysis, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 9: Michael D. Bond , Kathryn S. McKinley, Probabilistic calling context, Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 10: Shigeru Chiba, Load-Time Structural Reflection in Java, Proceedings of the 14th European Conference on Object-Oriented Programming, p.313-336, June 12-16, 2000
• 11: Geoff A. Cohen , Jeffrey S. Chase , David L. Kaminsky, Automatic program transformation with JOIE, Proceedings of the annual conference on USENIX Annual Technical Conference, p.14-14, June 15-19, 1998, New Orleans, Louisiana
• 12: R. Covington, S. Dwarkadas, J. Jump, J. Sinclair, and S. Madala. The efficient simulation of parallel computer systems. International Journal in Computer Simulation, 1:31--58, 1991.
• 13: M. Dahm. Byte code engineering. In Java-Information-Tage 1999 (JIT'99), Sept. 1999. http://jakarta.apache.org/bcel/
• 14: Bruno Dufour , Karel Driesen , Laurie Hendren , Clark Verbrugge, Dynamic metrics for java, ACM SIGPLAN Notices, v.38 n.11, November 2003
• 15: Jozo Dujmović , Carl Herder, Visualization of Java workloads using ternary diagrams, ACM SIGSOFT Software Engineering Notes, v.29 n.1, January 2004
• 16: Michael Factor , Assaf Schuster , Konstantin Shagin, Instrumentation of standard libraries in object-oriented languages: the twin class hierarchy approach, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 17: David Gregg , James Power , John Waldron, A method-level comparison of the Java Grande and SPEC JVM98 benchmark suites: Research Articles, Concurrency and Computation: Practice & Experience, v.17 n.7-8, p.757-773, June 2005 [doi>10.1002/cpe.v17:7/8]
• 18: ObjectWeb. ASM. Web pages at http://asm.objectweb.org/
• 19: Martin Schoeberl, A Java processor architecture for embedded real-time systems, Journal of Systems Architecture: the EUROMICRO Journal, v.54 n.1-2, p.265-286, January, 2008 [doi>10.1016/j.sysarc.2007.06.001]
• 20: J. M. Spivey, Fast, accurate call graph profiling, Software—Practice & Experience, v.34 n.3, p.249-264, March 2004 [doi>10.1002/spe.562]
• 21: Sun Microsystems, Inc. Java Virtual Machine Profiler Interface (JVMPI). Web pages at http://java.sun.com/j2se/1.4.2/docs/guide/jvmpi/, 2000.
• 22: The Standard Performance Evaluation Corporation. SPEC JVM98 Benchmarks. Web pages at http://www.spec.org/osg/jvm98/, 1998.
• 23: Eli Tilevich , Yannis Smaragdakis, Transparent program transformations in the presence of opaque code, Proceedings of the 5th international conference on Generative programming and component engineering, October 22-26, 2006, Portland, Oregon, USA [doi>10.1145/1173706.1173720]
• 24: Raja Vallée-Rai , Etienne Gagnon , Laurie J. Hendren , Patrick Lam , Patrice Pominville , Vijay Sundaresan, Optimizing Java Bytecode Using the Soot Framework: Is It Feasible?, Proceedings of the 9th International Conference on Compiler Construction, p.18-34, March 25-April 02, 2000
• 25: John Whaley, A portable sampling-based profiler for Java virtual machines, Proceedings of the ACM 2000 conference on Java Grande, p.78-87, June 03-04, 2000, San Francisco, California, United States [doi>10.1145/337449.337483]
• 26: T. Wilkinson. Kaffe -- a Java virtual machine. Web pages at http://www.kaffe.org/
• 27: Xiaotong Zhuang , Mauricio J. Serrano , Harold W. Cain , Jong-Deok Choi, Accurate, efficient, and adaptive calling context profiling, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Algorithms, Languages, Measurement, Performance

Keywords:
bytecode instrumentation, calling context profiling, java virtual machine, native code