# Benchmarks

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.