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