research-article

Algorithmic profiling

Authors:

Dmitrijs Zaparanuks,

Matthias HauswirthAuthors Info & Claims

PLDI '12: Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 67 - 76

https://doi.org/10.1145/2254064.2254074

Published: 11 June 2012 Publication History

Abstract

Traditional profilers identify where a program spends most of its resources. They do not provide information about why the program spends those resources or about how resource consumption would change for different program inputs. In this paper we introduce the idea of algorithmic profiling. While a traditional profiler determines a set of measured cost values, an algorithmic profiler determines a cost function. It does that by automatically determining the "inputs" of a program, by measuring the program's "cost" for any given input, and by inferring an empirical cost function.

References

[1]

A. Bergel, O. Nierstrasz, L. Renggli, and J. Ressia. Domain-specific profiling. In J. Bishop and A. Vallecillo, editors, Objects, Models, Components, Patterns, volume 6705 of Lecture Notes in Computer Science, pages 68--82. Springer, 2011.

Digital Library

[2]

B. Dufour, B. G. Ryder, and G. Sevitsky. Blended analysis for performance understanding of framework-based applications. In Proceedings of the 2007 international symposium on Software testing and analysis, ISSTA '07, pages 118--128. ACM, 2007.

Digital Library

[3]

S. F. Goldsmith. Measuring Empirical Computational Complexity. PhD thesis, University of California, Berkeley, 2009.

Digital Library

[4]

S. F. Goldsmith, A. S. Aiken, and D. S. Wilkerson. Measuring empirical computational complexity. In Proceedings of the the 6th joint meeting of the FSE, ESEC-FSE '07, pages 395--404. ACM, 2007.

Digital Library

[5]

S. L. Graham, P. B. Kessler, and M. K. McKusick. gprof: a call graph execution profiler. SIGPLAN Not., 39 (4): 49--57, 2004.

Digital Library

[6]

T. Israr, M. Woodside, and G. Franks. Interaction tree algorithms to extract effective architecture and layered performance models from traces. J. Syst. Softw., 80: 474--492, April 2007.

Digital Library

[7]

M. Jump and K. S. McKinley. Dynamic shape analysis via degree metrics. In Proceedings of the 2009 international symposium on Memory management, ISMM '09, pages 119--128. ACM, 2009.

Digital Library

[8]

C. McGeoch, P. Sanders, R. Fleischer, P. R. Cohen, and D. Precup. Experimental algorithmics, chapter Using finite experiments to study asymptotic performance. Springer, 2002.

Digital Library

[9]

C. C. Mcgeoch. Experimental analysis of algorithms. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, USA, 1986.

Digital Library

[10]

N. Mitchell, E. Schonberg, and G. Sevitsky. Making sense of large heaps. In Proceedings of the 23rd European Conference on ECOOP 2009, Genoa, pages 77--97. Springer, 2009.

Digital Library

[11]

S. Pheng and C. Verbrugge. Dynamic data structure analysis for java programs. In Program Comprehension, 2006. ICPC 2006. 14th IEEE International Conference on, pages 191--201, 2006.

Digital Library

[12]

E. Raman and D. I. August. Recursive data structure profiling. In Proceedings of the 2005 workshop on Memory system performance, MSP '05, pages 5--14. ACM, 2005.

Digital Library

[13]

M. Sagiv, T. Reps, and R. Wilhelm. Solving shape-analysis problems in languages with destructive updating. ACM Trans. Program. Lang. Syst., 20: 1--50, January 1998.

Digital Library

[14]

P. Sanders and R. Fleischer. Asymptotic complexity from experiments? a case study for randomized algorithms. In WAE '00: Proceedings of the 4th International Workshop on Algorithm Engineering, pages 135--146. Springer, 2001.

Digital Library

[15]

R. Wilhelm, S. Sagiv, and T. W. Reps. Shape analysis. In Proceedings of the 9th International Conference on Compiler Construction, CC '00, pages 1--17. Springer, 2000.

Digital Library

[16]

X. Xiao, J. Zhou, and C. Zhang. Tracking data structures for postmortem analysis. In ICSE 2011 NIER Track, 2011.

Digital Library

[17]

G. Xu and A. Rountev. Precise memory leak detection for java software using container profiling. In Proceedings of the 30th international conference on Software engineering, ICSE '08, pages 151--160. ACM, 2008.

Digital Library

[18]

G. Xu and A. Rountev. Detecting inefficiently-used containers to avoid bloat. In Proceedings of the 2010 ACM SIGPLAN conference on Programming language design and implementation, PLDI '10, pages 160--173, New York, NY, USA, 2010. ACM.

Digital Library

[19]

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 2009 ACM SIGPLAN conference on Programming language design and implementation, PLDI '09, pages 419--430. ACM, 2009.

Digital Library

[20]

G. Xu, N. Mitchell, M. Arnold, A. Rountev, E. Schonberg, and G. Sevitsky. Finding low-utility data structures. In Proceedings of the 2010 ACM SIGPLAN conference on Programming language design and implementation, PLDI '10, pages 174--186. ACM, 2010.

Digital Library

[21]

D. Zaparanuks and M. Hauswirth. The beauty and the beast: Separating design from algorithm. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP'11), 2011.

Digital Library

[22]

}Zaparanuks11bD. Zaparanuks and M. Hauswirth. Vision paper: The essence of structural models. In J. Whittle, T. Clark, and T. Kühne, editors, Model Driven Engineering Languages and Systems, volume 6981 of Lecture Notes in Computer Science, pages 470--479. Springer, 2011.

Digital Library

Cited By

Pham LSaad FHoffmann J(2024)Robust Resource Bounds with Static Analysis and Bayesian InferenceProceedings of the ACM on Programming Languages10.1145/36563808:PLDI(76-101)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656380
Zhao GGeorgiou SHassan SZou YTruong DCorbin TSpinellis DConstantinou EBacchelli A(2024)Enhancing Performance Bug Prediction Using Performance Code MetricsProceedings of the 21st International Conference on Mining Software Repositories10.1145/3643991.3644920(50-62)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1145/3643991.3644920
Alsaeed ZYoung MJust RFraser G(2023)Finding Short Slow Inputs Faster with Grammar-Based SearchProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598118(1068-1079)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598118
Show More Cited By

Index Terms

Algorithmic profiling

Recommendations

Algorithmic profiling
PLDI '12

Traditional profilers identify where a program spends most of its resources. They do not provide information about why the program spends those resources or about how resource consumption would change for different program inputs. In this paper we ...
Edge profiling versus path profiling: the showdown
POPL '98: Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Edge profiles are the traditional control flow profile of choice for profile-directed compilation. They have been the basis of path-based optimizations that select "hot" paths, even though edge profiles contain strictly less information than path ...
2D-Profiling: Detecting Input-Dependent Branches with a Single Input Data Set
CGO '06: Proceedings of the International Symposium on Code Generation and Optimization

Static compilers use profiling to predict run-time program behavior. Generally, this requires multiple input sets to capture wide variations in run-time behavior. This is expensive in terms of resources and compilation time. We introduce a new mechanism,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '12: Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2012

572 pages

ISBN:9781450312059

DOI:10.1145/2254064

General Chairs:
Jan Vitek
Purdue University
,
Haibo Lin
Microsoft China
,
Program Chair:
Frank Tip
IBM T.J. Watson Research Center

ACM SIGPLAN Notices Volume 47, Issue 6
PLDI '12
June 2012
534 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2345156
Issue’s Table of Contents

Copyright © 2012 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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '12

Sponsor:

SIGPLAN

PLDI '12: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 11 - 16, 2012

Beijing, China

Acceptance Rates

PLDI '12 Paper Acceptance Rate 48 of 255 submissions, 19%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

74
Total Citations
View Citations
1,450
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)8

Reflects downloads up to 17 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pham LSaad FHoffmann J(2024)Robust Resource Bounds with Static Analysis and Bayesian InferenceProceedings of the ACM on Programming Languages10.1145/36563808:PLDI(76-101)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656380
Zhao GGeorgiou SHassan SZou YTruong DCorbin TSpinellis DConstantinou EBacchelli A(2024)Enhancing Performance Bug Prediction Using Performance Code MetricsProceedings of the 21st International Conference on Mining Software Repositories10.1145/3643991.3644920(50-62)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1145/3643991.3644920
Alsaeed ZYoung MJust RFraser G(2023)Finding Short Slow Inputs Faster with Grammar-Based SearchProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598118(1068-1079)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598118
Li JZhang YLu SGunawi HGu XHuang FLi D(2023)Performance Bug Analysis and Detection for Distributed Storage and Computing SystemsACM Transactions on Storage10.1145/358028119:3(1-33)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3580281
Qin BTu TLiu ZYu TSong L(2022)Algorithmic Profiling for Real-World Complexity ProblemsIEEE Transactions on Software Engineering10.1109/TSE.2021.306765248:7(2680-2694)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TSE.2021.3067652
Ishimwe DNguyen KNguyen T(2021)Dynaplex: analyzing program complexity using dynamically inferred recurrence relationsProceedings of the ACM on Programming Languages10.1145/34855155:OOPSLA(1-23)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485515
Gottschall BEeckhout LJahre M(2021)TIP: Time-Proportional Instruction ProfilingMICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3466752.3480058(15-27)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3466752.3480058
Rogora DCarzaniga ADiwan AHauswirth MSoulé RBilas AMagoutis KMarkatos EKostic DSeltzer M(2020)Analyzing system performance with probabilistic performance annotationsProceedings of the Fifteenth European Conference on Computer Systems10.1145/3342195.3387554(1-14)Online publication date: 15-Apr-2020
https://dl.acm.org/doi/10.1145/3342195.3387554
He HJia ZLi SXu EYu TYu YWang JLiao XGrundy JLe Goues CLo D(2020)CP-detectorProceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering10.1145/3324884.3416531(623-634)Online publication date: 21-Dec-2020
https://dl.acm.org/doi/10.1145/3324884.3416531
Incerto ENapolitano ATribastone M(2020)Statistical Learning of Markov Chains of Programs2020 28th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)10.1109/MASCOTS50786.2020.9285947(1-8)Online publication date: 17-Nov-2020
https://doi.org/10.1109/MASCOTS50786.2020.9285947
Show More Cited By

View Options

Get Access

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