Measuring empirical computational complexity Export

@inproceedings{citeulike:5287267, 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.}, address = {New York, NY, USA}, author = {Goldsmith, Simon F. and Aiken, Alex S. and Wilkerson, Daniel S.}, booktitle = {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}, citeulike-article-id = {5287267}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1287681}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1287624.1287681}, doi = {10.1145/1287624.1287681}, isbn = {978-1-59593-811-4}, keywords = {aoa, experimental}, location = {Dubrovnik, Croatia}, pages = {395--404}, posted-at = {2009-07-28 06:42:20}, priority = {2}, publisher = {ACM}, title = {Measuring empirical computational complexity}, url = {http://dx.doi.org/10.1145/1287624.1287681}, year = {2007} }

TY - CONF ID - citeulike:5287267 L3 - citeulike-article-id:5287267 N2 - 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. CY - Dubrovnik, Croatia SN - 978-1-59593-811-4 AD - New York, NY, USA EP - 404 TI - Measuring empirical computational complexity PB - ACM T2 - 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 SP - 395 KW - aoa KW - experimental AU - Goldsmith, Simon AU - Aiken, Alex AU - Wilkerson, Daniel PY - 2007/// UR - http://dx.doi.org/10.1145/1287624.1287681 ER -