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 101

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.

What happens when multiple patterns match my 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.

Performance Comparison

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 ElectricAccelerator (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”.

Are you at risk?

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 ElectricAccelerator, 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:


Build Acceleration and Continuous Delivery

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

Eric Melski

Eric Melski was part of the team that founded Electric Cloud and is now Chief Architect. Before Electric Cloud, he was a Software Engineer at Scriptics, Inc. and Interwoven. He holds a BS in Computer Science from the University of Wisconsin. Eric also writes about software development at http://blog.melski.net/.

Share this:

4 Responses to “Makefile performance: pattern-specific variables”

  1. Laurent says:

    You say “here are the results” but you forgot to publish them. Can you edit your post please.

    Thanks

  2. Eric Melski says:

    Sorry about the mixup with the results graph — WordPress sometimes decides to zap images from my posts for no apparent reason.

  3. Richard Sharpe says:

    Hmmm, I seem to have an interesting problem as well:

    $(INSTALL_libs:%=$(OUTPUT)/%) :
    :cd $(MY); (printenv; ./build/mkcomp all)

    Now, INSTALL_libs is some 20 or so library names. Make is running the command for each library name. It should be running the command only once.

  4. Eric Melski says:

    Richard,

    Unfortunately in GNU Make syntax this:

    target1 target2 target3: ; @echo $@

    … is identical in meaning to this:

    target1: ; @echo $@
    target2: ; @echo $@
    target3: ; @echo $@

    That is, it creates multiple distinct rules that happen to have identical contents for the rule bodies. It does not create a single rule with multiple outputs, as many people naturally assume. The only way to get a single rule with multiple outputs in GNU make is with a pattern-rule, such as this:

    %.c %.h: %.y ; @echo Building two things from one!

    Don’t be fooled by the %’s in your example! At first glance those give the impression that you have a pattern rule, but you do not. The %’s in your example are in the context of a simple string substitution command, which is not related to pattern-rules in any way, except that the both use % as a wildcard.

    One approach that might work for you is to define a pseudo-target that actually does the work, then make the real targets depend on that, but not do any work themselves. For example:

    target1 target2 target3: pseudo
    pseudo: ; @echo Do the work once!

    Hope that helps.

Leave a Reply

Subscribe via RSS
Click here to subscribe to the Electric Cloud Blog via RSS

Subscribe to Blog via Email
Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Continuous Discussions Online Panel

Next Episode: Deployment Automation
Dec. 22, 10am PST


Add to your calendar »

Using CMake?
Accelerate Your Builds for Free!

Read the technical document on CMake Build Acceleration
Read Now »
banner_continuous-integration-at-scale

banner_huddle_free-build-acceleration