Empirical Computational ComplexityABSTRACTComputational complexity is the standard language for talkingabout the asymptotic behavior of algorithms. We propose a sim-ilar notion, which we call empirical computational complexity, fordescribing the scalability of a program in practice. Constructing amodel of empirical computational complexity involves running aprogram on workloads whose sizes span several orders of magni-tude, measuring their performance, and constructing a model thatpredicts the program’s performance as a function of input size.We describe our tool, the Trend Profiler (trend-prof), forconstructing models of empirical computational complexity thatpredict how many times each basic block in a program runs as afunction of input size. We show for several real-world programs(such as gcc and gzip) that the number of times that scalability-critical basic blocks execute is often well modeled by either a line(y = a+ bx) or a power law (y = axb). We ran trend-prof onseveral real-world programs and found interesting facts about theirscaling behavior including two developer-confirmed performancebugs. By using trend-prof, a programmer can find perfor-mance bugs before they happen.1. INTRODUCTIONComputer scientists talk about the scalability of algorithms interms of computational complexity: Quicksort is O(nlogn) in thesize of the array; depth-first search is O(e) in the number of edgesin the graph. A similar idea is useful for describing program behav-ior in practice. In particular, we propose measuring multiple runsof a program and constructing empirical models that predict theperformance of the program as a function of the size of its inputs.Consider the following code.node*lastnode(node*n) {if (!n) return NULL;while (n->next) n = n->next;return n;}From a performance perspective, this code looks fishy; it is com-puting the last element in a list in time linear in the list’s length.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$5.00.The Trend Profile technique:• Many inputs spanning magnitudes: Profile across inputswhose sizes span several orders of magnitude.• Separate source-line observations: count the number ofexecutions of each basic block separately.• Two dimensional model: fit these counts versus some rea-sonable measure of input size.• Linear and power law fits: fit to a line in linear-linear andlog-log space, which tend to find linear and power lawmodels respectively.Adding a pointer directly to the last element in the list would ad-mit an obvious constant time implementation of this function. Ofcourse, if the list’s size is a small constant, then the performanceimpact of this code is likely to be negligible, and adding the pointermight not be worth the cost in code complexity and memory foot-print. On the other hand, ifthese liststend to be long, and especiallyif their sizes increase with the size of the input to the program as awhole, then this code constitutes a performance bug.The crucial piece of information is how this code is used in thecontext of the rest of the program. This code is from a C parser usedin a program analysis system [11]. In practice the sizes of the listsincrease as the square root of input size. On small- to medium-sizeinputs, this line is not particularly high on the list of what a typicalprofiler reports, but on large inputs the problem suddenly becomesapparent.We describe a technique for constructing models of the empiricalcomputational complexity of a program (Section 2). These modelspredict the asymptotic behavior of programs based on observationof multiple runs of the program. We describe our tool, Trend Pro-filer (trend-prof), that measures the number of times each ba-sic block in a program is executed and automatically builds linear( ˆy = a+bx) and power law( ˆy = axb) models that predict how manytimes a basic block will be executed as a function of user-specifiedinput size (Section 3).With trend-prof we found the scalability problem describedabove and several other interesting characteristics of several largeC and C++ programs, including gcc and gzip (Section 4). Run-ning trend-prof reveals trends not only in the performance ofprograms we measured but also in the characteristics of the work-loads on which we ran the programs. By extrapolating these trends,trend-prof can predict how many times each piece of the pro-gram will execute on inputs larger than any of those that it mea-sured. In particular it can identify pieces of code that scale worseFacts about the trend-prof technique:• It is easy to apply to programs without detailed knowledgeof their internals.• Our models do not fit every line of code well, but thoselines that execute frequently often fit well.• Simply ranking the models in decreasing order by 1) ex-ponent or 2) their prediction for a fixed large input sizealmost always points to interesting lines of code or showsthat the whole program is linear.• It reveals facts about 1) the program and 2) the data, asseen through the program.• It can reveal a more accurate model of the actual behaviorthan a worst-case theoretical analysis.than the program as a whole; such code constitutes a performancebug waiting to happen. We find that on the programs we mea-sured, linear and powerlaw models generally fit the most-executedbasic blocks of the programs well (Section 5). We propose thattrend-prof or a similar technique be used to make quantitativestatements about the performance and scalability of complex pro-grams.2. EMPIRICAL COMPUTATIONAL COM-PLEXITYA model of empirical computational complexity for a piece ofcode relates a workload’s size to the code’s performance on thatworkload. We use the term “size” rather loosely to refer to anymeasure of how hard the workload is. Thus, we expect “bigger”workloads to consume more units of performance. These modelsare quantitative; they predict a performance-relevant quantity as afunction of a workload’s size. For example, a model of a pieceof code to compute the transitive closure of a graph might predictthe number of machine instructions executed as a