From a48ae3d689ee2cfd999268893e3f70dc531d9ca7 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 21 Nov 2014 00:15:15 -0500 Subject: write make-memoize.md --- public/make-memoize.md | 86 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 86 insertions(+) create mode 100644 public/make-memoize.md diff --git a/public/make-memoize.md b/public/make-memoize.md new file mode 100644 index 0000000..03bb2dc --- /dev/null +++ b/public/make-memoize.md @@ -0,0 +1,86 @@ +A memoization routine for GNU Make functions +============================================ +--- +date: "2014-11-20" +license: WTFPL-2 +--- + +I'm a big fan of [GNU Make][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][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][reimplement] 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. + +[make]: https://www.gnu.org/software/make/ +[gmsl]: http://gmsl.sourceforge.net/ +[reimplement]: https://projects.parabola.nu/~lukeshu/maven-dist.git/commit/?id=fec5a7281b3824cb952aa0bb76bbbaa41eaafdf9 -- cgit v1.2.3