Automated Memoization in C++

------------------

Memoization is a caching technique that can result in enormous performance improvements in software that performs repetitive calculations. In some languages (e.g. Lisp, Prolog, and Haskell) the use of memoization can be automated so that programmers can reap the benefits of memoization without having to modify their code. Using a preprocessor tool and a supporting library, this automated technique has been extended to C++. This work was recently reported in the C++ Toolbox column of the ACM SIGPLAN Notices, Developing a Tool for Memoizing Functions in C++, August 1998.

As an example of the technique, consider the recursive, implemenation of a function to compute the Fibonacci numbers. The following code is tree-recursive and runs in exponential time. Using automated memoization, this code can be transformed to run in linear-time (see the table) without changing the readability of the function.

unsigned long Fib (int n) { if (n <= 2) return 1; else return (Fib(n-1) + Fib(n-2)); }
nFib(n)Orig (sec)Memoized (sec)
308320400.20000.0008
3592274764.20000.0008
4010233411548.2000.0010

Besides its application to expensive, recursive functions, memoization is also applicable to dynamic programming problems and can be used anywhere a dynamically created cache is needed.

Downloading, Installing, and Using the Tool

As of 8/19/98: The tool may be downloaded in UNIX tar format. I am working on ZIP as well, but in the meantime if you can't download a tar file, you can grab the files individually. The tar file contains the source code for the expanding preprocessor, the supporting Memo_Fn class, some examples of usage, and README and Makefile files.

To 'install', just un-tar and type 'make'. Users who don't have the privilege of working in a UNIX environment should still be able to download the code and build the executable and class library themselves --- but I haven't tried this. I have used the code on Sun, SGI, and HP systems.

I am interested in any feedback on the toolkit especially regarding the bugs, (I'm sure they exist), and getting it to work in an Windows environment.

Other Papers on Memoization

  1. Marty Hall and Paul McNamee, Improving Software Performance with Automatic Memoization, Johns Hopkins APL Technical Digest, 18(2), April 1997.
  2. Marty Hall and James Mayfield, Improving the Performance of AI Software: Payoffs and Pitfalls in Using Automatic Memoization, Proceedings of the Sixth International Symposium on Artificial Intelligence, Monterrey, Mexico, September 1993.
  3. Cormen, Leiserson, and Rivest, Introduction to Algorithms (chapter 16), MIT Press, 1990.

Sites of interest

------------------
Paul McNamee

Last updated: August 21, 1998