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.
|
|
|
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.
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.
Paul McNamee
Last updated: August 21, 1998
