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.

Four Quarters Of The Codebase

As a software project grows, eventually it becomes unwieldy to keep the entire source in one single gigantic folder: you’ll need to split it up. Canonically, and indeed quite correctly, the first idea most architects then have is to split the source into a main program plus one or more libraries that provide ancillary services.

Once that’s done, everyone on the project who sits down to write some new code, will have to think at least for a moment about where to put the source file. The answer, of course, is that the new code should go in the main program if it’s fairly specific to the current project (or if it depends on code that’s already in there), and into the library otherwise. The “force of gravity” — developers’ sense of where code should go unless there’s good reason otherwise — should be in the direction of pulling functionality over into the generic code.

Sometimes this decision seems harder than it should be: if that’s the case, what’s often going on is that the functionality in question should really be split up — with a generic part in the library, and the specific use this project makes of it in the main program. In this way, source code organisation can act as a forcing function for good design.

If that’s so useful, can we get extra design-forcing out of how we organise the source? One issue that often throws a spanner in the works of software designs whose creators didn’t originally bear it in mind, is portability between software platforms. It would be decidedly helpful if the source code organisation, and/or the system architecture it (one hopes) reflects, could help prevent platform specialists from unthinkingly tying code to a particular platform when in fact it’ll be needed more widely in future.

So instead of just application versus library, it’s helpful to organise the codebase so that a developer sitting down to write new code, will have to choose between four different places to put it:

Application-specific, platform-specific	Library code, platform-specific
Application-specific, platform-agnostic	Library code, platform-agnostic

This means that, if you’re writing an application that you’re targetting at, say, both Iphone and Windows, or both desktop and embedded, then the actual application logic needs to go in the south-west corner, where implementations on any platform can use it; user-interface code mostly goes in the north-east, where other applications wanting similar UI components can use it; and only the minimum of code necessary to wire the two together goes in the north-west.

The force of gravity in this diagram acts towards the south and the east: if you can turn code from a Win32 application into generic Win32 components, or into a portable implementation of the logic, that’s a design improvement. If you can split the code up, even split a single class up, along those lines, that’s an improvement too. And by forcing developers to make the four-way choice before they write a source file, you’re helping everyone in the team to think about these issues and to factor the code in the best way as it’s first written. Fostering a feeling of “design guilt”, in yourself or others, when placing functionality further north or west than it belongs, gives everyone an easily-grasped metric for well-factored designs.

Really this just another way of thinking about the model-view-controller pattern; the mapping is straightforward, except that MVC doesn’t have a word for the fourth quarter, libraries which are assumed to be at a lower level than the components MVC deals with:

Controllers	Views
Models	(Libraries)

but, even so, embodying MVC in the source layout itself means that its issues get thought about earlier in the software process.

Now naturally, any real codebase above a certain size won’t consist of just “the” application and “the” library. There’ll be a whole collection of libraries, and perhaps of applications too, arranged in a dependency graph — hopefully, for reasons Lakos expounds, a graph which forms a non-cyclic hierarchy. But it should be possible to partition this graph into (up to) four parts, matching the four quarters of the codebase, and with all dependency arrows pointing southwards, eastwards, or south-eastwards. No view or model should depend on a controller; no platform-agnostic library should depend on any view, model or controller. Again, these are truisms of MVC design, but thinking about them in their four quarters gives an easy visual way of thinking about and discussing the issues.

Incidentally, my own Chorale codebase currently (as of v0.15) fails this test, or at least gets a technical pass only: it doesn’t have any platform-specific library code or directories, as all that code is rather bogusly stuffed in the application-specific, platform-specific directories. (Some classes are, in fact, platform-specific library classes, but the split isn’t enforced in the source organisation, either by libraries or by directories.)