Accurate, efficient, and adaptive calling context profiling

ABSTRACT

Calling context profiles are used in many inter-procedural code optimizations and in overall program understanding. Unfortunately, the collection of profile information is highly intrusive due to the high frequency of method calls in most applications. Previously proposed calling-context profiling mechanisms consequently suffer from either low accuracy, high overhead, or both. We have developed a new approach for building the calling context tree at runtime, called adaptive bursting. By selectively inhibiting redundant profiling, this approach dramatically reduces overhead while preserving profile accuracy. We first demonstrate the drawbacks of previously proposed calling context profiling mechanisms. We show that a low-overhead solution using sampled stack-walking alone is less than 50% accurate, based on degree of overlap with a complete calling-context tree. We also show that a static bursting approach collects a highly accurate profile, but causes an unacceptable application slowdown. Our adaptive solution achieves 85% degree of overlap and provides an 88% hot-edge coverage when using a 0.1 hot-edge threshold, while dramatically reducing overhead compared to the static bursting approach.

REFERENCES

• 1: Colorado bench. http://www-plan.cs.colorado.edu/henkel/projects/colorado bench.
• 2: Kawa, the java-based scheme system. http://www.gnu.org/software/kawa.
• 3: 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
• 4: Matthew Arnold , David Grove, Collecting and Exploiting High-Accuracy Call Graph Profiles in Virtual Machines, Proceedings of the international symposium on Code generation and optimization, p.51-62, March 20-23, 2005 [doi>10.1109/CGO.2005.9]
• 5: 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
• 6: M. Arnold and P. F. Sweeney. Approximating the calling context tree via sampling. IBM Research Report, July 2000.
• 7: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1319-1360, July 1994 [doi>10.1145/183432.183527]
• 8: A. R. Bernat and B. P. Miller. Incremental call-path profiling. Technical report, University of Wisconsin, 2004.
• 9: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Wen-mei W. Hwu, Profile-guided automatic inline expansion for C programs, Software—Practice & Experience, v.22 n.5, p.349-369, May 1992 [doi>10.1002/spe.4380220502]
• 10: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 11: Standard Performance Evaluation Corporation. Specjbb2000 java business benchmark. http://www.spec.org/jbb2000.
• 12: Standard Performance Evaluation Corporation. Specjvm98 benchmarks. http://www.spec.org/jvm98.
• 13: Standard Performance Evaluation Corporation. SPECjAppServer2004. http://www.spec.org/jAppServer2004.
• 14: P. T. Feller. Value profiling for instructions and memory locations. Masters Thesis CS98-581, University of California San Diego, April 1998.
• 15: Nathan Froyd , John Mellor-Crummey , Rob Fowler, Low-overhead call path profiling of unmodified, optimized code, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088161]
• 16: David Grove , Greg DeFouw , Jeffrey Dean , Craig Chambers, Call graph construction in object-oriented languages, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.108-124, October 05-09, 1997, Atlanta, Georgia, United States
• 17: N. Grcevski, A. Kielstra, K. Stoodley, M. Stoodley, and V. Sundaresan. Java just-in-time compiler and virtual machine improvements for server and middleware applications. In Usenix 3rd Virtual Machine Research and Technology Symposium (VM'04), 2004.
• 18: Robert J. Hall, Call path profiling, Proceedings of the 14th international conference on Software engineering, p.296-306, May 11-15, 1992, Melbourne, Australia [doi>10.1145/143062.143147]
• 19: Kim Hazelwood , David Grove, Adaptive online context-sensitive inlining, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 20: M. Hirzel and T. Chilimbi. Bursty tracing: A framework for lowoverhead temporal profiling. In In 4th ACM Workshop on Feedback- Directed and Dynamic Optimization (FDDO-4), December 2001.
• 21: Urs Hölzle , David Ungar, Optimizing dynamically-dispatched calls with run-time type feedback, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.326-336, June 20-24, 1994, Orlando, Florida, United States
• 22: P. Kessler S. Graham and M. McKusick. An execution profiler for modular programs. Software-Practice and Experience, 13(8):671--685, 1983.
• 23: 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]
• 24: Toshio Suganuma , Toshiaki Yasue , Toshio Nakatani, An Empirical Study of Method In-lining for a Java Just-in-Time Compiler, Proceedings of the 2nd Java™ Virtual Machine Research and Technology Symposium, p.91-104, August 01-02, 2002
• 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: Toshiaki Yasue , Toshio Suganuma , Hideaki Komatsu , Toshio Nakatani, An Efficient Online Path Profiling Framework for Java Just-In-Time Compilers, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.148, September 27-October 01, 2003

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Measurement, Performance

Keywords:
adaptive, call graph, calling context, calling context tree, java virtual machine, profiling