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 hall@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 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) ) followed by (Memoize 'Foo) has the same effect as doing (Define-Memo-Function Foo (Args) ), 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 () ) running the time-consuming cases off-line, calling (Save-Memo-Table ') then using (Define-Memo-Function Foo () (:Hash-Table-Source :Disk) ) 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).