summaryrefslogtreecommitdiff
path: root/public
diff options
context:
space:
mode:
authorLuke Shumaker <lukeshu@sbcglobal.net>2014-11-21 00:15:15 -0500
committerLuke Shumaker <lukeshu@sbcglobal.net>2014-11-21 00:15:15 -0500
commita48ae3d689ee2cfd999268893e3f70dc531d9ca7 (patch)
tree51e490f1fe88228739d0bfe6fc6e38ef7c03526b /public
parenta1d94a8a42c4755514eb478d513cd24c54b276a1 (diff)
write make-memoize.md
Diffstat (limited to 'public')
-rw-r--r--public/make-memoize.md86
1 files changed, 86 insertions, 0 deletions
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):
+ # `_<var>NAME</var>_main` and `_<var>NAME</var>_hash`. Now, `_<var>NAME</var>_main` is the function getting
+ # memoized, and _<var>NAME</var>_hash is a function that hashes the function arguments
+ # into a string suitable for a variable name.
+ #
+ # Then, define the final function like:
+ #
+ # <var>NAME</var> = $(foreach func,<var>NAME</var>,$(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:
+ #
+ # _<var>NAME</var>_main = <var>your main function to be memoized</var>
+ # _<var>NAME</var>_hash = <var>your hash function for parameters</var>
+ # <var>NAME</var> = $(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