Measuring empirical computational complexity

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: Albert Alexandrov , Mihai F. Ionescu , Klaus E. Schauser , Chris Scheiman, LogGP: incorporating long messages into the LogP model—one step closer towards a realistic model for parallel computation, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.95-105, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215427]
• 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: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1319-1360, July 1994 [doi>10.1145/183432.183527]
• 5: Eric A. Brewer, High-level optimization via automated statistical modeling, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.80-91, July 19-21, 1995, Santa Barbara, California, United States
• 6: bzip2 project homepage. http://www.bzip.org/.
• 7: gcov documentation. http://gcc.gnu.org/onlinedocs/gcc/Gcov.html.
• 8: Susan L. Graham , Peter B. Kessler , Marshall K. Mckusick, Gprof: A call graph execution profiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.120-126, June 23-25, 1982, Boston, Massachusetts, United States
• 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.
• 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.
• 11: S. McPeak and G. C. Necula. Elkhound: A fast, practical GLR parser generator. In Conference on Compiler Construction (CC04), 2004.
• 12: Daniel Le Métayer, ACE: an automatic complexity evaluator, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.2, p.248-266, April 1988 [doi>10.1145/42190.42347]
• 13: J. A. Rice. Mathematical Statistics and Data Analysis. Duxbury Press, 2006.
• 14: Mads Rosendahl, Automatic complexity analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.144-156, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99381]
• 15: Predicting the Running Times of Parallel Programs by Simulation, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.654, March 30-April 03, 1998
• 16: V. Sarkar, Determining average program execution times and their variance, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.298-312, June 19-23, 1989, Portland, Oregon, United States
• 17: Gary Sevitsky , Wim de Pauw , Ravi Konuru, An Information Exploration Tool for Performance Analysis of Java Programs, Proceedings of the Technology of Object-Oriented Languages and Systems, p.85, March 12-14, 2001
• 18: E. Ukkonen. A linear-time algorithm for finding approximate shortest common superstrings. In Algorithmica, volume 5, pages 313--323, 1990.
• 19: Ben Wegbreit, Mechanical program analysis, Communications of the ACM, v.18 n.9, p.528-539, Sept. 1975 [doi>10.1145/361002.361016]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Measurement, Performance

Keywords:
empirical computational complexity, trend-prof