Article

Measuring empirical computational complexity

Authors:

Simon F. Goldsmith,

Daniel S. WilkersonAuthors Info & Claims

ESEC-FSE '07: Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering

Pages 395 - 404

https://doi.org/10.1145/1287624.1287681

Published: 07 September 2007 Publication History

Abstract

The standard language for describing the asymptotic behavior of algorithms is theoretical computational complexity. We propose a method for describing the asymptotic behavior of programs in practice by measuring their empirical computational complexity. Our method involves running a program on workloads spanning several orders of magnitude in size, measuring their performance, and fitting these observations to a model that predicts performance as a function of workload size. Comparing these models to the programmer's expectations or to theoretical asymptotic bounds can reveal performance bugs or confirm that a program's performance scales as expected. Grouping and ranking program locations based on these models focuses attention on scalability-critical code. We describe our tool, the Trend Profiler (trend-prof), for constructing models of empirical computational complexity that predict how many times each basic block in a program runs as a linear (y = a + bx) or a powerlaw (y = ax^b) function of user-specified features of the program's workloads. We ran trend-prof on several large programs and report cases where a program scaled as expected, beat its worst-case theoretical complexity bound, or had a performance bug.

References

[1]

A. Alexandrov, M. F. Ionescu, K. E. Schauser, and C. Scheiman. LogGP: Incorporating long messages into the LogP model - One step closer towards a realistic model for parallel computation. In SPAA '95: Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 95--105, New York, NY, USA, 1995. ACM Press.

Digital Library

[2]

G. Ammons, J.-D. Choi, M. Gupta, and N. Swamy. Finding and removing performance bottlenecks in large systems. In ECOOP 2004. Springer Berlin / Heidelberg.

[3]

L.O.Andersen.Program Analysis and Specialization for the C Programming Language. Ph.d. thesis, DIKU, Unversity of Copenhagen, 1994.

[4]

T. Ball and J. R. Larus. Optimally profiling and tracing programs. ACM Trans. Program. Lang. Syst., 16(4):1319--1360, 1994.

Digital Library

[5]

E. A. Brewer. High-level optimization via automated statistical modeling. In PPOPP '95: Proceedings of the 5th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 80--91, New York, NY, USA, 1995. ACM Press.

Digital Library

[6]

bzip2 project homepage. http://www.bzip.org/.

[7]

gcov documentation. http://gcc.gnu.org/onlinedocs/gcc/Gcov.html.

[8]

S. L. Graham, P. B. Kessler, and M. K. Mckusick. Gprof: A call graph execution profiler. In SIGPLAN '82: Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction, pages 120--126, New York, NY, USA, 1982. ACM Press.

Digital Library

[9]

M. Kluge, A. Knüpfer, and W. E. Nagel. Knowledge based automatic scalability analysis and extrapolation for MPI programs. In Euro-Par 2005 Parallel Processing: 11th International Euro-Par Conference, Lecture Notes in Computer Science. Springer-Verlag.

Digital Library

[10]

J. Kodumal and A. Aiken. Banshee: A scalable constraint-based analysis toolkit. In SAS '05: Proceedings of the 12th International Static Analysis Symposium. London, United Kingdom, September 2005.

Digital Library

[11]

S. McPeak and G. C. Necula. Elkhound: A fast, practical GLR parser generator. In Conference on Compiler Construction (CC04), 2004.

[12]

D. L. Métayer. ACE: An automatic complexity evaluator. ACM Trans. Program. Lang. Syst., 10(2):248--266, 1988.

Digital Library

[13]

J. A. Rice. Mathematical Statistics and Data Analysis. Duxbury Press, 2006.

[14]

M. Rosendahl. Automatic complexity analysis. Proceedings of the 4th International Conference on Functional Programming Languages and Computer Architecture, pages 144--156, 1989.

Digital Library

[15]

R. Rugina and K. Schauser. Predicting the running times of parallel programs by simulation. In Proceedings of the 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing, 1998.

Digital Library

[16]

V. Sarkar. Determining average program execution times and their variance. In PLDI '89: Proceedings of the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation, pages 298--312, New York, NY, USA, 1989. ACM Press.

Digital Library

[17]

G. Sevitsky, W. de Pauw, and R. Konuru. An information exploration tool for performance analysis of Java programs. In TOOLS '01: Proceedings of the Technology of Object-Oriented Languages and Systems, page 85, Washington, DC, USA, 2001. IEEE Computer Society.

Digital Library

[18]

E. Ukkonen. A linear-time algorithm for finding approximate shortest common superstrings. In Algorithmica, volume 5, pages 313--323, 1990.

[19]

B. Wegbreit. Mechanical program analysis. Commun. ACM, 18(9):528--539, 1975.

Digital Library

Cited By

Pesic DVujosevic-Janicic MMisic MProtic J(2024)A novel approach to source code assembling in the field of algorithmic complexityComputer Science and Information Systems10.2298/CSIS230730015P21:3(781-806)Online publication date: 2024
https://doi.org/10.2298/CSIS230730015P
Olaewe OAgbedemnab PIddrisu M(2024)An Optimised Hoffman Algorithm for Testing Linear Code EquivalencyMathematics and Computer Science10.11648/j.mcs.20240902.119:2(26-35)Online publication date: 29-Apr-2024
https://doi.org/10.11648/j.mcs.20240902.11
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
Show More Cited By

Index Terms

Measuring empirical computational complexity

Recommendations

An overview of computational complexity
ACM Turing award lectures

An historical overview of computational complexity is presented. Emphasis is on the fundamental issues of defining the intrinsic computational complexity of a problem and proving upper and lower bounds on the complexity of problems. Probabilistic and ...
An overview of computational complexity

An historical overview of computational complexity is presented. Emphasis is on the fundamental issues of defining the intrinsic computational complexity of a problem and proving upper and lower bounds on the complexity of problems. Probabilistic and ...
Kolmogorov Complexity and Computational Complexity

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ESEC-FSE '07: Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering

September 2007

638 pages

ISBN:9781595938114

DOI:10.1145/1287624

General Chair:
Ivica Crnkovic
Mälardalen University, Sweden
,
Program Chair:
Antonia Bertolino
ISTI-CNR, Italy

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 September 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ESEC/FSE07

Sponsor:

ESEC/FSE07: Joint 11th European Software Engineering Conference 2007

September 3 - 7, 2007

Dubrovnik, Croatia

Acceptance Rates

Overall Acceptance Rate 112 of 543 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

109
Total Citations
View Citations
957
Total Downloads

Downloads (Last 12 months)64
Downloads (Last 6 weeks)9

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pesic DVujosevic-Janicic MMisic MProtic J(2024)A novel approach to source code assembling in the field of algorithmic complexityComputer Science and Information Systems10.2298/CSIS230730015P21:3(781-806)Online publication date: 2024
https://doi.org/10.2298/CSIS230730015P
Olaewe OAgbedemnab PIddrisu M(2024)An Optimised Hoffman Algorithm for Testing Linear Code EquivalencyMathematics and Computer Science10.11648/j.mcs.20240902.119:2(26-35)Online publication date: 29-Apr-2024
https://doi.org/10.11648/j.mcs.20240902.11
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
Kuwalek P(2024)Assessment of Diagnostic Capabilities of Methods of Recreation of Voltage Fluctuations2024 IEEE 18th International Conference on Compatibility, Power Electronics and Power Engineering (CPE-POWERENG)10.1109/CPE-POWERENG60842.2024.10604333(1-6)Online publication date: 24-Jun-2024
https://doi.org/10.1109/CPE-POWERENG60842.2024.10604333
Duque EGiraldo JVergara PNguyen PSlootweg H(2024)Tensor power flow formulations for multidimensional analyses in distribution systemsInternational Journal of Electrical Power & Energy Systems10.1016/j.ijepes.2024.110275162(110275)Online publication date: Nov-2024
https://doi.org/10.1016/j.ijepes.2024.110275
Sumitani RSilva LCampos FPereira F(2023)A Class of Programs that Admit Exact Complexity Analysis via Newton?s Polynomial InterpolationProceedings of the XXVII Brazilian Symposium on Programming Languages10.1145/3624309.3624311(50-55)Online publication date: 25-Sep-2023
https://dl.acm.org/doi/10.1145/3624309.3624311
Ishimwe DChandra SBlincoe KTonella P(2023)Inferring Complexity Bounds from Recurrence RelationsProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3617853(2198-2200)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3617853
Hutter ESolomonik EMohror KArnold DBadia R(2023)Application Performance Modeling via Tensor CompletionProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3581784.3607069(1-14)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3581784.3607069
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
Zhao YXiao LBondi AChen BLiu Y(2023)A Large-Scale Empirical Study of Real-Life Performance Issues in Open Source ProjectsIEEE Transactions on Software Engineering10.1109/TSE.2022.316762849:2(924-946)Online publication date: 1-Feb-2023
https://doi.org/10.1109/TSE.2022.3167628
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