Inferred call path profiling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Inferred call path profiling

Full text

Pdf (510 KB)

Source

Conference on Object Oriented Programming Systems Languages and Applications archive
Proceeding of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications table of contents

Orlando, Florida, USA

SESSION: Reliability and monitoring table of contents

Pages 175-190

Year of Publication: 2009

ISBN:978-1-60558-766-0

Also published in ...

Authors

Todd Mytkowicz	University of Colorado, Boulder, CO, USA
Devin Coughlin	University of Colorado, Boulder, CO, USA
Amer Diwan	University of Colorado, Boulder, CO, USA

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 45, Downloads (12 Months): 45, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1640089.1640102 What is a DOI?

ABSTRACT

Prior work has found call path profiles to be useful for optimizers and programmer-productivity tools. Unfortunately, previous approaches for collecting path profiles are expensive: they need to either execute additional instructions (to track calls and returns) or they need to walk the stack. The state-of-the-art techniques for call path profiling slow down the program by 7% (for C programs) and 20% (for Java programs). This paper describes an innovative technique that collects minimal information from the running program and later (offline) infers the full call paths from this information.

The key insight behind our approach is that readily available information during program execution - the height of the call stack and the identity of the current executing function - are good indicators of calling context. We call this pair a context identifier. Because more than one call path may have the same context identifier, we show how to disambiguate context identifiers by changing the sizes of function activation records. This disambiguation has no overhead in terms of executed instructions.

We evaluate our approach on the SPEC CPU 2006 C++ and C benchmarks. We show that collecting context identifiers slows down programs by 0.17% (geometric mean). We can map these context identifiers to the correct unique call path 80% of the time for C++ programs and 95% of the time for C programs.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Gerald Aigner and Urs H¨olzle. Eliminating virtual function calls in C++ programs. In ECOOP '96: Proceedings of the 10th European Conference on Object-Oriented Programming, pages 142--166, London, UK, 1996. Springer-Verlag.
	2	Glenn Ammons, Thomas Ball, and James R. Larus. Exploiting hardware performance counters with flow and context sensitive profiling. SIGPLAN Not., 32(5):85--96, 1997.
	3	M. Arnold and D. Grove. Collecting and exploiting highaccuracy call graph profiles in virtual machines. In Code Generation and Optimization, 2005. CGO 2005. International Symposium on, pages 51--62, March 2005.
	4	Matthew Arnold and David Grove. Collecting and exploiting high-accuracy call graph profiles in virtual machines. In CGO '05: Proceedings of the international symposium on Code generation and optimization, pages 51--62, Washington, DC, USA, 2005. IEEE Computer Society.
	5	Thomas Ball and James R. Larus. Optimally profiling and tracing programs. ACM Trans. Program. Lang. Syst., 16(4):1319--1360, 1994.
	6	Andrew R. Bernat and Barton P. Miller. Incremental call-path profiling: Research articles. Concurr. Comput. : Pract. Exper., 19(11):1533--1547, 2007.
	7	Michael D. Bond and Kathryn S. McKinley. Probabilistic Calling Context. SIGPLAN Not., 42(10):97--112, 2007.
	8	Apple Computer. Shark. http://developer.apple.com/performance.
	9	Jeffrey Dean, David Grove, and Craig Chambers. Optimization of object-oriented programs using static class hierarchy analysis. In ECOOP '95: Proceedings of the 9th European Conference on Object-Oriented Programming, pages 77--101, London, UK, 1995. Springer-Verlag.
	10	Saumya Debray and Robert Muth. Alias analysis of executable code. In In POPL, pages 12--24, 1998.
	11	Henry Hanping Feng, Oleg M. Kolesnikov, Prahlad Fogla, Wenke Lee, and Weibo Gong. Anomaly detection using call stack information. In SP'03: Proceedings of the 2003 IEEE Symposium on Security and Privacy, page 62, Washington, DC, USA, 2003. IEEE Computer Society.
	12	Nathan Froyd, John Mellor-Crummey, and Rob Fowler. Lowoverhead call path profiling of unmodified, optimized code. In Proceedings of the 19th annual international conference on Supercomputing, pages 81--90, Cambridge,Massachusetts, 2005. ACM.
	13	Susan L. Graham, Peter B. Kessler, and Marshall K. Mckusick. gprof: A call graph execution profiler. In Proceedings of the 1982 SIGPLAN symposium on Compiler construction, pages 120--126, Boston, Massachusetts, United States, 1982. ACM.
	14	Kim Hazelwood and David Grove. Adaptive online contextsensitive inlining. In Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, pages 253--264, San Francisco, California, 2003. IEEE Computer Society.
	15	Allen D. Malony, Sameer Shende, Robert Bell, Kai Li, Li Li, and Nick Trebon. Advances in the TAU performance system. Performance analysis and grid computing, pages 129--144, 2004.
	16	Todd Mytkowicz, Amer Diwan, Matthias Hauswirth, and Peter F. Sweeney. Producing wrong data without doing anything obviously wrong! In ASPLOS '09: Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, pages 265--276, New York, NY, USA, 2009. ACM.
	17	George C. Necula, Scott McPeak, Shree Prakash Rahul, and Westley Weimer. CIL: Intermediate language and tools for analysis and transformation of C programs. In CC '02: Proceedings of the 11th International Conference on Compiler Construction, pages 213--228, London, UK, 2002. Springer-Verlag.
	18	Karl Pettis and Robert C. Hansen. Profile guided code positioning. SIGPLAN Not., 25(6):16--27, 1990.
	19	J. M. Spivey. Fast, accurate call graph profiling. Softw. Pract. Exper., 34(3):249--264, 2004.
	20	B. Sprunt. Pentium 4 performance-monitoring features. Micro, IEEE, 22(4):72--82, Jul/Aug 2002.
	21	Standard Performance Evaluation Corporation. SPEC CPU2006 Benchmarks. http://www.spec.org/cpu2006/.
	22	Toshio Suganuma, Toshiaki Yasue, Motohiro Kawahito, Hideaki Komatsu, and Toshio Nakatani. A dynamic optimization framework for a Java just-in-time compiler. SIGPLAN Not., 36(11):180--195, 2001.
	23	Kapil Vaswani, Aditya V. Nori, and Trishul M. Chilimbi. Preferential path profiling: compactly numbering interesting paths. In Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 351--362, Nice, France, 2007. ACM.
	24	Mark Weiser. Program slicing. In ICSE '81: Proceedings of the 5th international conference on Software engineering, pages 439--449, Piscataway, NJ, USA, 1981. IEEE Press.
	25	Xiaotong Zhuang, Mauricio J. Serrano, Harold W. Cain, and Jong-Deok Choi. Accurate, efficient, and adaptive calling context profiling. SIGPLAN Not., 41(6):263--271, 2006.