\section{Experimental data collection}

\label{s:data}

Preliminary empirical data was collected from three large Unix
installations.
The problem domain is not particularly well-defined,
but is rather ``the mishmash of things one wants to do on a
typical research Unix machine.''  On the SunOS and Mac OS X machines
we located every
shared object and used the unix commands $\mathsf{nm}$ or
$\mathsf{objdump}$ to obtain a listing of the relocatable symbols
(i.e., references to subroutines in shared libraries).  
For the Linux machine, a more sophisticated approach was used that
involved disassembling every executable object and decoding the
PLT and GOT tables for shared library calls.  For this reason
the Linux data is much more fine-grained and reliable; for example,
our data set for Linux includes the frequencies of all the x86
machine instructions, in addition to almost a half-million subroutines.

\begin{tabular}{lrr}
Operating System & \# Objects & \# Components \\ \hline
Linux (SuSE) & 12136 & 455716 \\
SunOS & 23774 & 110306 \\
Mac OS X & 2334 & 37677
\end{tabular}

We counted the number of references to each component, sorted these
by frequency, and this data is plotted in \reffig{f:rates}.  
The observed counts match nicely the asymptotic prediction made in
\refsec{s:newderiv} (the family of curves $c n^{-1}$ is shown
as dotted lines).
To account for machine instructions, which are not included in the tally
for the Mac OS X and SunOS machines
but constitute by far the most frequently occurring software components,
we started numbering the components for these machines at $n=50$.  Without this
adjustment the rates have a characteristic ``flat top'' and then
rapidly converge to $n^{-1}$ lines; this is an artifact of the
log-log scale.  

The pronounced ``steps'' in the data for large $n$ occur because
there are many rarely-used subroutines with only a few references;
this is typical of such plots (see, e.g., \cite{Powers:ACL:1998}).

Another prediction that may follow from our model is that the number 
of distinct components used in a program should approach a normal distribution:
under maximum entropy conditions the use of components is statistically
independent, and so the central limit theorem applies.
This is reminiscent of the
Erd{\"o}s-Kac theorem \cite{Erdos:AJM:1940} that the number of prime factors 
of integers converges to a normal distribution.  \reffig{f:erdos} shows some
preliminary results that support this result, drawn from the
SuSE Linux data.  The number of component references have been
normalized by an estimated variance of $\sigma^2 = c s^2$ where
$s$ is the program size.  Subfigure (c) shows a suggestively
shaped distribution for the inset box of (a), a region where there
is good ``saturation'' of the problem domain with programs.

Our preliminary data demonstrates a Heaps' style law for
vocabulary growth \cite[\S 7.5]{Heaps:1978}: the number of unique 
components encountered
in examining the first $s$ bytes of the corpus grows roughly
as a power law $s^\alpha$ with $\alpha \approx 0.8$.  We have
not found a satisfactory theoretical explanation.

% We were able to collect very detailed information from Linux RPMs,
% because this is open-source software.  Disassembly of commercial software
% is often prohibited by licenses, and therefore its legality is uncertain.

%\input{estimation}


% Erdos-Kac

\begin{figure*}
\subfigure[Scatter-plot of the number of subroutine references]{
\includegraphics[scale=0.6]{numrefs}
}
\begin{minipage}[b]{2in}
\subfigure[Distribution histogram]{
\includegraphics[scale=0.4]{erdosall}
} 
\subfigure[Distribution for inset box]{
\includegraphics[scale=0.4]{erdos}
}
\end{minipage}
\caption{\label{f:erdos}Data suggesting a library analogue of the
Erd{\"o}s-Kac theorem.  (a) A scatter-plot showing the number of
distinct library subroutines used vs. software size for the Linux RPM
data.  (b) Histogram for the number of references, normalized (see text).
(c) Histogram only for the inset box of (a), illustrating an
Erd{\"o}s-Kac-style normal distribution for the number of components used
in software.  Such plots might provide a useful tool for assessing
the extent of reuse vs. ideal predictions from a model.}
\end{figure*}
