# Benchmarks
$docnav
We present here a large number of benchmarks. You can click on each
plot to view that plot as a high-resolution SVG file.
One major conclusion is that `fac` is generally about a factor of two
times slower than make. But do keep in mind that `fac` does
a lot more than make does, and is considerably easier to use in a
robustly correct manner. There are also still some remaining scaling
issues that should be addressed, which arise when there are 10k or so
files involved.
## Deep hierarchy
$\newcommand\O[1]{\mathcal{O}(#1)}$
In the following benchmarks, there are 9 C files and 9 header files
per directory, as well as 9 subdirectories. Each C file imports 10
header files as well as its matching header file. Every C file
implements the same simple linked list, and imports more system
headers than it needs (but not an unusual number) to try to make
compile times close to typical. In all of the plots below $N$ is the
number of C files that need to be built.
### Initial build (hierarchy)
The initial build takes linear time ($\O{N}$) in the best-case
scenario. Some build systems, however, have a large constant term
which can make a large difference up to surprisingly large systems.
In addition, some build systems may have a different $\O{N}$
prefactor, which can make an even bigger difference for large
systems.
### Touching all (hierarchy)
For the rebuild, we touch all the C files. The cost is still $\O{N}$
at best, but by remembering a hash of file content it is possible to
dramatically reduce the cost of the rebuild, which allows scons to win
in this case by more than an order of magnitude.
### Modify a C file (hierarchy)
The following test modifies a single C file, adding a newline to its
end. Thus in principle, the cost could be $\O{1}$, if you could
magically determine which files to rebuild. However, if you need to
check modification times on every file, it will still be $\O{N}$. I
believe tup "magically" determines which files to build by running a
background process that uses inotify (or similar) to wait for changes
to input files. You can note that scons here has a dramatically more
expensive $\O{N}$ cost, as it reads each C file to check dependencies
(I think).
### Modify a header file (hierarchy)
The following modifies a single header file, adding a newline to its
end. This should be close to identical to the former test, but
requires rebuilding about 10 times as many files. Thus the $\O{1}$
term is increased while the $\O{N}$ term is hardly affected.
### Doing nothing (hierarchy)
The cost of doing nothing can be $\O{1}$ if (as tup does) you employ a
background process to watch for changes. Otherwise, it is necessarily
$\O{N}$ as one checks each file for modifications.
## Linear dependency chain, flat directory
In the following tests, we have $N$ C files,
arranged in a linear chain. Each C file compiles to an executable
that is run to generate a header file that is included by the
following C file. This tests the scaling of each build system in the
extreme case of a highly dependent build, in contrast to the previous
case, in which each build operation could be performed independently.
### Initial build (linear chain)
Obviously again this must be $\O{N}$. As usual, scons and tup have a
noticeable $\O{1}$ contribution, which is much more significant for
tup. FIXME I think there must be a bug in the scons benchmarking in
this case.
### Rebuild (linear chain)
Here we remove all the generated executables and rerun, so again it is
$\O{N}$. This technically does not require an entire rebuild, since
we need do not need to rerun the executables, so long as they come out
the same as last time. But that is irrelevant, because compiling and
linking is way slower than running the executables.
### Modifying a C file (linear chain)
Here we modify a single C file, which causes the whole chain to be
rebuilt for most build systems, thus costing $\O{N}$. Again, scons's
tracking of file checksums makes this much faster, as it realizes that
the output is identical, so there is no rebuilding required. I do not
understand why tup is cheap here. Tup should need to rebuild
everything.
### Modifying a header (linear chain)
This test touches a header that only requires one rebuild. It thus
requires only $\O{1}$ rebuilds, but should with most systems require
$\O{N}$ checks of file modification times. Presumably my tests are
small enough that we aren't able to see the $\O{N}$ costs clearly.
### Doing nothing (linear chain)
This test should be close to identical to the previous one, but
without the $\O{1}$ build cost. Again, it looks boring because it
doesn't (yet) cover very large builds.
## Linear dependency chain, flat directory, cats
In the following tests, we have a very simple dependency chain in
which we `cat` a file $N$ times. This tests the scaling of each build
system in the extreme case of a highly dependent build, but with an
even faster build command, to highlight scaling issues by making
$\O{N}$ costs as small as possible.
### Initial build of cats
Obviously again this must be $\O{N}$. As usual, scons and tup have a
noticeable $\O{1}$ contribution, which is much more significant for
tup.
### Rebuild cats
Here we modify the source file from which the entire dependency chain
depends, which results in $\O{N}$ run cost.
### Doing nothing to cats
This test involves no changes, and thus should be very fast, as is the
case for all the "do nothing" builds.
## Independent C files
A bunch of C files with no interdependencies. A sort of polar
opposite of the linearly dependent tests.
### Initial build of independent C files
This is quite clearly a linear scaling as with all initial builds,
although it demonstrates that fac has an unusually high constant
term, due presumably to hashing the information for all the input
files that are outside the repository (compiler, header files,
libraries, etc.).
### Re-build of independent C files
Here we delete all the output and rerun the build. It looks similar
to the initial build to me.
### Modifying a single independent C file
We modify a single C file. We would like this build to be $O(1)$, and
it looks pretty good, even though we need to check $O(N)$ input files
to see if they have been modified. Tup, of course, scales beautifully
here, although it doesn't catch up with ninja, make, or a blind fac at
less than about 10,000 files.
### Nochanges to the independent C files
Here with no changes, again we would dream of $O(1)$ time, but that
can only be acheived if you have a daemon running to tell you that no
files were touched. Or I suppose if you could use the modification
time of the directory to determine that no changes were made, but I
don't think that's correct. Ninja is the clear winner here.