\" @(#)gathering.me 1.1 %G%
.sh 1 "Gathering Profile Data"
Routine calls or statement executions can be measured by having a
compiler augment the code at strategic points.
The additions can be inline increments to counters [Knuth71]
[Satterthwaite72] [Joy79] or calls to
monitoring routines [Unix].
The counter increment overhead is low, and is suitable for
statement level profiling.
A call to the monitoring routine has an overhead on par with a
call to a regular routine, and is therefore reasonably suited
only to routine level profiling.
However, the monitoring routine solution has certain advantages.
Whatever counters are needed by the monitoring routine can be
managed by the monitoring routine itself, rather than being
distributed around the code.
In particular, a monitoring routine can be called from separately
whereas the counters would have to be distributed among the separately
In addition, different monitoring routines can be linked into the
program to assemble different profiling data without having to
change the compiler or recompile the program.
We have exploited this approach;
our compilers for C, Fortran77, and Pascal can insert calls to a
monitoring routine in the prologue for each routine.
We are interested in gathering three pieces of information during
program execution: call counts and execution times for
each profiled routine, and the arcs of the dynamic call graph
traversed by this execution of the program.
By post-processing of this data we can construct the dynamic call
graph for this execution of the program and propagate times along
the edges of this graph to attribute times for routines to the
routines that invoke them.
We make the simplifying assumption that all calls to a specific
routine require the same amount of time to execute.
This assumption may disguise the fact that some calls (or worse, some call
sites) always invoke a routine such that its execution is
faster (or slower) than the average time for that routine.
However, gathering of the profiling information should not greatly
interfere with the running of the program.
Thus, the monitoring routine must not produce trace output each
The volume of data thus produced would be unmanageably large,
and the time required to record it would overwhelm the running
Similarly, the monitoring routine can not perform the analysis of
the profiling data (e.g. assembling the call graph, propagating
times around it, discovering cycles, etc.) during program
Our solution is to gather profiling data in memory during program
execution and to condense it to a file as the profiled
This file is then processed by a separate program to produce the
listing of the profile data.
An advantage of this approach is that the profile data for
several executions of a program can be combined by the
post-processing to provide a profile of a large number of
executions, and a large amount of program execution time.
The execution time monitoring consists of three parts.
The first part allocates and initializes the runtime monitoring data
structures before the program begins execution.
The third part condenses these data structures and writes them
to a file as the program terminates.
The second part is the monitoring routine invoked from the
prologue of each profiled routine.
The monitoring routine is discussed in detail in the following sections.
Our monitoring routine counts the number of times each profiled
The monitoring routine also records the arc in the call graph
that activated the profiled routine.
In fact, the count is associated with the arc in the call graph
rather than with the routine.
Call counts for routines can then be determined by summing the counts
on arcs directed into that routine.
In a machine-dependent fashion, the monitoring routine notes its
This address is in the prologue of some profiled routine that is
at the head of an arc in the dynamic call graph.
The monitoring routine also discovers the return address for that
routine, thus identifying the call site, or tail of the arc.
The tail of the arc is in the \fIcaller\fP, and the head is in
For example, if a routine A calls a routine B, A is the caller,
The prologue of B will include a call to the monitoring routine
that will note the arc from A to B and either initialize or
increment a counter for that arc.
One can not afford to have the monitoring routine output tracing
information as each arc is identified.
Therefore, the monitoring routine maintains a table of all the
arcs discovered, with counts of the numbers of times each is
traversed during execution.
This table is accessed once per routine call, so access to it
must be as fast as possible so as not to overwhelm the time
required to execute the program.
Our solution is to access the table through a hash table.
We use the call site as the primary key with the callee
address being the secondary key.
Since each call site typically calls only one callee, we can
reduce (usually to one) the number of minor lookups based on the callee.
Another alternative, would use the callee as the primary key and the
call site as the secondary key.
Such an organization has the advantage of associating callers with
callees, at the expense of longer lookups in the monitoring
We are fortunate to be running in a virtual memory environment,
and (for the sake of speed) were able to allocate enough space
for the primary hash table to allow a one-to-one mapping from
call site addresses to the primary hash table.
Thus our hash function was trivial to calculate and collisions
occurred only for call sites that called to multiple
destinations (e.g. functional parameters and variables).
A one level hash function using both call site and callee would
result in an unreasonably large hash table.
Further, the number of call sites and callees is not known during
execution of the profiled program.
Not all callers and callees can be identified by the monitoring
Routines that were compiled without the profiling augmentations
will not call the monitoring routine as part of their prologue,
and thus we will never discover arcs whose heads are in these
One need not profile all the routines in a program.
Routines that are not profiled run at full speed.
Certain routines, notably exception handlers, are invoked by
non-standard calling sequences.
Thus we may know the head of an arc, but find it difficult or
impossible to determine the tail of the arc.
Often in these cases the apparent tail of the arc is not a call
Such anomalies cause us to declare a routine invocation
The execution times for routines can be gathered in at least two
One method measures the execution time of a routine by measuring
the elapsed time from routine entry to routine exit.
Unfortunately, time measurement is complicated on time sharing
systems by the interruptions of program time relative to real time.
A second method records the value of the program counter at some
interval, and infers execution time from the distribution of the
samples within the program.
This technique is particularly suited to time sharing systems,
where the interruptions of program time can serve as the basis for sampling
Notice that, whereas the first method could provide exact timings,
the second is inherently a statistical approximation.
The sampling method need not require support from the operating
system: all that is needed is the ability to set and respond to
``alarm clock'' interrupts that run relative to program time.
It is imperative that the intervals be uniform since the
sampling of the program counter rather than the duration of the
interval is the basis of the distribution.
If sampling is done too often, the interruptions to sample the
program counter will overwhelm the running of the profiled program.
On the other hand, the program must run for enough sampled
intervals that the distribution of the samples accurately
represents the distribution of time for the execution of the
As with routine call tracing, the monitoring routine can not
afford to output information for each program counter
In our computing environment, the operating system can provide a
histogram of the location of the program counter at the end of
each clock tick (1/60th of a second) in which a program runs.
The histogram is assembled in memory as the program runs.
This facility is enabled by our monitoring routine.
We have adjusted the granularity of the histogram so that
program counter values map one-to-one onto the histogram.
As the profiled program terminates,
the arc table and the histogram of
program counter samples is written to a file.
The arc table is condensed to consist of the head and tail
addresses of the arc and the count of the number of times the arc
was traversed by this execution of the program.
The recorded histogram consists of counters of the number of
times the program counter was found to be in each of the ranges covered
The ranges themselves are not output, since they can be summarized as a
lower and upper bound for the histogram and a step size.
projects / unix-history / blob