1\" @(#)profiling.me 1.6 03/14/82 2.sh 1 "Types of Profiling" 3.pp 4There are several different uses for program profiles, 5and each may require different information from the profiles, 6or different presentation of the information. 7We distinguish two broad categories of profiles: 8those that present counts of statement or routine invocations, 9and those that display timing information about statements 10or routines. 11Counts are typically presented in tabular form, 12often in parallel with a listing of the source code. 13Timing information could be similarly presented; 14but more than one measure of time might be associated with each 15statement or routine. 16For example, 17in the framework used by \fBgprof\fP 18each profiled segment would display two times: 19one for the time used by the segment itself, and another for the 20time inherited from code segments it invokes. 21.pp 22Execution counts are used in many different contexts. 23The exact number of times a routine or statement is activated 24can be used to determine if an algorithm is performing as 25expected. 26Cursory inspection of such counters may show algorithms whose 27complexity is unsuited to the task at hand. 28Careful interpretation of counters can often suggest 29improvements to acceptable algorithms. 30Precise examination can uncover subtle errors in an 31algorithm. 32At this level, profiling counters are similar to 33debugging statements whose purpose is to show the number of times 34a piece of code is executed. 35Another view of such counters is as boolean values. 36One may be interested that a portion of code has executed at 37all, for exhaustive testing, or to check that one implementation 38of an abstraction completely replaces a previous one. 39.pp 40Execution counts are not necessarily proportional to the amount 41of time required to execute the routine or statement. 42Further, the execution time of a routine will not be the same for 43all calls on the routine. 44The criteria for establishing execution time 45must be decided. 46If a routine implements an abstraction by invoking other abstractions, 47the time spent in the routine will not accurately reflect the 48time required by the abstraction it implements. 49Similarly, if an abstraction is implemented by several 50routines the time required by the abstraction will be distributed 51across those routines. 52.pp 53Given the execution time of individual routines, 54\fBgprof\fP accounts to each routine the time spent 55for it by the routines it invokes. 56This accounting is done by assembling a \fIcall graph\fP with nodes that 57are the routines of the program and directed arcs that represent 58calls from call sites to routines. 59We distinguish among three different call graphs for a program. 60The \fIcomplete call graph\fP incorporates all routines and all 61potential arcs, 62including arcs that represent calls to functional parameters 63or functional variables. 64This graph contains the other two graphs as subgraphs. 65The \fIstatic call graph\fP includes all routines and all possible arcs 66that are not calls to functional parameters or variables. 67The \fIdynamic call graph\fP includes only those routines and 68arcs traversed by the profiled execution of the program. 69This graph need not include all routines, nor need it include all 70potential arcs between the routines it covers. 71It may, however, include arcs to functional parameters or 72variables that the static call graph may omit. 73The static call graph can be determined from the (static) program text. 74The dynamic call graph is determined only by profiling an 75execution of the program. 76The complete call graph for a monolithic program could be determined 77by data flow analysis techniques. 78The complete call graph for programs that change 79during execution, by modifying themselves or dynamically loading 80or overlaying code, may never be determinable. 81Both the static call graph and the dynamic call graph are used 82by \fBgprof\fP, but it does not search for the complete call 83graph. 84