A memoization routine for GNU Make functions
I’m a big fan of GNU Make. I’m pretty knowledgeable about it, and was pretty active on the help-make mailing list for a while. Something that many experienced make-ers know of is John Graham-Cumming’s “GNU Make Standard Library”, or GMSL.
I don’t like to use it, as I’m capable of defining macros myself as I need them instead of pulling in a 3rd party dependency (and generally like to stay away from the kind of Makefile that would lean heavily on something like GMSL).
However, one really neat thing that GMSL offers is a way to memoize
expensive functions (such as those that shell out). I was considering
pulling in GMSL for one of my projects, almost just for the
memoize
function.
However, John’s memoize
has a couple short-comings that
made it unsuitable for my needs.
- Only allows functions that take one argument.
- Considers empty values to be unset; for my needs, an empty string is a valid value that should be cached.
So, I implemented my own, more flexible memoization routine for Make.
# This definition of `rest` is equivalent to that in GMSL
rest = $(wordlist 2,$(words $1),$1)
# How to use: Define 2 variables (the type you would pass to $(call):
# `_NAME_main` and `_NAME_hash`. Now, `_NAME_main` is the function getting
# memoized, and _NAME_hash is a function that hashes the function arguments
# into a string suitable for a variable name.
#
# Then, define the final function like:
#
# NAME = $(foreach func,NAME,$(memoized))
_main = $(_$(func)_main)
_hash = __memoized_$(_$(func)_hash)
memoized = $(if $($(_hash)),,$(eval $(_hash) := _ $(_main)))$(call rest,$($(_hash)))
However, I later removed it from the Makefile, as I re-implemented the bits that it memoized in a more efficient way, such that memoization was no longer needed, and the whole thing was faster.
Later, I realized that my memoized routine could have been improved
by replacing func
with $0
, which would
simplify how the final function is declared:
# This definition of `rest` is equivalent to that in GMSL
rest = $(wordlist 2,$(words $1),$1)
# How to use:
#
# _NAME_main = your main function to be memoized
# _NAME_hash = your hash function for parameters
# NAME = $(memoized)
#
# The output of your hash function should be a string following
# the same rules that variable names follow.
_main = $(_$0_main)
_hash = __memoized_$(_$0_hash)
memoized = $(if $($(_hash)),,$(eval $(_hash) := _ $(_main)))$(call rest,$($(_hash)))
Now, I’m pretty sure that should work, but I have only actually tested the first version.
TL;DR
Avoid doing things in Make that would make you lean on complex solutions like an external memoize function.
However, if you do end up needing a more flexible memoize routine, I wrote one that you can use.