Blended analysis for performance understanding of framework-based applications

ABSTRACT

This paper defines a new analysis paradigm, blended program analysis, that enables practical, effective analysis of large framework-based Java applications for performance understanding. Blended analysis combines a dynamic representation of the program calling structure, with a static analysis applied to a region of that calling structure with observed performance problems. A blended escape analysis is presented which enables approximation of object effective lifetimes, to facilitate explanation of the usage of newly created objects in a program region. Performance bottlenecks stemming from overuse of temporary structures are common in framework-based applications. Metrics are introduced to expose how, in aggregate, these applications make use of new objects. Results of empirical experiments with the Trade benchmark are presented. A case study demonstrates how results from a blended escape analysis can help locate, in a region which calls 223 distinct methods, the single call path responsible for a performance problem involving objects created at 9 distinct sites and as far as 6 call levels away.

REFERENCES

• 1: W. P. Alexander , R. F. Berry , F. E. Levine , R. J. Urquhart, A unifying approach to performance analysis in the Java environment, IBM Systems Journal, v.39 n.1, p.118-134, 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: G. Ammons, J. -D. Choi, M. Gupta, and N. Swamy. Finding and removing performance bottlenecks in large systems. In Proc. of the European Conf. on Object-Oriented Prog. (ECOOP), 2004.
• 4: S. Artzi, M. Ernst, D. Glasser, and A. Kiezun. Combined static and dynamic mutability analysis. Technical Report MIT-CSAIL-TR-2006-065, MIT CS and AI Lab., Sep. 2006.
• 5: M. Q. Beers, C. H. Stork, and M. Franz. Efficiently verifiable escape analysis. In Proc. of the European Conf. on Object-Oriented Prog. (ECOOP), pages 96--122. Springer, 2004.
• 6: Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.20-34, November 01-05, 1999, Denver, Colorado, United States
• 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: Jong-Deok Choi , Manish Gupta , Mauricio J. Serrano , Vugranam C. Sreedhar , Samuel P. Midkiff, Stack allocation and synchronization optimizations for Java using escape analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.6, p.876-910, November 2003 [doi>10.1145/945885.945892]
• 9: W. DePauw, E. Jensen, N. Mitchell, G. Sevitsky, J. Vlissides, and J. Yang. Visualizing the execution of java programs. In Software Visualization: State of the Art Survey, LNCS 2269, 2002.
• 10: M. Ernst. Static and dynamic analysis: Synergy and duality. In Proc. of the Wshp on Dynamic Analysis (WODA), 2003.
• 11: David Gay , Bjarne Steensgaard, Fast Escape Analysis and Stack Allocation for Object-Based Programs, Proceedings of the 9th International Conference on Compiler Construction, p.82-93, March 25-April 02, 2000
• 12: A. Groce and R. Joshi. Exploiting traces in program analysis. In Proc. of Int'l Conf. on Tools and Algs for the Construction and Analysis of Systems (TACAS), 2006.
• 13: David Grove , Craig Chambers, A framework for call graph construction algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.6, p.685-746, November 2001 [doi>10.1145/506315.506316]
• 14: Rajiv Gupta , Mary Lou Soffa , John Howard, Hybrid slicing: integrating dynamic information with static analysis, ACM Transactions on Software Engineering and Methodology (TOSEM), v.6 n.4, p.370-397, Oct. 1997 [doi>10.1145/261640.261644]
• 15: Matthew Hertz , Stephen M. Blackburn , J. Eliot B. Moss , Kathryn S. McKinley , Darko Stefanović, Generating object lifetime traces with Merlin, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.3, p.476-516, May 2006 [doi>10.1145/1133651.1133654]
• 16: N. Jones and S. Muchnick. Flow analysis and optimization of lisp-like structures. In Program Flow Analysis: Theory and Applications. Prentice Hall, 1982.
• 17: David Mandelin , Lin Xu , Rastislav Bodík , Doug Kimelman, Jungloid mining: helping to navigate the API jungle, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 18: N. Mitchell. The runtime structure of object ownership. In Proc. of the European Conf. on Object-Oriented Prog. (ECOOP), 2006.
• 19: N. Mitchell and G. Sevitsky. Leakbot: An automated and lightweight tool for diagnosing memory leaks in large Java applications. In Proc. of the European Conf. on Object-Oriented Prog. (ECOOP), 2003.
• 20: N. Mitchell, G. Sevitsky, and H. Srinivasan. Modeling runtime behavior in framework-based applications. In Proc. of the European Conf. on Object-Oriented Prog. (ECOOP), 2006.
• 21: Markus Mock , Darren C. Atkinson , Craig Chambers , Susan J. Eggers, Improving program slicing with dynamic points-to data, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA [doi>10.1145/587051.587062]
• 22: B. G. Ryder. Dimensions of precision in reference analysis of object-oriented programming languages. In Proc. of the 12th Int'l Conf. on Compiler Constr., pages 126--137, April 2003.
• 23: Ran Shaham , Elliot K. Kolodner , Mooly Sagiv, Estimating the impact of heap liveness information on space consumption in Java, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 24: 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
• 25: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States
• 26: 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:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

General Terms:
Experimentation, Languages, Measurement, Performance

Keywords:
dataflow analysis, escape analysis, framework-intensive applications, java, program understandingperfor-mance