mprof.tex

早期freebsd实现

\label{recursive call figure}
\end{figure}

We considered several solutions to the problems caused by cycles and
adopted the most conservative solution.  One way to avoid recording
spurious allocation caused by recursion is for the monitor to identify
the cycles before recording the allocation.  For example, in
Figure~\ref{recursive call figure}, the monitor could realize that it
had already credited {\tt F} with the 10 bytes when it encountered
{\tt F} calling {\tt G} the second time.  This solution adds overhead
to the monitor and conflicts with our goal to make the monitor as
unobtrusive as possible.

The solution that we adopted was to merge functions that are in a
cycle into a single node in the reduction phase.  Thus, each strongly
connected component in the dynamic call graph is merged into a single
node.  The result is a call graph with no cycles.  This process is
also used by {\tt gprof}, and described carefully
elsewhere~\cite{graham83:gprof}.  Such an approach works well in {\tt
gprof} because C programs, for which {\tt gprof} was primarily
intended, tend to have limited amounts of recursion.  Lisp programs,
for which {\tt mprof} is also intended, intuitively contain much more
recursion.  We have experience profiling a number of large Common Lisp
programs.  We observe several recursive cycles in most programs, but
the cycles generally contain a small percentage of the total functions
and {\tt mprof} is quite effective.

\subsection{Lisp Implementation}

So far, we have described the implementation of {\tt mprof} for C.
The Lisp implementation is quite similar, and here we describe the
major differences.  C has a single function, {\tt malloc}, that is
called to allocate memory explicitly.  Lisp has a large number of
primitives that allocate memory implicitly (i.e., {\tt cons}, {\tt *},
{\tt intern}, etc.).  To make {\tt mprof} work, these primitives must
be modified so that every allocation is recorded.  Fortunately, at the
Lisp implementation level, all memory allocations may be channeled
through a single routine.  We worked with KCL (Kyoto Common Lisp),
which is implemented in C.  In KCL, all Lisp memory allocations are
handled by a single function, {\tt alloc\_object}.  Just as we had
modified {\tt malloc} in C, we were able to simply patch {\tt
alloc\_object} to monitor memory allocation in KCL.

The other major difference in monitoring Lisp is that the addresses
recorded by the monitor must be translated into Lisp function names.
Again, KCL makes this quite easy because Lisp functions are defined in
a central place in KCL and the names of the functions are known when
they are defined.  Many other Lisp systems are designed to allow
return addresses to be mapped to symbolic function names so that the
call stack can be printed at a breakpoint.  In this case, the monitor
can use the same mechanism to map return addresses to function names.
Therefore, in Lisp systems in which addresses can be quickly mapped to
function names, memory profiling in the style of {\tt mprof} is not a
difficult problem.  In systems in which symbolic names are not
available in compiled code, profiling is more difficult.  Furthermore,
many systems open-code important allocation functions, like {\tt
cons}.  Because open-coded allocation functions will not necessarily
call a central allocation function (like {\tt alloc\_object}), such
allocations will not be observed by {\tt mprof}.  To avoid such a loss
of information, {\tt mprof} should be used in conjunction with program
declarations that will force allocation functions such as {\tt cons}
to be coded out-of-line.

\section{Measurements}
\label{measurements}

We have measured the C implementation of {\tt mprof} by instrumenting
four programs using {\tt mprof}.  The first program, {\tt example}, is
our example program with the number of widgets allocated increased to
100,000 to increase program execution time.  The second program, {\tt
fidilrt}, is the runtime library of FIDIL, a programming language for
finite difference computations~\cite{hilfinger88:fidil}.  The third
program, {\tt epoxy}, is an electrical and physical layout optimizer
written by Fred Obermeier~\cite{fwo87:epoxy}.  The fourth program,
{\tt crystal}, is a VLSI timing analysis
program~\cite{ouster85:crystal}.  These tests represent a small
program ({\tt example}, 100 lines); a medium-sized program ({\tt
fidilrt}, 7,100 lines); and two large programs ({\tt epoxy}, 11,000
lines and {\tt crystal}, 10,500 lines).  In the remainder of this
section, we will look at the resource consumption of {\tt mprof} from
two perspectives: execution time overhead and space consumption.

\subsection{Execution Time Overhead}

There are two sources of execution time overhead associated with {\tt
mprof}: additional time spent monitoring an application and the time
to reduce and print the data produced by the monitor.  The largest
source of monitor overhead is the time required to traverse the
complete call chain and associate allocations with caller/callee
pairs.  We implemented a version of {\tt mprof}, called {\tt mprof-},
which does not create the allocation call graph.  With this version,
we can see the relative cost of the allocation call graph.  The ratio
of the time spent with profiling to the time spent without profiling
is called the {\em slowdown factor\/}.  Table \ref{cpu:tab} summarizes
the execution time overheads for our four applications.  Measurements
were gathered running the test programs on a VAX 8800 with 80
megabytes of physical memory.

\begin{table}[htbp]
\begin{singlespace}
\begin{center}
\begin{tabular}{|l|r|r|r|r|} \hline
\multicolumn{1}{|c|}{} & \multicolumn{4}{|c|}{Cost} \\ \cline{2-5}
\multicolumn{1}{|c|}{Resource Description} & 
\multicolumn{1}{|c|}{\tt example} & 
\multicolumn{1}{|c|}{\tt fidilrt} & 
\multicolumn{1}{|c|}{\tt epoxy} & 
\multicolumn{1}{|c|}{\tt crystal} \\ \hline
Number of allocations & 100000 & 77376 & 306295 & 31158 \\
Execution time with {\tt mprof} (seconds) & 62.7 & 132.7 & 188.8 & 134.1 \\
Execution time with {\tt mprof-} (seconds) & 44.1 & 116.0 & 149.7 & 25.5 \\
Execution time without {\tt mprof} (seconds) & 17.9 & 107.1 & 52.1 & 13.2 \\
\hline
Slowdown using {\tt mprof} & 3.5 & 1.2 & 3.6 & 10.1 \\
Slowdown using {\tt mprof-} & 2.5 & 1.1 & 2.9 & 1.9 \\
\hline 
Reduction and display time (seconds) & 10.3 & 28.8 & 28.3 & 36.8 \\
\hline 
\end{tabular}
\caption{Execution Time Overhead of {\tt mprof}}
\label{cpu:tab}
\end{center}
\end{singlespace}
\end{table}

The slowdown associated with {\tt mprof} varies widely, from 1.5 to
10.  {\tt crystal} suffered the worst degradation from profiling
because {\tt crystal} uses a depth-first algorithm that results in
long call chains.  Programs without long call chains appear to slow
down by a factor of 2--4.  If the allocation call graph is not
generated and long call chains are not traversed, the slowdown is
significantly less, especially in the extreme cases.  Since {\tt
mprof} is a prototype and has not been carefully optimized, this
overhead seems acceptable.  From the table, we see the reduction and
display time is typically less than a minute.

\subsection{Storage Consumption}
\label{mmeas:sec}

The storage consumption of {\tt mprof} is divided into the additional
memory needed by the monitor as an application executes, and the
external storage required by the profile data file.  The most
significant source of memory used by the monitor is the data stored
with each object allocated: an object size and a pointer needed to
construct the memory leak table.  The monitor also uses memory to
record the memory bins and caller/callee byte counts and must write
this information to a file when the application is finished.  We
measured how many bytes of memory and disk space are needed to store
this information.  Table~\ref{mem:tab} summarizes the measurements of
storage consumption associated with {\tt mprof}.

\begin{table}[htbp]
\begin{singlespace}
\begin{center}
\begin{tabular}{|l|r|r|r|r|} \hline
\multicolumn{1}{|c|}{} & \multicolumn{4}{|c|}{Cost} \\ \cline{2-5}
\multicolumn{1}{|c|}{Resource Description} & 
\multicolumn{1}{|c|}{\tt example} & 
\multicolumn{1}{|c|}{\tt fidilrt} & 
\multicolumn{1}{|c|}{\tt epoxy} & 
\multicolumn{1}{|c|}{\tt crystal} \\ \hline
Number of allocations & 100000 & 61163 & 306295 & 31158 \\
User memory allocated (Kbytes) & 20000 & 2425 & 6418  & 21464 \\
\hline
Per object memory (Kbytes) & 781 & 477 & 2393 & 168 \\
Other monitor memory (Kbytes) & 8.7 & 23.3 & 52.3 & 17.5 \\
Total monitor memory (Kbytes) & 790 & 500 & 2445 & 186 \\
Monitor fraction (\% memory allocated) & 4 & 17 & 28 & 1 \\
\hline
Data file size (Kbytes) & 4.5 & 8.1 & 28.6 & 9.6 \\
\hline 
\end{tabular}
\caption{Storage Consumption of {\tt mprof}}
\label{mem:tab}
\end{center}
\end{singlespace}
\end{table}

The memory overhead of {\tt mprof} is small, except that an additional
8 bytes of storage are allocated with every object.  In programs in
which many small objects are allocated, like {\tt epoxy}, {\tt mprof}
can contribute significantly to the total memory allocated.
Nevertheless, in the worst case, {\tt mprof} increases application
size by 1/3, and since {\tt mprof} is a development tool, this
overhead seems acceptable.  From the table we also see that the data
files created by {\tt mprof} are quite small ($<$ 30 Kbytes).

\section{Related Work}
\label{related work}

{\tt Mprof} is similar to the tool {\tt gprof}~\cite{graham83:gprof},
a dynamic execution profiler.  Because some of the problems of
interpreting the dynamic call graph are the same, we have borrowed
these ideas from {\tt gprof}.  Also, we have used ideas from the user
interface of {\tt gprof} for two reasons: because the information
being displayed is quite similar and because users familiar with {\tt
gprof} would probably also be interested in {\tt mprof} and would
benefit from a similar presentation.

Barach, Taenzer, and Wells developed a tool for finding storage
allocation errors in C programs~\cite{barach82:memprof}.  Their
approach concentrated on finding two specific storage allocation
errors: memory leaks and duplicate frees.  They modified {\tt malloc}
and {\tt free} so that every time that these functions were called,
information about the memory block being manipulated was recorded in a
file.  A program that examines this file, {\tt prleak}, prints out
which memory blocks were never freed or were freed twice.  This
approach differs from {\tt mprof} in two ways.  First, {\tt mprof}
provides more information about the memory allocation of programs than
{\tt prleak}, which just reports on storage errors.  Second, {\tt
prleak} generates extremely large intermediate files that are
comparable in size to the total amount of memory allocated by the
program (often megabytes of data).  Although {\tt mprof} records more
useful information, the data files it generates are of modest size
(see the table above).

\section{Conclusions}
\label{conclusions}

We have implemented a memory allocation profiling program for both C
and Common Lisp.  Our example has shown that {\tt mprof} can be
effective in elucidating the allocation behavior of a program so that
a programmer can detect memory leaks and identify major sources of
allocation.

Unlike {\tt gprof}, {\tt mprof} records every caller in the call chain
every time an object is allocated.  The overhead for this recording is
large but not impractically so, because we take advantage of the fact
that a call chain changes little between allocations.  Moreover,
recording this information does not require large amounts of memory
because there are relatively few unique caller/callee address pairs on
call chains in which allocation takes place, even in very large
programs.  We have measured the overhead of {\tt mprof}, and find that
typically it slows applications by a factor of 2--4 times, and adds up
to 33\% to the memory allocated by the application.  Because {\tt
mprof} is intended as a development tool, these costs are acceptable.

Because {\tt mprof} merges cycles caused by recursive function calls,
{\tt mprof} may be ineffective for programs with large cycles in their
call graph.  Only with more data will we be able to decide if many
programs (especially those written in Lisp) contain so many recursive
calls that cycle merging makes {\tt mprof} ineffective.  Nevertheless,
{\tt mprof} has already been effective in detecting KCL system
functions that allocate memory extraneously.\footnote{Using {\tt
mprof}, we noted that for a large object-oriented program written in
KCL, the system function {\tt every} accounted for 13\% of the memory
allocated.  We rewrote {\tt every} so it would not allocate any
memory, and decreased the memory consumption of the program by 13\%.}

As a final note, we have received feedback from C application
programmers who have used {\tt mprof}.  They report that the memory
leak table and the allocation bin table are both extremely useful,
while the direct allocation table and the allocation call graph are
harder to understand and also less useful.  Considering the execution
overhead associated with the allocation call graph and the complexity
of the table, it is questionable whether the allocation call graph
will ever be as helpful C programmers as the memory leak table.  On
the other hand, with automatic storage reclamation, the memory leak
table becomes unnecessary.  Yet for memory intensive languages, such
as Lisp, the need for effective use of the memory is more important,
and tools such as the allocation call graph might prove very useful.
Because we have limited feedback from Lisp programmers using {\tt
mprof}, we cannot report their response to this tool.

\bibliography{/spur2/larus/bib/abbrev,lispm,gc,/spur2/larus/bib/optim,spur,misc,lisp}
\bibliographystyle{plain}

\end{document}
%