£prof: a Call Graph Execution Profiler i by Susan L. Graham Peter B. Kessler Marshall K McKusiclc Computer Science Division Electrical Engineering and Computer Science Department University of California, Berkeley Berkeley, California 94720 Abstract Large complex programs are composed of many small routines that implement abstractions for the routines that call them. To be useful, an execution profiler must attribute execution time in a way that is significant for the logical structure of a program as well as for its textual decomposition. This data must then be displayed to the user in a convenient and informative way. The gprof profiler accounts • for the running time of called routines in the run- ning time of the routines that call them. The design and use of this profiler is described. 1. Programs to be Profiled Software research environments normally include many large programs both for production use and for experimental investigation. These pro- grams are typically modular, in accordance with generally accepted principles of good program design. Often they consist of numerous small rou- tines that implement various abstractions. Some- times such large programs are written by one pro- grammer who has understood the requirements for these abstractions, and has programmed them appropriately. More frequently the program has had multiple authors and has evolved over time, changing the demands placed on the implementa- tion of the abstractions without changing the imple- mentation itself. Finally, the program may be assembled from a library of abstraction implemen- tations unexamined by the programmer. Once a large program is executable, it is often desirable to increase its speed, especially if small portions of the program are found to dominate its ZThil work was supported by grant MCS80-05144 from the National Scien~ Foundation. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, rcquircs a fcc and/or specific permission. © 1982 ACM 0-89791-074-5/82/006/0120 $00.75 execution time. The purpose of the gprof profiling tool is to help the user evaluate alternative imple- mentations of abstractions. We developed this tool in response to our efforts to improve a code genera- tor we were writing [Graham82]. The gprof design takes advantage of the fact that the programs to be measured are large, struc- tured and hierarchical. We provide a profile in which the execution time for a set of routines that implement an abstraction is collected and charged to that abstraction. The profile can be used to com- pare and assess the costs of various implementa- tions. The profiler can be linked into a program without special planning by the programmer. The overhead for using gprof is low; both in terms of added execution time and in the volume of profiling information recorded. 2. Types of Profiling There are several different uses for program profiles, and each may require different information from the profiles, or different presentation of the information. We distinguish two broad categories of profiles: those that present counts of statement or routine invocations, and those that display timing information about statements or routines. Counts are typically presented in tabular form, often in parallel with a listing of the source code. Timing information could be similarly presented; but more than one measure of time might be associated with each statement or routine. For example, in the framework used by gprof each profiled segment would display two times: one for the time used by the segment itself, and another for the time inher- ited from code segments it invokes. Execution counts are used in many different contexts. The exact number of times a routine or statement is activated can be used to determine if an algorithm is performing as expected. Cursory inspection of such counters may show algorithms whose complexity is unsuited to the task at hand. Careful interpretation of counters can often suggest improvements to acceptable algorithms. Precise examination can uncover subtle errors in an 120algorithm. At this level, profiling counters are simi- lar to debugging statements whose purpose is to show the number of times a piece of code is exe- cuted. Another view of such counters is as boolean values. One may be interested that a portion of code has executed at all, for exhaustive testing, or to check that one implementation of an abstraction completely replaces a previous one. Execution counts are not necessarily propor- tional to the amount of time required to execute the routine or statement. Further, the execution time of a routine will not be the same for all calls on the routine. The criteria for establishing execution time must be decided. If a routine implements an abstraction by invoking other abstractions, the time spent in the routine will not accurately reflect the time required by the abstraction it implements. Similarly, if an abstraction is implemented by several routines the time required by the abstrac- tion will be distributed across those routines. Given the execution time of individual routines, gprof accounts to each routine the time spent for it by the routines it invokes. This accounting is done by assembling a call graph with nodes that are the routines of the program and directed arcs that represent calls from call sites to routines. We dis- tinguish among three different call graphs for a pro- gram. The complete call graph incorporates all rou- tines and all potential arcs, including arcs that represent calls to functional parameters or func- tional variables. This graph contains the other two graphs as subgraphs. The static call graph includes all routines and all possible arcs that are not calls to