Goldsmith, Aiken, and Wilkerson demonstrate a tool, trend-prof, that attempts, by running a program on various-sized workloads, to measure the empirical computational complexity of various parts of the program as a function of the variables categorizing the workloads. To the claim, “but gprof does that,” the authors point out that gprof will tell you the time spent, but not the complexity formula, unless one does manual post-processing of various gprof runs. To the complaint, “but I’ll drown in data,” the authors exhibit a powerful clusters algorithm that reduces 33,000 basic blocks to 1,500 clusters, of which 30 are flagged as costly; this is hardly enough data in which to drown. They also produce a realistic example of a worst-case cubic algorithm, which, in reality, exhibits quadratic behavior, an important difference.

The authors conclude by saying, “While anyone could attempt a performance-trend analysis of their program, most engineers do not; a generic and convenient tool for automatically computing a comprehensive performance-trend analysis belongs in every programmer’s toolbox.” I have seen enough systems that fail to scale to wish that more programmers had, and used, a tool like this one.