Saturday, August 8, 2009

Benchmarking build systems

I've long been on a quest to find a replacement for "make" for building projects. I will be writing more about this, but for now I would like to report some preliminary results from benchmarking some build systems, including a newcomer to the scene.

The benchmarking effort was inspired by by discovery of a couple of excellent blog posts done by Noel Llopis in 2005. I especially wanted to extend his results to cover non-recursive use of make (PDF) and fabricate. Happily, Noel published the scripts that he used for his work, so I downloaded them and added two new benchmarks.

There are many other build tools (and build tool advocates!) so I made a public git repository to hold the benchmarking tools. I welcome patches containing benchmarks for other build tools! Personally, I would be very interested to see benchmarks of waf, which claims to be much faster than scons. [I have added data for waf to the results table below.]

Here I would like to report some preliminary results. Briefly, the test "project" consists of 50 libraries; each library consists of 100 C++ header files and 100 C++ source files; each header+source defines one trivial class; and the source files each include 15 other headers from the same library plus 5 headers from other, earlier-numbered libraries. The interlibrary dependencies only go one way, making it easy to define a self-consistent build order. Altogether the project includes about 10000 files, meaning that it is quite large but not enormous.

For comparison, I repeated some of the blog author's original measurements on my computer (a Linux notebook), plus a few new ones. I only bothered with the "full" build (build everything from scratch) and the global "do-nothing" build (run the build again when there is nothing to do). The builds that I added are as follows:

A "make_nonrecursive" build that uses "gcc -MM" to generate include-file dependencies for each file, and includes all of the dependency files and the library-wide Makefiles into a single project-wide Makefile that knows about all of the dependencies. See "Recursive Make Considered Harmful" (PDF) for more information about this style of Makefile.

I added two fabricate benchmarks, one using atimes_runner and one using strace_runner. In both cases the build file does the obvious loop-over-libraries, loop-over-sourcefiles and invokes g++ using once for each file. The tests use fabricate trunk r21.

Here are my results:

Build systemFull compilationDo-nothing build
make (recursively invoked)194 s3.7 s
make_nonrecursive319 s1.7 s
scons312 s52 s
waf207 s2.7 s
fabricate, using atimes_runner4245 s17.7 s
fabricate, using strace_runner251 s18.9 s
fabricate, using strace_runner and mtime_hasher328 s352 s [1]

[1] I.e., this combination didn't work; it rebuilt everything.


make_nonrecursive is slower than recursive make for the full build, but this is probably mostly because make_recursive uses "gcc -MM" to generate the dependencies rather than "makedepend" as used by the recursive make. This is an implementation difference that could be changed. For the do-nothing build, make_nonrecursive is faster.

fabricate with the atimes_runner is so excruciatingly slow at doing a full build that it cannot seriously be considered for a project of this size. In retrospect, it is clear that it has to be slow for large projects, because before and after every command it has to monkey around with the atimes of every single file in the project. Thus the time for building a project with N files goes something like O(N2).

A full build using fabricate and strace_runner is much better, almost as fast as make.

For do-nothing builds, fabricate is considerably slower than make, though not as slow as scons. A do-nothing build is the extreme case of an incremental build, which is the bread-and-butter of daily development. So the fabricate project should definitely invest time to speed up do-nothing builds.

For some reason, fabricate with strace_runner and mtime_hasher didn't work for me. The do-nothing build in fact rebuilt everything, making it even slower than the corresponding full build.

EDIT, 2009-09-15: Reformatted results in tabular form, and added numbers for waf.


Anonymous said...

I recently came accross your blog and have been reading along. I thought I would leave my first comment. I dont know what to say except that I have enjoyed reading. Nice blog. I will keep visiting this blog very often.


bohan said...
This comment has been removed by the author.
bohan said...

You may be interested to see more numbers there:

bohan said...

This tool seem to have a lot in common with yours:

Michael Haggerty said...

bohan: Thanks for your comments. Just to be clear, none of these build systems was developed by me. My goal was to find out whether the approach used by fabricate could possibly be efficient enough to compete with other build systems.

Thanks also for the link to your own benchmarks page. I had come across your data before and found it very useful.

Anatol Pomozov said...

If you are interested in a fast incremental build you should definitely look at the Tup build tool. Here is its benchmark with Make