Makefile performance: pattern-specific variables

If you've been using GNU make for some time, you are probably familiar with both pattern rules and target-specific variables . You may even be familiar with the intersection of these features: pattern-specific variables . But you may not be aware of a subtle change in gmake 3.81 which affects the processing of pattern-specific variables with potentially disastrous performance consequences.

Pattern-specific variables are similar to target-specific variables in that they define a variable value that applies only in a particular context, but where target-specific variables apply to a single specific target, pattern-specific variables apply to all targets that match the given pattern. This gives us a way to get target-specific-variable-like behavior when using pattern rules. It also allows us a more flexible syntax for target-specific variables, even in the absence of pattern rules. A few examples should make everything clear. First, regular target-specific variables:

Here we have defined FLAGS with a default value at the global scope, and a custom value for target a . When you run this makefile with gmake, you'll see the value used for FLAGS is different for the two targets, as expected. Now, let's look at typical pattern-specific variable usage:

Again we have a custom value for FLAGS , but this time it applies to all targets matching the pattern .x . We could achieve the same behavior by using normal target-specific variables for each of the .x files of course, but the pattern-specific variable definition is more succinct and convenient, and it is more robust, since we need not hardcode the list of targets to which the new definition applies. Finally, let's look at pattern-specific variables without pattern rules:

With this example you can see that pattern-specific variables are used for each of the foo files , even though we have specified explicit rules for each of those files. That implies that gmake searches through the pattern-specific variables looking for variables that should apply for a given target independent of the search for a rule to build the target.

Suppose we modify our previous makefile like this:

What would you expect the value of FLAGS to be when building fooboo ? After all, both foo and boo match the target fooboo . In fact, there are two possibilities, both perfectly reasonable, both consistent with at least some other aspect of gmake behavior. The first possibility is that when building fooboo , FLAGS has the value base extra_foo_flags . That is, gmake applies the pattern-specific variables from the first , and only the first, pattern that matches the target. This is consistent with the way that gmake searches patterns to find a rule to build a target: as soon as one match is found, gmake stops searching. GNU make 3.80 uses the "first match" policy. The second possibility is that FLAGS has the value base extra_foo_flags extra_boo_flags when building fooboo . That is, gmake applies all the pattern-specific variables from all patterns that match the target, in the order the variables are defined in the makefile. This is a bit more intuitive, and is more consistent with the way variable definition in general works in gmake. GNU make 3.81 uses the "all matches" policy.

In both 3.80 and 3.81, the search for pattern-specific variables that apply to a given target involves a search of the pattern-specific variable definitions. The difference is that in 3.80, the search scales with the number of patterns that have pattern-specific variable definitions , and the search can stop as soon as a match is found. In gmake 3.81, the search search scales with the number of pattern-specific variable definitions , and the search must always inspect every single definition, even after the first match is found. To demonstrate the impact of this change, I did a series of tests. I created several makefiles like the following:

These makefiles each have a single all target with 10,000 prerequisites. I varied the number of pattern-specific variable definitions from 1,000 to 80,000 and timed how long it took to run the makefile in dry-run mode with both gmake 3.80 and 3.81. For kicks, I also included the runtimes for CloudBees Accelerator (emake) in 3.81 emulation mode. Here are the results: No doubt some of you are thinking that this is a toy example, so not particularly applicable to the real world. After all, nobody assigns the same variable over and over like that. That's an excellent point. Unfortunately, when I tried to create 20,000 unique pattern-specific variables, gmake 3.81 crashed after sucking up all the available RAM on my system. Oops! The bigger question is, who would ever have tens of thousands of pattern-specific variables? The answer is: people who have switched from a recursive build to a non-recursive build. In fact, I have seen a single makefile with over 180,000 pattern-specific variables, attached to just 18 distinct patterns. The point is, as crazy as it seems, builds of this scale do exist in the "real world".

To find the pattern-specific variable definitions in your makefiles, you can use the following command:

If you have lots of pattern-specific variables, what can you do to reduce the performance impact? A few ideas come to mind:

• Switch to gmake 3.80 and hope that a future release will address this problem.

• Convert your pattern-specific rules to explicit target-specific rules, perhaps using $(eval) to generate the new variable definitions dynamically so you don't have to type out every one by hand.

• Switch to a recursive build, which would allow you to partition your pattern-specific variables so that gmake only ends up searching the variables that are likely to apply to the targets referenced in a given makefile.

• Use CloudBees Accelerator, which emulates gmake 3.81 behavior but uses a more efficient algorithm in its implementation.

Update : Restored the results graph to the post, which mysteriously disappeared thanks to WordPress.

This article is one of several looking at different aspects of makefile performance. If you liked this article, you may enjoy the others in the series:

• Makefile performance: recursive make

• Makefile performance: $(shell)

• Makefile performance: pattern-specific variables (this post)

• Makefile performance: built-in rules

Continuous Delivery isn’t continuous if builds and tests take too long to complete. Learn more on how CloudBees Accelerator speeds up builds and tests by up to 20X, improving software time to market, infrastructure utilization and developer productivity.