Recursive Make Is A Time-Waster

Now you’ve arranged to divide your project into libraries, how do you go about compiling them?

Clearly you want to be able to do the whole thing in one go: to do otherwise would be to fail the Joel test. And you want all the dependencies to be checked every time: there’s no bug harder to find than one that no longer actually exists in the source you’re looking at. (And stale objects, not updated following a header change, can lead to ODR violations: in other words, to random spookiness and borkage that the compiler and linker aren’t required to warn you about, and in many cases can’t even theoretically do so.)

GNU Automake is one answer to the problem, and makefiles in the same spirit as the ones it generates are popular even in projects that don’t use Automake. Such makefiles express inter-module dependencies, such as that of an application on a library, by recursively invoking make in the library directory before invoking it again in the application directory.

For a variety of reasons, documented once and for all in the famous paper Recursive make Considered Harmful, this is a bad idea. The paper suggests that for some systems, it’s even a bad idea for correctness reasons — that incorrect builds with inadequately-followed dependencies can result. But the example given is that of a system whose module dependencies can’t be serialised; this naturally means Automake’s sequential run over the sub-Makefiles can’t do the Right Thing. However, if the module dependencies can’t be serialised, that means there’s a cycle and they don’t form a true hierarchy; that’s a bad situation for more reasons than just Automake’s — bad for reusability, bad for unit-testability, and bad because it reveals that the system designers haven’t really thought through what the rôles of the modules are.

So if that doesn’t apply to you, if your modules are properly factored into a neat hierarchy, does that mean there’s less incentive to ditch a recursive-make scheme and take the time to write a non-recursive one? Less, perhaps, but decidedly not none — because there are substantial performance benefits from whole-project makefiles on modern systems.

This effect is, to be fair, mentioned in Recursive make Considered Harmful (7.1), but the author didn’t draw it out on pretty graphs, nor quantify the improvements, so there is scope for it to be better-documented.

Suppose your project has ten components (nine libraries and the application, say), each with between four and twenty source files. These source files won’t, naturally, all take exactly the same length of time to compile — in fact, typically there’ll be quite a wide range of compilation times, especially if only certain files include certain rather profligate library headers. And further suppose that the machine you’re compiling on has eight CPU cores or threads (such machines are desktop-class these days), so you use make -j8.

If your makefiles are like Automake’s, what happens is that make will make the first library using up to eight CPUs, then, once that’s done, make the second library using up to eight CPUs, and so on until it’s done all of them in the serialised order you used in the top-level Makefile. Which is correct, but it’s not efficient, because make needlessly serialises the entire of each library build against the entire of the next one, when typically a library’s components will each depend on only some of the previous one’s targets.

In graphical form, your CPU utilisation would look like the following diagram, where time runs from left to right, each horizontal row represents a different CPU, and blocks of the same colour belong to the same library; the top half of the diagram shows CPU utilisation during a recursive-make-driven recompilation, and the bottom half the same recompilation done with a whole-project Makefile.

click for full-size

Using one Makefile has allowed make -j8 to keep all eight CPUs busy the whole time — as, whenever a CPU comes free, any pending work from anywhere else in the project can be scheduled on it. By contrast, the top half of the diagram has lots of whitespace, where all the CPUs must wait each time until the last one in that library has finished.

In this example, the build takes scarcely 70% of the time a recursive build would do. If you have more cores, perhaps in a multi-machine build farm, the benefit goes up: building on four cores sees a reeduction only to 88%, but 12 cores sees the whole-project build take just 59% as long as the recursive version, and on 16 cores the time is better than halved. If, in the limit, you work for Dr. Evil, your entire company is basically one big compute surface and you can use “make -j one-meelion”, then the improvement factor is essentially the same as the number of libraries — in this case, 10x, though in practice if you went down that route you’d find communication overheads starting to bite into your scalability.

Type Erasure, boost::mutex, And The617

The boost::mutex class is certainly not considered harmful. It’s jolly good, especially the way it, and its companion boost::condition, work properly on Win32. But it doesn’t half include a lot of header files to obtain all that jolly goodness.

Let’s get GCC to tell us what header files it includes. To do this, we need GCC’s dependency generation features, the ones normally used for generating Makefile fragments listing all the files a translation unit depends on.

$ echo "#include <boost/thread/mutex.hpp>" \
      | g++ -xc++ -E - -MP -M | grep ^/usr | sort
...long list...

OK, that’s indeed quite a lot of headers. How many exactly? (using GCC 4.3.3, amd64-linux, Boost 1.39.0)

$ echo "#include <boost/thread/mutex.hpp>" \
      | g++ -xc++ -E - -MP -M | grep ^/usr | sort | wc -l
618

Yes, a source file that includes nothing but <boost/thread/mutex.hpp> has actually also read six hundred and seventeen other headers by the time it’s done.

Now I’d hate to be one of those bloggers who does nothing but sit around and grouse about the people who are actually doing useful work. But I humbly submit that having to include 618 C++ headers just to get hold of a mutex class, is, in an objective sense, rather a lot.

Really what’s wanted is one of the “complete insulation” or type-erasure techniques from Lakos section 6.4, so that instead of the situation on the left — where every file in the project which needs a mutex, includes the Boost header and its 617 dependencies — we get the situation on the right, where only the encapsulating file needs to know the details, and everyone else can just include the simple leaf header my_mutex.h.

The problem is, every encapsulation technique discussed by Lakos has an inevitable cost in efficiency. Whichever way you slice it — whether you use a mutex protocol class plus a factory, or whether you use the handle/body or pimpl pattern — you tend to end up needing to call new and delete, not just every time you create or destroy a mutex, but every time you create or destroy a mutex scoped-lock object. Especially for rarely-contended locks, that overhead can easily swamp the actual implementation time.

The issue is, that to end up with a boost::mutex, client code must either construct one itself — depending on boost::mutex “in size” is Lakos’s term — or call other code which hands one back, which latter scheme necessarily requires an allocation.

So how can we solve this impasse? How can we depend on boost::mutex “in size”, without depending on all its headers?

Well, we can cheat. We can populate my_mutex.h with classes whose objects are the same size as boost::mutexes — and which, within the file my_mutex.cpp, are boost::mutexes — but whose actual type is invisible to other clients of my_mutex.h. The idea is to behave a bit like this:

class Mutex
{
    char m_data[sizeof(boost::mutex)];

public:
    Mutex()
    {
        new(m_data) boost::mutex;
    }
    ~Mutex()
    {
        ((boost::mutex*)m_data)->~mutex();
    }
};

though of course that doesn’t yet help as-is, as you still need to include the 617 to get sizeof(boost::mutex) to compile.

To eliminate the dependencies, you need to know sizeof(boost::mutex) ahead of time. Probably the best way to do this, is to get your configury to work it out, by adding lines like these to your configure.ac:

AC_LANG_PUSH([C++])
AC_CHECK_SIZEOF([boost::mutex],, [[#include <boost/thread/mutex.hpp>]])
AC_CHECK_SIZEOF([boost::condition],, [[#include <boost/thread/condition.hpp>]])
AC_CHECK_SIZEOF([boost::mutex::scoped_lock],, [[#include <boost/thread/mutex.hpp>]])
AC_LANG_POP

which will leave you with lines like this in your config.h:

#define SIZEOF_BOOST__CONDITION 88
#define SIZEOF_BOOST__MUTEX 40
#define SIZEOF_BOOST__MUTEX__SCOPED_LOCK 16

giving you exactly what you need to write my_mutex.h. (One day when you want to see something deliciously evil, go and look at the way Autoconf determines such size information when cross-compiling, without depending on any particular compiler or linker.) The result looks like this:

/* my_mutex.h */
#include "config.h"

class Mutex
{
    char m_data[SIZEOF_BOOST__MUTEX];

public:
    Mutex();
    ~Mutex();
};


/* my_mutex.cpp */
#include "my_mutex.h"
#include <boost/thread/mutex.hpp>

Mutex::Mutex()
{
    new(m_data) boost::mutex;
}

Mutex::~Mutex()
{
    ((boost::mutex*)m_data)->~mutex();
}

which is indeed good enough to free client code from the burden of the 617.

But if you’re doing this wrapping for more than one class — Chorale wanted at least boost::mutex, boost::mutex::scoped_lock, and boost::condition — you start to realise you’re writing the same thing many times over, and that it really ought to be wrapped up in a template. (An attempt is also made to avoid alignment issues, a worry which might already have been nagging at you after the above snippets; an assertion checks that the configury got the right answer for the size.) Here it is:

template <class T>
struct WrappedType;

/** Wrap up a type so that even clients who depend on it in size,
 * don't have to see its declaration.
 */
template <class T, unsigned int sz>
class Wrapper
{
    union {
        char m_data[sz];
        void *m_align;
    };

    /** Use a nested class, rather than using WrappedType<T>::type
     * directly, so that we can be sure that its destructor is called
     * "~Wrapped" -- if T1 is a typedef-name, its destructor won't be
     * called "~T1".
     */
    class Wrapped: public WrappedType<T>::type
    {
    public:
        Wrapped() {}

        template <class Arg>
        explicit Wrapped(Arg& arg) : WrappedType<T>::type(arg) {}
    };

public:
    Wrapper()
    {
        BOOST_STATIC_ASSERT(sizeof(Wrapped) == sz);
        new (m_data) Wrapped;
    }

    template <class Arg>
    explicit Wrapper(Arg& arg)
    {
        BOOST_STATIC_ASSERT(sizeof(Wrapped) == sz);
        new (m_data) Wrapped(arg);
    }

    ~Wrapper()
    {
        ((Wrapped*)m_data)->~Wrapped();
    }

    /** Calls to Unwrap() will only compile following a definition of
     * WrappedType<T> -- not in client code.
     */
    Wrapped& Unwrap() { return *(Wrapped*)m_data; }
};

Armed with this, my_mutex.h can be very straightforward:

#include "config.h"
#include "wrapper.h"

/** Wrap a boost::mutex so we don't include so very many headers.
 */
class Mutex: public Wrapper<Mutex, SIZEOF_BOOST__MUTEX>
{
public:
    Mutex();
    ~Mutex();

    class Lock: public Wrapper<Lock, SIZEOF_BOOST__MUTEX__SCOPED_LOCK>
    {
    public:
        Lock(Mutex&);
        ~Lock();
    };
};

class Condition: public Wrapper<Condition, SIZEOF_BOOST__CONDITION>
{
public:
    Condition();
    ~Condition();

    bool Wait(Mutex::Lock&, unsigned int sec);

    void NotifyOne();
    void NotifyAll();
};

and my_mutex.cpp not much less straightforward; note that WrappedType<T> is used like a traits class, in that the intended wrapped type is “revealed” by specialising WrappedType for the particular wrapper type — it’s only following such a specialisation, that the constructor, destructor, or Unwrap() calls will compile:

#include "my_mutex.h"
#include <boost/thread/mutex.hpp>
#include <boost/thread/condition.hpp>

template<>
struct WrappedType<Mutex>
{
    typedef boost::mutex type;
};

Mutex::Mutex()
{
}

Mutex::~Mutex()
{
}

template<>
struct WrappedType<Mutex::Lock>
{
    typedef boost::mutex::scoped_lock type;
};

Mutex::Lock::Lock(Mutex& mutex)
    : Wrapper<Lock,SIZEOF_BOOST__MUTEX__SCOPED_LOCK>(mutex.Unwrap())
{
}

Mutex::Lock::~Lock()
{
}

template<>
struct WrappedType<Condition>
{
    typedef boost::condition type;
};

Condition::Condition()
{
}

Condition::~Condition()
{
}

bool Condition::Wait(Mutex::Lock& lock, unsigned int sec)
{
    return Unwrap().timed_wait(lock.Unwrap(), boost::posix_time::seconds(sec));
}

void Condition::NotifyAll()
{
    Unwrap().notify_all();
}

void Condition::NotifyOne()
{
    Unwrap().notify_one();
}

So this technique is neat if a bit icky (with the casting and the explicit size-checking). Is it worthwhile? For Chorale, the answer was certainly “yes”. Chorale is vigorously multi-threaded, and many parts of the system use mutexes. Using a script a bit like the GCC-based dependency counter from the very top of this post, it turns out that Chorale’s 250ish source files and 250ish headers, had between them nearly 240,000 dependencies. Wrapping up just boost::mutex and boost::condition reduced that number to 115,000 — meaning that more than half of all header files compiled while compile the whole of Chorale, a fairly large and complex program, get compiled solely to satisfy the dependencies of boost::mutex. This startling figure is also borne out by the total time taken to compile (with a cold pagecache):

Before wrapping		After wrapping
real 4m0.304s user 10m33.296s sys 1m38.870s		real 2m39.516s user 6m10.523s sys 1m9.452s

...a 42% improvement. It is just possible that there’s a run-time efficiency impact of this wrapping, as the mutex operations now all get inlined into my_mutex.cpp and not directly into the client code. However, as is the way with these things, it’s really just as likely that this gives a performance improvement — some of these Boost calls inline a lot of code, especially under Win32.

Autoconf, #ifdef, and #if

The standard macros available in GNU Autoconf for “checking for...” C/C++ functions and header files, AC_CHECK_FUNCS and AC_CHECK_HEADERS, have a couple of things going for them: their syntax and semantics essentially haven’t changed for years, perhaps ever, and everyone — well, everyone who writes configure scripts, which if it isn’t you should be a big hint as to how much you’ll get from this blog — already knows how they work. Which is to say, they end up embedding in your generating header, typically config.h, lines which look like this:

/* Define to 1 if you have the <linux/inotify.h> header file. */
/* #undef HAVE_LINUX_INOTIFY_H */

/* Define to 1 if you have the `localtime_r' function. */
#define HAVE_LOCALTIME_R 1

That’s all you need to start making your code conditional on which facilities are available:

#include "config.h"
    [...]
#ifdef HAVE_LOCALTIME_R
    localtime_r(&start, &stm);
#else
    // This code isn't thread-safe and could
    // get the wrong time -- but the result
    // would just be an odd-looking filename, not 
    // incorrect operation, so we live with it
    stm = *localtime(&start);
#endif

But there’s a problem. In fact, there’re two problems. One of the best features of C and C++, one of the few things that lets the old guard lord it over today’s arriviste scripting languages, the pythons and the rubies, is that almost everything is checked at compile-time. If you mistype an identifier, say localtime_r, as localtimer or whatever else, your code won’t compile, even if it’s on a rarely- or never-used path through the code. Unless you’re unlucky enough to hit the exact name of another existing identifier (and even then the type system may save you, unless you’re unlucky again), your mistyping is caught right there as you’re writing the code, not in QA — or, horrors, in production.

The same can’t be said, though, of identifiers in #ifdef. It’s perfectly valid to use a name there that doesn’t exist — nor could it be otherwise, as there’s nothing else it does except distinguish existent from non-existent names. So if you fat-finger it — HAVE_LOCALTIMER, maybe — the code compiles without even a warning, and just does the wrong thing, or at least the less-optimal thing. Even into production.

The second problem is config.h itself: if you forget to #include it, again your code compiles without a warning, but all your features get turned off! There are ways around this, such as by having a little script that checks your sources using grep, or by using GCC’s -include command-line option to force the inclusion, but none is ideal. (For instance, the latter gets dependencies wrong if config.h changes.)

Really what you want is warnings at compile-time if you mistype the identifier, or forget the header. In order to do this, you’re going to need to use #if rather than #ifdef; in other words, you’re going to need a config.h with lines like this:

/* Define to 1 if you have <linux/inotify.h>, or to 0 if you don't. */
#define HAVE_LINUX_INOTIFY_H 0

/* Define to 1 if you have localtime_r(), or to 0 if you don't. */
#define HAVE_LOCALTIME_R 1

And to do that, you’re going to have to use custom Autoconf macros instead of the standard AC_CHECK_ ones. Which is the point at which most people would give up, as Autoconf macros expand into shell code but are themselves written in the macro language m4, whose syntax can be charitably described as quixotic, and is regularly described using rather shorter and more Anglo-Saxon words than that. So here, I’ve done it for you, have these ones:

AC_DEFUN([PDH_CHECK_HEADER], [
AC_MSG_CHECKING([for <$1>])
AC_COMPILE_IFELSE([AC_LANG_PROGRAM([[#include <$1>
]])],
          [AC_MSG_RESULT([yes]); pdh_haveit=1; pdh_yesno="yes"],
          [AC_MSG_RESULT([no]);  pdh_haveit=0; pdh_yesno="no"])
AC_DEFINE_UNQUOTED(AS_TR_CPP([HAVE_$1]), $pdh_haveit,
          [Define to 1 if you have <$1>, or to 0 if you don't.])
AS_TR_SH([ac_cv_header_$1])=$pdh_yesno
])

AC_DEFUN([PDH_CHECK_HEADERS], [
m4_foreach_w([pdh_header], $1, [PDH_CHECK_HEADER(pdh_header)])
])

AC_DEFUN([PDH_CHECK_FUNC], [
AC_MSG_CHECKING([for $1()])
AC_LINK_IFELSE([AC_LANG_PROGRAM([], [[(void)$1();]])],
        [AC_MSG_RESULT([yes]); pdh_haveit=1; pdh_yesno="yes"],
        [AC_MSG_RESULT([no]);  pdh_haveit=0; pdh_yesno="no"])
AC_DEFINE_UNQUOTED(AS_TR_CPP([HAVE_$1]), $pdh_haveit,
        [Define to 1 if you have $1(), or to 0 if you don't.])
AS_TR_SH([ac_cv_func_$1])=$pdh_yesno
])

AC_DEFUN([PDH_CHECK_FUNCS], [
m4_foreach_w([pdh_func], $1, [PDH_CHECK_FUNC(pdh_func)])
])

That bracketfest defines macros PDH_CHECK_HEADERS and PDH_CHECK_FUNCS which do the same job as the standard AC_CHECK_HEADERS and AC_CHECK_FUNCS...

PDH_CHECK_HEADERS([io.h poll.h errno.h fcntl.h sched.h net/if.h stdint.h stdlib.h unistd.h shlwapi.h pthread.h ws2tcpip.h sys/poll.h sys/time.h sys/types.h sys/socket.h sys/syslog.h netinet/in.h netinet/tcp.h sys/inotify.h sys/resource.h linux/unistd.h linux/inotify.h linux/dvb/dmx.h linux/dvb/frontend.h])

PDH_CHECK_FUNCS([mkstemp localtime_r setpriority getaddrinfo inotify_init gettimeofday gethostbyname_r sync_file_range sched_setscheduler])

...but leave you with identifiers in config.h that you can use #if on rather than #ifdef, so you can enjoy compile-time warnings if you get any of them wrong.

Ah, except you can’t just yet, because there’s one final wrinkle. The C and C++ standards allow undefined identifiers in #if just as in #ifdef — they don’t expand to nothing, giving the syntax errors you’d initially hope for, but are defined as evaluating to zero. So, back to square one. Except, fortunately, the authors of GCC appear to be as sceptical about the usefulness of that preprocessor feature as I am, and they provide an optional warning which can be emitted whenever the preprocessor is obliged to evaluate an undefined identifier as zero: -Wundef. So, if you use the configury macros above, and add -Wundef to your GCC command-lines, you can at last get the compiler to point it out to you when you mistype your configure macros.

When I wrote these new macros, I did have a nagging feeling that it was all just NIH syndrome, and that it was silly makework to be rewriting core bits of Autoconf for this marginal benefit. But once I’d done it, re-compiling Chorale showed up two warnings, both places where a mistyped identifier was causing real and otherwise hard-to-find problems. So I felt retrospectively justified in my tinkering. The moral of the story: if you’ve fixed a bug, you’ve done a day’s work; but if you’ve fixed a bug by ensuring that it, and its whole class of fellow bugs, can never happen undetected again — then, you’ve done a good day’s work.