summaryrefslogtreecommitdiff
path: root/public/make-memoize.md
blob: 03bb2dcbfedf390d886564180785b510279c4ca5 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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