Makefile Optimization: $(eval) and macro caching

[article]

of these recursively-defined macros actually only ever have one value when used.  The long evaluation time for a complex recursively defined macro is a convenience for the Makefile author.

What would be really nice is a way to cache the macro values so that the flexibility of the =
style is preserved, but the macros are only evaluated once for speed.  Clearly, this would cause a little loss of flexibility: a macro couldn't take two different values (which is sometimes handy in a Makefile), but for most uses it would provide a significant speed up.

How much speed up?

Consider the following example Makefile.  It defines a variable C which is a long string (it's actually 1234567890 repeated 2,048 times with the alphabet repeated 2,048 plus spaces for a totally of 77,824 characters).  Here I used := so that I could build C's size quickly.  C
is designed to emulate the sort of long strings that get generated inside Makefiles (e.g. long lists of source files with paths).

The a variable FOO is defined that manipulates C using the built-in $(subst) function.  FOO emulates the sort of manipulation that occurs inside Makefiles.

Finally $(FOO) is evaluated 200 times to emulate the use of FOO in a small, but realistically sized Makefile.  The Makefile itself does nothing, there's a dummy, empty all rule at the end.

C := 1234567890 ABCDEFGHIJKLMNOPQRSTUVWXYZ

C += $C

C += $C

C += $C

C += $C

C += $C

C += $C

C += $C

C += $C

C += $C

C += $C

C += $C

FOO
= $(subst 9,NINE,$C)$(subst 8,EIGHT,$C)$(subst 7,SEVEN,$C)$(subst
6,SIX,$C)$(subst 5,FIVE,$C)$(subst 4,THREE,$C)$(subst 2,TWO,$C)$(subst
1,ONE,$C)

_DUMMY := $(FOO)

... repeated 200 times ...

.PHONY: all

all:

On my laptop, using GNU Make 3.81, this Makefile takes an average of 3.1s to run (I averaged ten runs using the time function in zsh).  That's a pretty long time spent repeatedly manipulating C and FOO.

Using the counter trick above it's possible to figure out how many times FOO and C are evaluated in this Makefile. FOO was evaluated 200 times, and C 1600 times.  It's amazing how fast these evaluations can add up.

But the value of C and FOO only actually need to be calculated once (since they don't change).   Altering the definition of FOO to use :=:

FOO
:= $(subst 9,NINE,$C)$(subst 8,EIGHT,$C)$(subst 7,SEVEN,$C)$(subst
6,SIX,$C)$(subst 5,FIVE,$C)$(subst 4,THREE,$C)$(subst 2,TWO,$C)$(subst
1,ONE,$C)

drops the run time to 1.8s with C evaluated 9 times and FOO just once.

But, of course, that requires using := with the problems described above.  Another alternative is the following simple caching scheme.  First, I define a function cache
which automatically caches a macro's value the first time it is
evaluated and retrieves it from the cache for each subsequent attempt
to retrieve it.

cache = $(if $(cached-$1),,$(eval cached-$1 := 1)$(eval cache-$1 := $($1)))$(cache-$1)

cache uses two macros to store the cached value of a macro (when caching macro A the cached value is stored in cache-A) and whether the macro has been cached (when caching macro A the 'has been cached flag' is cached-A.

First, it checks to see if the macro has been cached, if so the $(if) does nothing, if not the cached flag is set for that macro in the first $(eval) and then the value of the macro is expanded (notice the $($1) which gets the name of the macro and then gets its value) and cached.  Lastly, cache returns the value from cache.

To update the Makefile simply turn any reference to a macro into a call to the cache function.  For example, the Makefile above can be modified by changing all occurrences of

About the author

John Graham-Cumming's picture John Graham-Cumming

John Graham-Cumming is Co-Founder at Electric Cloud, Inc . Prior to joining Electric Cloud, John was a Venture Consultant with Accel Partners, VP of Internet Technology at Interwoven, Inc. (IWOV), VP of Engineering at Scriptics Corporation (acquired by Interwoven), and Chief Architect at Optimal Networks, Inc. John holds BA and MA degrees in Mathematics and Computation and a Doctorate in Computer Security from Oxford University. John is the creator of the highly acclaimed open source POPFile project. He also holds two patents in network analysis and has others pending.

AgileConnection is one of the growing communities of the TechWell network.

Featuring fresh, insightful stories, TechWell.com is the place to go for what is happening in software development and delivery.  Join the conversation now!

Upcoming Events

Nov 09
Nov 09
Apr 13
May 03