research-article

Efficient flow profiling for detecting performance bugs

Authors:

Rashmi Mudduluru,

Murali Krishna RamanathanAuthors Info & Claims

ISSTA 2016: Proceedings of the 25th International Symposium on Software Testing and Analysis

Pages 413 - 424

https://doi.org/10.1145/2931037.2931066

Published: 18 July 2016 Publication History

Abstract

Performance issues in large applications arise only in particular scenarios under heavy load conditions. It is therefore difficult to catch them during testing and they easily escape into production. This necessitates the design of a common and efficient instrumentation strategy that profiles the flow of objects during an execution. Designing such a strategy which enables profile generation precisely with low overhead is non-trivial due to the number of objects created, accessed and paths traversed by them in an execution. In this paper, we design and implement an efficient instrumentation technique that efficiently generates object flow profiles for Java programs, without requiring any modifications to the underlying virtual machine. We achieve this by applying Ball-Larus numbering on a specialized hybrid flow graph (hfg). The hfg path profiles that are collected during runtime are post-processed offline to derive the object flow profiles. We implemented the profiler and validated its efficacy by applying it on Java programs. The results demonstrate the scalability of our approach, which handles 0.2M to 0.55B object accesses with an average runtime overhead of 8x. We also demonstrate the effectiveness of the generated profiles by implementing a client analysis that consumes the profiles to detect performance bugs. The analysis detects 38 performance bugs which when refactored result in significant performance gains (up to 30%) in running times.

References

[1]

O. Agesen and A. Garthwaite. Efficient object sampling via weak references. In Proceedings of the 2Nd International Symposium on Memory Management, ISMM ’00, pages 121–126, New York, NY, USA, 2000.

Digital Library

[2]

T. Ball and J. R. Larus. Efficient path profiling. In Proceedings of the 29th Annual ACM/IEEE International Symposium on Microarchitecture, MICRO 29, pages 46–57, Washington, DC, USA, 1996.

Digital Library

[3]

T. Bao, Y. Zheng, Z. Lin, X. Zhang, and D. Xu. Strict control dependence and its effect on dynamic information flow analyses. In Proceedings of the 19th International Symposium on Software Testing and Analysis, ISSTA ’10, pages 13–24, New York, NY, USA, 2010.

Digital Library

[4]

S. Bhattacharya, K. Gopinath, and M. G. Nanda. Combining concern input with program analysis for bloat detection. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA ’13, pages 745–764, New York, NY, USA, 2013.

Digital Library

[5]

S. Bhattacharya, M. G. Nanda, K. Gopinath, and M. Gupta. Reuse, recycle to de-bloat software. In Proceedings of the 25th European Conference on Object-oriented Programming, ECOOP’11, pages 408–432, Berlin, Heidelberg, 2011.

Digital Library

[6]

S. M. Blackburn, S. Singhai, M. Hertz, K. S. McKinely, and J. E. B. Moss. Pretenuring for java. In Proceedings of the 16th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA ’01, pages 342–352, New York, NY, USA, 2001.

Digital Library

[7]

D. C. D’Elia and C. Demetrescu. Ball-larus path profiling across multiple loop iterations. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA ’13, pages 373–390, New York, NY, USA, 2013.

Digital Library

[8]

L. Della Toffola, M. Pradel, and T. R. Gross. Performance problems you can fix: A dynamic analysis of memoization opportunities. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2015, pages 607–622, New York, NY, USA, 2015.

Digital Library

[9]

J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. ACM Trans. Program. Lang. Syst., 9(3):319–349, July 1987.

Digital Library

[10]

L. Gong, M. Pradel, and K. Sen. Jitprof: Pinpointing jit-unfriendly javascript code. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2015, pages 357–368, New York, NY, USA, 2015.

Digital Library

[11]

L. Gong, M. Pradel, M. Sridharan, and K. Sen. DLint: Dynamically checking bad coding practices in javascript. In Proceedings of the 2015 International Symposium on Software Testing and Analysis, ISSTA 2015, pages 94–105, New York, NY, USA, 2015.

Digital Library

[12]

S. Z. Guyer, K. S. McKinley, and D. Frampton. Free-me: A static analysis for automatic individual object reclamation. In Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’06, pages 364–375, New York, NY, USA, 2006.

Digital Library

[13]

S. Han, Y. Dang, S. Ge, D. Zhang, and T. Xie. Performance debugging in the large via mining millions of stack traces. In Proceedings of the 34th International Conference on Software Engineering, ICSE ’12, pages 145–155, Piscataway, NJ, USA, 2012.

Digital Library

[14]

M. Hertz, S. M. Blackburn, J. E. B. Moss, K. S. McKinley, and D. Stefanovi´c. Generating object lifetime traces with merlin. ACM Trans. Program. Lang. Syst., 28(3):476–516, May 2006.

Digital Library

[15]

W. huang, W. Srisa-an, and J. M. Chang. Dynamic pretenuring schemes for generational garbage collection. In Proceedings of the 2004 IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS ’04, pages 133–140, Washington, DC, USA, 2004.

Digital Library

[16]

S. H. Jensen, M. Sridharan, K. Sen, and S. Chandra. Meminsight: Platform-independent memory debugging for javascript. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2015, pages 345–356, New York, NY, USA, 2015.

Digital Library

[17]

M. Jovic, A. Adamoli, and M. Hauswirth. Catch me if you can: Performance bug detection in the wild. In Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA ’11, pages 155–170, New York, NY, USA, 2011.

Digital Library

[18]

M. Jump, S. M. Blackburn, and K. S. McKinley. Dynamic object sampling for pretenuring. In Proceedings of the 4th International Symposium on Memory Management, ISMM ’04, pages 152–162, New York, NY, USA, 2004.

Digital Library

[19]

M. Jump and K. S. McKinley. Detecting memory leaks in managed languages with cork. Softw. Pract. Exper., 40(1):1–22, Jan. 2010.

Digital Library

[20]

J. R. Larus. Whole program paths. In Proceedings of the ACM SIGPLAN 1999 Conference on Programming Language Design and Implementation, PLDI ’99, pages 259–269, New York, NY, USA.

Digital Library

[21]

H. Lieberman and C. Hewitt. A real-time garbage collector based on the lifetimes of objects. Commun. ACM, 26(6):419–429, June 1983.

Digital Library

[22]

A. Nistor, L. Song, D. Marinov, and S. Lu. Toddler: Detecting performance problems via similar memory-access patterns. In Proceedings of the 2013 International Conference on Software Engineering, ICSE ’13, pages 562–571, Piscataway, NJ, USA, 2013.

Digital Library

[23]

R. Odaira and T. Nakatani. Continuous object access profiling and optimizations to overcome the memory wall and bloat. In Proceedings of the Seventeenth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XVII, pages 147–158, New York, NY, USA, 2012.

Digital Library

[24]

O. Olivo, I. Dillig, and C. Lin. Static detection of asymptotic performance bugs in collection traversals. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2015, pages 369–378, New York, NY, USA, 2015.

Digital Library

[25]

M. Pradel and T. R. Gross. Automatic generation of object usage specifications from large method traces. In Proceedings of the 2009 IEEE/ACM International Conference on Automated Software Engineering, ASE ’09, pages 371–382, Washington, DC, USA, 2009.

Digital Library

[26]

M. Pradel, M. Huggler, and T. R. Gross. Performance regression testing of concurrent classes. In Proceedings of the 2014 International Symposium on Software Testing and Analysis, ISSTA 2014, pages 13–25, New York, NY, USA, 2014.

Digital Library

[27]

M. Selakovic and M. Pradel. Automatically fixing real-world javascript performance bugs. In Proceedings of the 37th International Conference on Software Engineering - Volume 2, ICSE ’15, pages 811–812, Piscataway, NJ, USA, 2015.

Digital Library

[28]

R. Shaham, E. K. Kolodner, and M. Sagiv. Heap profiling for space-efficient java. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, PLDI ’01, pages 104–113, New York, NY, USA, 2001.

Digital Library

[29]

A. Shankar, M. Arnold, and R. Bodik. Jolt: Lightweight dynamic analysis and removal of object churn. In Proceedings of the 23rd ACM SIGPLAN Conference on Object-oriented Programming Systems Languages and Applications, OOPSLA ’08, pages 127–142, New York, NY, USA, 2008.

Digital Library

[30]

W. N. Sumner and X. Zhang. Memory indexing: Canonicalizing addresses across executions. In Proceedings of the Eighteenth ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE ’10, pages 217–226, New York, NY, USA, 2010.

Digital Library

[31]

W. N. Sumner, Y. Zheng, D. Weeratunge, and X. Zhang. Precise calling context encoding. In Proceedings of the 32Nd ACM/IEEE International Conference on Software Engineering - Volume 1, ICSE ’10, pages 525–534, New York, NY, USA, 2010.

Digital Library

[32]

S. Tallam, X. Zhang, and R. Gupta. Extending path profiling across loop backedges and procedure boundaries. In Code Generation and Optimization, 2004. CGO 2004. International Symposium on, pages 251–262, March 2004.

Digital Library

[33]

R. Vallée-Rai, P. Co, E. Gagnon, L. Hendren, P. Lam, and V. Sundaresan. Soot - a java bytecode optimization framework. In Proceedings of the 1999 Conference of the Centre for Advanced Studies on Collaborative Research, CASCON ’99, pages 13–, 1999.

Digital Library

[34]

M. Weiser. Program slicing. In Proceedings of the 5th International Conference on Software Engineering, ICSE ’81, pages 439–449, Piscataway, NJ, USA, 1981.

Digital Library

[35]

R. Wu, X. Xiao, S.-C. Cheung, H. Zhang, and C. Zhang. Casper: An efficient approach to call trace collection. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2016, pages 678–690, New York, NY, USA, 2016.

Digital Library

[36]

B. Xin and X. Zhang. Efficient online detection of dynamic control dependence. In Proceedings of the 2007 International Symposium on Software Testing and Analysis, ISSTA ’07, pages 185–195, New York, NY, USA, 2007.

Digital Library

[37]

G. Xu. Resurrector: A tunable object lifetime profiling technique for optimizing real-world programs. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA ’13, pages 111–130, New York, NY, USA, 2013.

Digital Library

[38]

G. Xu, M. Arnold, N. Mitchell, A. Rountev, and G. Sevitsky. Go with the flow: Profiling copies to find runtime bloat. In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’09, pages 419–430, New York, NY, USA, 2009.

Digital Library

[39]

G. Xu, M. D. Bond, F. Qin, and A. Rountev. Leakchaser: Helping programmers narrow down causes of memory leaks. In Proceedings of the 32Nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’11, pages 270–282, New York, NY, USA, 2011.

Digital Library

[40]

D. Yan, G. Xu, and A. Rountev. Uncovering performance problems in java applications with reference propagation profiling. In Proceedings of the 34th International Conference on Software Engineering, ICSE ’12, pages 134–144, Piscataway, NJ, USA, 2012.

Digital Library

[41]

X. Zhang and R. Gupta. Whole execution traces. In Microarchitecture, 2004. MICRO-37 2004. 37th International Symposium on, pages 105–116, 2004.

Digital Library

[42]

X. Zhang, A. Navabi, and S. Jagannathan. Alchemist: A transparent dependence distance profiling infrastructure. In Proceedings of the 7th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO ’09, pages 47–58, Washington, DC, USA, 2009.

Digital Library

Cited By

Liu XYang CLi DZhou YLi SChen JChen Z(2023)Adonis: Practical and Efficient Control Flow Recovery through OS-level TracesACM Transactions on Software Engineering and Methodology10.1145/360718733:1(1-27)Online publication date: 4-Jul-2023
https://dl.acm.org/doi/10.1145/3607187
Wang CYao PTang WShi QZhang C(2022)Complexity-guided container replacement synthesisProceedings of the ACM on Programming Languages10.1145/35273126:OOPSLA1(1-31)Online publication date: 29-Apr-2022
https://dl.acm.org/doi/10.1145/3527312
Lei ZZhao WDing ZXia MQi Z(2022)AppSPIN: reconfiguration-based responsiveness testing and diagnosing for Android AppsAutomated Software Engineering10.1007/s10515-022-00347-929:2Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10515-022-00347-9
Show More Cited By

Index Terms

Efficient flow profiling for detecting performance bugs
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Object oriented languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection
    2. Extra-functional properties
      1. Software performance

Recommendations

Low overhead program monitoring and profiling

Program instrumentation, inserted either before or during execution, is rapidly becoming a necessary component of many systems. Instrumentation is commonly used to collect information for many diverse analysis applications, such as detecting program ...
Incremental call-path profiling: Research Articles
European–American Working Group on Automatic Performance Analysis (APART)

Profiling is a key technique for achieving high performance. Call-path profiling is a refinement of this technique that classifies a function's behavior based on the path taken to reach the function. This information is particularly useful when ...
Continuous object access profiling and optimizations to overcome the memory wall and bloat
ASPLOS '12

Future microprocessors will have more serious memory wall problems since they will include more cores and threads in each chip. Similarly, future applications will have more serious memory bloat problems since they are more often written using object-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA 2016: Proceedings of the 25th International Symposium on Software Testing and Analysis

July 2016

452 pages

ISBN:9781450343909

DOI:10.1145/2931037

General Chair:
Andreas Zeller
Saarland University, Germany
,
Program Chair:
Abhik Roychoudhury
National University of Singapore, Singapore

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

In-Cooperation

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Distinguished Paper

Author Tags

Qualifiers

Research-article

Conference

ISSTA '16

Sponsor:

SIGSOFT

ISSTA '16: International Symposium on Software Testing and Analysis

July 18 - 20, 2016

Saarbrücken, Germany

Acceptance Rates

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
424
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu XYang CLi DZhou YLi SChen JChen Z(2023)Adonis: Practical and Efficient Control Flow Recovery through OS-level TracesACM Transactions on Software Engineering and Methodology10.1145/360718733:1(1-27)Online publication date: 4-Jul-2023
https://dl.acm.org/doi/10.1145/3607187
Wang CYao PTang WShi QZhang C(2022)Complexity-guided container replacement synthesisProceedings of the ACM on Programming Languages10.1145/35273126:OOPSLA1(1-31)Online publication date: 29-Apr-2022
https://dl.acm.org/doi/10.1145/3527312
Lei ZZhao WDing ZXia MQi Z(2022)AppSPIN: reconfiguration-based responsiveness testing and diagnosing for Android AppsAutomated Software Engineering10.1007/s10515-022-00347-929:2Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10515-022-00347-9
Huang LZhu T(2021)tprofProceedings of the ACM Symposium on Cloud Computing10.1145/3472883.3486994(76-91)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1145/3472883.3486994
Zhao YXiao LWang XChen ZChen BLiu Y(2020)Butterfly Space: An Architectural Approach for Investigating Performance Issues2020 IEEE International Conference on Software Architecture (ICSA)10.1109/ICSA47634.2020.00027(202-213)Online publication date: Mar-2020
https://doi.org/10.1109/ICSA47634.2020.00027
Sanchez ADelgado-Perez PMedina-Bulo ISegura S(2020)TANDEM: A Taxonomy and a Dataset of Real-World Performance BugsIEEE Access10.1109/ACCESS.2020.30009288(107214-107228)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3000928
Rodrigues MGuimarães BPereira FKandemir MJimborean AMoseley T(2019)Generation of in-bounds inputs for arrays in memory-unsafe languagesProceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization10.5555/3314872.3314890(136-148)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.5555/3314872.3314890
Zhao WDing ZXia MQi Z(2019)Systematically Testing and Diagnosing Responsiveness for Android Apps2019 IEEE International Conference on Software Maintenance and Evolution (ICSME)10.1109/ICSME.2019.00077(449-453)Online publication date: Sep-2019
https://doi.org/10.1109/ICSME.2019.00077
Zhao YXiao LWang XChen BLiu YMussbacher GAtlee JBultan T(2019)Localized or architecturalProceedings of the 41st International Conference on Software Engineering: Companion Proceedings10.1109/ICSE-Companion.2019.00132(316-317)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE-Companion.2019.00132
Cody-Kenny BO'Neill MBarrett SPetke JStolee KLangdon WWeimer W(2018)Performance localisationProceedings of the 4th International Workshop on Genetic Improvement Workshop10.1145/3194810.3194815(27-34)Online publication date: 2-Jun-2018
https://dl.acm.org/doi/10.1145/3194810.3194815
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents