This message is to announce the the second release (first non-beta) of a
facility for automatic memoization in Common LISP. Automatic memoization is a
technique by which an existing function can be transformed into one
that "remembers" previous arguments and their associated results,
yielding large performance gains for certain types of applications.
This code was inspired by the section on automatic memoization in Peter
Norvig's _Paradigms of AI Programming_ (which in turn was inspired by
Abelson and Sussman's _Structure and Interpretation of Computer Programs_).
The idea of this facility is to extend those ideas into what is needed for a
practical facility for use in a large program. As such, it adds many facilities
for bookkeeping, timing, evaluating the timing advantages memoization
provides, saving hash tables to disk for automatic reuse in a later
session, etc. This utility has been used over the last two years on the
[D]ARPA Signature Management System, resulting in performance improvements
of 10-20 fold in several key modules.
These utilities, along with an overview of memoization and its applications,
are described in more detail below. The code itself is available via
anonymous FTP from ftp.cs.umbc.edu (130.85.100.53), in /pub/Memoization.
This archive also includes a PostScript version of a paper on the subject
to appear in the Sixth International Symposium on AI, Monterrey Mexico,
September 1993. If you are interested but do not have FTP access,
I can send a uuencoded tar file via email.
The code is freely available for unrestricted use and modification.
I am quite interested in suggestions, comments, corrections, and
experiences of anyone who tries out the package.
Marty Hall
The Johns Hopkins Applied Physics Lab
Room 7-38
Johns Hopkins Road
Laurel, MD 20723
····@aplcenmp.apl.jhu.edu
(410) 792-6000 x3440
=================== Lengthy Description Follows =============================
.../Memoization1.0/Memoization-Overview.text
Anonymous FTP from ftp.cs.umbc.edu (130.85.100.53) in /pub/Memoization
This file contains the following sections:
(I) What is Automatic Memoization
(II) Application Areas
(III) Potential Pitfalls
(IV) Main User Functions
1991-1993 Marty Hall
····@aplcenmp.apl.jhu.edu, (410) 792-6000 x3440
=============================================================================
WHAT IS AUTOMATIC MEMOIZATION?
==============================
The idea of memoization is that it allows a function to "remember"
previous invocations, returning the previously calculated values
(rather than recalculating) if it is called with exactly the same
arguments as in a previous execution. *Automatic* memoization means
that an existing function can be transformed into a memoized one
without requiring any changes in the code for the function itself.
This can result in tremendous speedups if calculations are repeated at
various points in a program's execution, yet while remaining somewhat
transparent to the users of the code.
APPLICATIONS
============
There are four basic applications of memoization.
(A) Repetitions within a Function Call
This case, illustrated below, is when a single routine calls some subroutine
(or itself recursively) more than is needed, resulting in extra calculations.
By memoizing, these results are returned immediately for subsequent calls,
with the effect of dynamic programming. In fact, this first case can be
thought of as a tool for automatic dynamic programming, but without the
need to build the subpieces in the correct order. This can frequently
reduce the time of exponential algorithms to polynomial or even linear
time. Given enough thought, this can be solved without an automatic
memoization facility by either building up the subpieces in the proper
order or maintaining a special purpose local data structure to retain the
results (ie "manual" memoization). The advantage of doing it automatically
is that less debugging and testing is required if the simple algorithm has
been already tested, the versions can be changed back and forth
interactively at run time, it is more transparent, and most importantly it
is simple and easy to use.
To illustrate this first case, consider a naive implementation of a
function to calculate the Nth Fibonacci number:
(defun Fib (N)
(if (<= N 1)
1
(+ (Fib (- N 1)) (Fib (- N 2)))) )
Once (Fib (- N 1)) is calculated, there should be no need to repeat the
calculation of (Fib (- N 2)), since it has already been performed as part of
the calculation of (Fib (- N 1)). These wasted calculations result in
exponential time to calculate (Fib N), growing as the golden ratio to
the Nth power. On almost any machine, N of 40 or 50 is the maximum tractable
calculation. Calling (Memoize 'Fib) before invoking Fib results in linear time,
so that N in the hundreds still only requires fractions of a second on most
machines. Later calculations require only constant time if they calculate
(Fib M) for an M less than or equal to a previously calculated value.
Of course, one doesn't need memoization to get an efficient calculation of
Fibonacci numbers. Simple tail-recursive or iterative implementations will
give the same performance, and there is even a closed form. But there are
many real-life problems where the more efficient algorithm is not so obvious,
and it is far simpler to memoize the obvious algorithm than to determine
a better algorithm. For instance, in the Memoization-Examples file included
in the distribution, a slightly less obvious illustration is given of an
algorithm to calculated divided differences. As further illustrations, Peter
Norvig showed that a memoized version of a simple recursive descent parser
yields the same performance as chart parsing or Earley's algorithm for parsing
context free languages. Paul McNamee has shown that memoizing the simple
brute-force approaches to the 0/1 knapsack problem or the matrix chain
problem gives the same performance as the complex dynamic programming
implementations. Other similar examples abound.
(B) Repetitions over Time
The second case is for invocations of a function that are repeated over
time, but from scattered places in the program, or even when revoked
repeatedly by a user in an interactive program. This generally yields a
speedup by a constant factor, but that factor may be large. Without an
automatic memoization facility, the only alternative is maintaining a
special purpose global data structure, requiring testing and debugging,
and much extra effort for something that at best is equally efficient as
memoization.
(C) Off-line Runs
The third case is when a function is so expensive that you want to
perform the calculations off-line and save the results for a later
session. The automatic memoization facility provides a simple and
transparent method to save the results and have them associated with the
function automatically in a later session. See Save-Memo-Table in the
following section for an explanation of how to do that.
(D) Timing and Profiling
The final case is when using memoization as a tool in conventional
performance profiling and optimization. Many implementations provide
some sort of a metering system, and this should be used for major test
cases. However, there is often tremendous overhead involved, with
20-30x slower performance when a routine is fully metered. For quick
test cases, it is often useful to know if speeding up a particular
routine will have much effect on the top-level timing. By using
Memoized-Time or With-Memoization, a user can memoize the routines in
question then run the same test case multiple times. If the identical
test case runs only, say 5% faster even during the second memoized
run, then this suggests that no amount of memoization in the routines
in question will make more than a 5% difference in the performance of
the test case, and that this is likely not the place to begin the
optimization efforts.
POTENTIAL PITFALLS
==================
(A) Non-Functions.
Memoization is only meaningful for routines that are true functions, not
procedures. That is, output must be totally determined by input, and there
can be no internal dependency on global variables or other side effects.
(B) Destructive Operations
If a memoized function returns a value that is later destructively modified,
then later calls that expect the original value will get the modified value
instead. For instance, one rule of thumb for performing destructive operations
on lists (nconc, setf on a specific location, sort, etc.) is that it is safe
only when the list is newly consed; ie you can guarantee that the function
providing you with the list has built it, and thus it does not share structure
with lists used elsewhere. However, if the function that builds the list is
memoized, it no longer conses the list afresh, and destructive operations can
cause problems.
(C) Arguments not testable by EQUAL
Memoization uses EQUAL to compare the current argument list to former
ones. If the argument list contains some entry (eg arrays) where only
EQUALP can recognize that two different objects have identical internal
values, undue repitition may result.
(D) Non-Printable Values
The SAVE-MEMO-TABLE code depends on having the print representation of
an object be such that READ can interpret it again. This is true for
lists, symbols, numbers, and strings, but not for arrays, hash tables,
CLOS instances, etc. In some of those cases a custom print function could
be defined, but in general there is a limitation on the types of values
(either input OR output) that can be in memoized functions that will be
saved to disk.
(E) Too-Strict Matches
Memoization is performed by doing an exact match on the argument list, using
EQUAL by default. If you write (defun Foo (&key (Bar 2) (Baz 3)) ...) and then
memoize FOO, all of the following will be treated as distinct, even though
the parameters have identical values:
(Foo)
(Foo :Bar 2)
(Foo :Bar 2 :Baz 3)
(Foo :Baz 3 :Bar 2)
etc.
Similarly, one can have counterintuitive results when the arguments are
floating point numbers, forgetting, for instance, that 2 is not EQUAL
to 2.0, 1.234567 is not EQUAL to 1.23456, etc., even though your function
may treat them as identical.
One possible solution is to use "wrapper functions" that take keyword
arguments, floating point numbers, etc., canonicalize their arguments,
then pass them onto some internal function that expects the arguments
in that standard format. This prevents unexpected mismatches, and
can help keep the size of the hash table smaller.
(F) Compiler Optimization of Self-Recursive Calls
Some LISP implementations, Lucid in particular, will remove
all self-recursive calls when compilation is done at the highest
speed optimization (3). Ie recursive routines jump directly
to the code, rather than going through the symbol-function slot.
This means they cannot be TRACEd, and memoization will only
benefit for repeated calls to the top-level function. So in the
case of FIB above, the first call would still take exponential time,
and calling (Fib 30) would *not* mean that (Fib 29) will become
stored in the table.
However, compilers that have this optimization also have flags that
can be set to prevent its use. In Lucid, this is set via
(user::compiler-options :tail-merge NIL)
(G) Memory Usage
In most cases, memoization is a time vs. memory tradeoff. In extreme
cases where a frequently repeated function generates large structures
memoization may actually save memory (no garbage), but in most cases
you sacrifice space in order to gain speed. These tradeoffs should
be evaluated carefully, using such tools as MEMOIZED-FUNCTION-CALL-COUNT
to see how often a function actually repeats, WITH-MEMOIZATION,
and MEMOIZED-TIME (which reports time and space for both memoized
and unmemoized versions).
MAIN USER ROUTINES
==================
Define-Memo-Function: a macro that can be used just like "defun", but
which has the result of defining a memoized function. Also updates
the doc string and the results of calling "Arglist" (if available in
current LISP implementation) on that function name. Any of the keywords
acceptable to Memoize can optionally be passed on, resulting in
specialized versions of memoization that seed their initial hash
tables from the disk, use particular hash table tests, etc.
With-Memoization: a macro that takes a list of function names and any
number of LISP forms and executes them in a context where the
functions are temporarily memoized.
(With-Memoization (Foo Bar Baz)
(Form-1)
(Form-2)) results in executing the two forms while functions
named Foo, Bar, and Baz are memoized. Useful for getting a quick feel
for the potential speed benefits of memoization.
Without-Memoization: a macro that executes LISP forms in a context
where all memoization is temporarily turned off.
(Without-Memoization
(Form-1)
(Form-2)) executes the two forms with no functions memoized.
Memoize: Takes a function name and changes its function definition to
be a memoized function.
(defun Foo (Args) <Body of Foo>) followed by
(Memoize 'Foo) has the same effect as doing
(Define-Memo-Function Foo (Args) <Body of Foo>), but calling
"Memoize" directly is sometimes more convenient when testing things
out, as it requires no changes in the preexisting code.
Save-Memo-Table: Saves to disk a definition of the hash table
associated with a given memoized function name. By defining a
memoized function via
(Define-Memo-Function Foo (<Args>)
<Body>)
running the time-consuming cases off-line, calling
(Save-Memo-Table '<Function-Name>)
then using
(Define-Memo-Function Foo (<Args>)
(:Hash-Table-Source :Disk)
<Body>)
or by calling Memoize with the :Hash-Table-Source set to :Disk,
you can have a function "remember" the values it calculated, not only
in the current run but also in the previous off-line run.
Clear-Memo-Table: Takes a function name and clears out the memo table
associated with the function. Useful when some internal change makes
the previously stored values incorrect.
Unmemoize: Takes a function name and returns it to the unmemoized form.
Useful for timing and for debugging, especially tracing recursive
routines. In combination with "Memoize", this lets you switch back
and forth between memoized and normal versions without changing or
reloading the code. Similarly, Unmemoize-Functions takes a list
instead of a single one, and Unmemoize-All-Functions unmemoizes
everything.
Rememoize: Takes the name of a function that is currently unmemoized,
but which had previously been memoized. Memoizes it again, but uses
the previous hash table instead of creating a new one. Similarly,
Rememoize-Functions applies to a list.
Memoized-Function-Call-Count: Given the name of a memoized function,
tells how many times that function has been called, and which of
those were simple table lookups that had been stored from a previous
invocation, vs how many were newly calculated using the original
function. For a normal memoized function, lets the user see if
memoization is paying off after a long period of time. For a function
whose memo table was stored on disk, lets the user see if the stored
values covered all or most of the cases.
Memoized-Time: Takes a list of functions and a single form and evaluates
and times the form 3 times, once without memoization, once with
memoization and an empty cache, and once with memoization but the
full cache from the previous run.
*Memoized-Function-Names*: a list of the currently memoized functions.
"Memoize", "Memo", and "Clear-Memo-Table" were based on code in Peter
Norvig's outstanding book _Paradigms of AI Programming: Case Studies in
Common LISP_, Morgan Kaufmann, 1992, which in turn was inspired by code in
ex. 3.27 of Abelson, Sussman, and Sussman's _Structure and Interpretation
of Computer Programs_, MIT Press, 1985. Comments and suggestions on the
code were given by Jim Mayfield (University of Maryland Baltimore County),
J. Paul McNamee (AAI Corporation), Peter Norvig (Sun Microsystems), and
David Scheerer (The Johns Hopkins Applied Physics Lab).
--------------------------------------------------------------------