Measuring empirical computational complexity

Simon Goldsmith, Alex Aiken, Daniel Shawcross Wilkerson

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 = axb) 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.

BibTeX

@inproceedings{Goldsmith-al:FSE07,
  author    = {Simon Goldsmith and
               Alex Aiken and
               Daniel Shawcross Wilkerson},
  title     = {Measuring empirical computational complexity},
  booktitle = {{ESEC/SIGSOFT} {FSE}},
  pages     = {395--404},
  publisher = {{ACM}},
  year      = {2007},
}

Measuring empirical computational complexity

Abstract

Related papers