ABSTRACT Improving the Performance of AI Software: Payoffs and Pitfalls in Using Automatic Memoization

Many functions perform redundant calculations. Within a single function invocation, several sub-functions may be invoked with exactly the same arguments, or, over the course of time in a system run, a function may be invoked by different users or routines with the same or similar inputs. This observation leads to the obvious conclusion that in some cases it is beneficial to store the previously calculated values and only perform a calculation in situations that have not been seen previously. This technique is called memoization, and the “manual ” version of this generally involves building lookup tables. This however, is often a tedious and time-consuming process, and requires significant modification and debugging of existing code. This is frequently inappropriate in the dynamic, rapid-prototyping context of AI software development. An “automatic ” memoization facility is one in which existing functions can be programmatically changed to cache previously-seen results in a hash table. These results will then be returned when the functions are invoked with arguments they have seen previously. This can be done without changing the code, thus providing a simple, modular, and transparent way to dramatically accelerate certain types of functions. This paper presents an overview of automatic memoization and discusses the types of applications that benefit from it, illustrated with experiences on the ARPA Submarine Signature Management System, a large LISP-based decision aiding system. 1. Overvie