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
|
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>A memoization routine for GNU Make functions — Luke Shumaker</title>
<link rel="stylesheet" href="assets/style.css">
<link rel="alternate" type="application/atom+xml" href="./index.atom" name="web log entries"/>
</head>
<body>
<header><a href="/">Luke Shumaker</a> » <a href=/blog>blog</a> » make-memoize</header>
<article>
<h1 id="a-memoization-routine-for-gnu-make-functions">A memoization routine for GNU Make functions</h1>
<p>I'm a big fan of <a href="https://www.gnu.org/software/make/">GNU Make</a>. 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 <a href="http://gmsl.sourceforge.net/">GMSL</a>.</p>
<p>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).</p>
<p>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 <code>memoize</code> function.</p>
<p>However, John's <code>memoize</code> has a couple short-comings that made it unsuitable for my needs.</p>
<ul>
<li>Only allows functions that take one argument.</li>
<li>Considers empty values to be unset; for my needs, an empty string is a valid value that should be cached.</li>
</ul>
<p>So, I implemented my own, more flexible memoization routine for Make.</p>
<pre><code># 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)))</code></pre>
<p>However, I later removed it from the Makefile, as I <a href="https://projects.parabola.nu/~lukeshu/maven-dist.git/commit/?id=fec5a7281b3824cb952aa0bb76bbbaa41eaafdf9">re-implemented</a> the bits that it memoized in a more efficient way, such that memoization was no longer needed, and the whole thing was faster.</p>
<p>Later, I realized that my memoized routine could have been improved by replacing <code>func</code> with <code>$0</code>, which would simplify how the final function is declared:</p>
<pre><code># 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)))</pre>
<p></code></p>
<p>Now, I'm pretty sure that should work, but I have only actually tested the first version.</p>
<h2 id="tldr">TL;DR</h2>
<p>Avoid doing things in Make that would make you lean on complex solutions like an external memoize function.</p>
<p>However, if you do end up needing a more flexible memoize routine, I wrote one that you can use.</p>
</article>
<footer>
<p>The content of this page is Copyright © 2014 <a href="mailto:lukeshu@sbcglobal.net">Luke Shumaker</a>.</p>
<p>This page is licensed under the <a href="http://www.wtfpl.net/txt/copying/">WTFPL-2</a> license.</p>
</footer>
</body>
</html>
|
