Go with the flow: profiling copies to find runtime bloat

ABSTRACT

Many large-scale Java applications suffer from runtime bloat. They execute large volumes of methods, and create many temporary objects, all to execute relatively simple operations. There are large opportunities for performance optimizations in these applications, but most are being missed by existing optimization and tooling technology. While JIT optimizations struggle for a few percent, performance experts analyze deployed applications and regularly find gains of 2x or more.

Finding such big gains is difficult, for both humans and compilers, because of the diffuse nature of runtime bloat. Time is spread thinly across calling contexts, making it difficult to judge how to improve performance. Bloat results from a pile-up of seemingly harmless decisions. Each adds temporary objects and method calls, and often copies values between those temporary objects. While data copies are not the entirety of bloat, we have observed that they are excellent indicators of regions of excessive activity. By optimizing copies, one is likely to remove the objects that carry copied values, and the method calls that allocate and populate them.

We introduce copy profiling, a technique that summarizes runtime activity in terms of chains of data copies. A flat copy profile counts copies by method. We show how flat profiles alone can be helpful. In many cases, diagnosing a problem requires data flow context. Tracking and making sense of raw copy chains does not scale, so we introduce a summarizing abstraction called the copy graph. We implement three clients analyses that, using the copy graph, expose common patterns of bloat, such as finding hot copy chains and discovering temporary data structures. We demonstrate, with examples from a large-scale commercial application and several benchmarks, that copy profiling can be used by a programmer to quickly find opportunities for large performance gains.

REFERENCES

• 1: G. Ammons, J.-D. Choi, M. Gupta, and N. Swamy. Finding and removing performance bottlenecks in large systems. In ECOOP, pages 172--196, 2004.
• 2: M. Arnold, S. Fink, D. Grove, M. Hind, and P. F. Sweeney. A survey of adaptive optimization in virtual machines. Proc. IEEE, 92(2):449--466, 2005.
• 3: Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
• 4: 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
• 5: Michael D. Bond , Kathryn S. McKinley, Continuous Path and Edge Profiling, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.130-140, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.16]
• 6: Michael D. Bond , Nicholas Nethercote , Stephen W. Kent , Samuel Z. Guyer , Kathryn S. McKinley, Tracking bad apples: reporting the origin of null and undefined value errors, Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 7: James Clause , Wanchun Li , Alessandro Orso, Dytan: a generic dynamic taint analysis framework, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273490]
• 8: Bruno Dufour , Karel Driesen , Laurie Hendren , Clark Verbrugge, Dynamic metrics for java, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 9: Bruno Dufour , Barbara G. Ryder , Gary Sevitsky, Blended analysis for performance understanding of framework-based applications, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273480]
• 10: Bruno Dufour , Barbara G. Ryder , Gary Sevitsky, A scalable technique for characterizing the usage of temporaries in framework-intensive Java applications, Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering, November 09-14, 2008, Atlanta, Georgia [doi>10.1145/1453101.1453111]
• 11: ej-technologies. JProfiler. www.ej-technologies.com.
• 12: Java Development Blog. dld.blog-city.com.
• 13: Java Heap Analyzer Tool (HAT). hat.dev.java.net.
• 14: James R. Larus, Whole program paths, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.259-269, May 01-04, 1999, Atlanta, Georgia, United States
• 15: Wes Masri , Andy Podgurski, An empirical study of the strength of information flows in programs, Proceedings of the 2006 international workshop on Dynamic systems analysis, May 23-23, 2006, Shanghai, China [doi>10.1145/1138912.1138927]
• 16: Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to analysis for Java, ACM Transactions on Software Engineering and Methodology (TOSEM), v.14 n.1, p.1-41, January 2005 [doi>10.1145/1044834.1044835]
• 17: Nick Mitchell , Gary Sevitsky, The causes of bloat, the limits of health, Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 18: N. Mitchell, G. Sevitsky, and H. Srinivasan. Modeling runtime behavior in framework-based applications. In ECOOP, pages 429--451, 2006.
• 19: Nicholas Nethercote , Julian Seward, How to shadow every byte of memory used by a program, Proceedings of the 3rd international conference on Virtual execution environments, June 13-15, 2007, San Diego, California, USA [doi>10.1145/1254810.1254820]
• 20: J. Newsome and D. Song. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. In NDSS, 2005.
• 21: Feng Qin , Cheng Wang , Zhenmin Li , Ho-seop Kim , Yuanyuan Zhou , Youfeng Wu, LIFT: A Low-Overhead Practical Information Flow Tracking System for Detecting Security Attacks, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.135-148, December 09-13, 2006 [doi>10.1109/MICRO.2006.29]
• 22: Quest Software. JProbe memory debugging. www.quest.com/jprobe.
• 23: Derek Rayside , Lucy Mendel, Object ownership profiling: a technique for finding and fixing memory leaks, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA [doi>10.1145/1321631.1321661]
• 24: Ajeet Shankar , Matthew Arnold , Rastislav Bodik, Jolt: lightweight dynamic analysis and removal of object churn, Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA
• 25: O. Shivers, Control flow analysis in scheme, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.164-174, June 20-24, 1988, Atlanta, Georgia, United States
• 26: Kavitha Srinivas , Harini Srinivasan, Summarizing application performance from a components perspective, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 27: Sun Java Forum. forums.java.net/jive/thread.jspa?messageID=180784.
• 28: Kapil Vaswani , Aditya V. Nori , Trishul M. Chilimbi, Preferential path profiling: compactly numbering interesting paths, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
• 29: Guoqing Xu , Atanas Rountev, Precise memory leak detection for java software using container profiling, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368110]
• 30: Wei Xu , Sandeep Bhatkar , R. Sekar, Taint-enhanced policy enforcement: a practical approach to defeat a wide range of attacks, Proceedings of the 15th conference on USENIX Security Symposium, July 31-August 04, 2006, Vancouver, B.C., Canada
• 31: Xiangyu Zhang , Neelam Gupta , Rajiv Gupta, Pruning dynamic slices with confidence, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 32: Xiangyu Zhang , Rajiv Gupta, Cost effective dynamic program slicing, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 33: Xiangyu Zhang , Rajiv Gupta, Whole Execution Traces, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.105-116, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.37]
• 34: Xiangyu Zhang , Rajiv Gupta , Youtao Zhang, Precise dynamic slicing algorithms, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Memory management (garbage collection); Run-time environments

General Terms:
Languages, Measurement, Performance

Keywords:
copy graph, heap analysis, memory bloat, profiling