Friday, September 14, 2007

Performance tuning in lisp

The more I use Lisp, the more I appreciate it. Recently I had to tune up the performance of a knowledge based application running on Allegro CL. We made extensive use of a reasoner. The reasoner, being a reasoner, had to be general purpose. Our application used a subset of the reasoner. The manner in which we went about performance tuning could possibly be done with any language capable of introspection, but this is just about lisp.

Broadly speaking, I see two approaches to tuning performance: use a better algorithm, and cache intermediate results. Given that the reasoner was essentially a library, we didn't have sufficient understanding to perform serious algorithmic tuning. However, there was a lot we could do with caching.

Consider that in a full frame based reasoner, a general purpose application could be creating arbitrary knowledge. At no point can we make a "closed world assumption" and optimize certain behaviors of the reasoner. However, an application using the reasoner does know when to make such assumptions. For example, we may enter a phase of computation where we're not creating any new classes, or creating any new slots. In our case, we never create any slots after compile time. So we can safely start caching the results of all computations performed on slots. For example, computing the inverse of a slot can potentially be a complex operation, but since we know we aren't going to see any operations on slots we can start caching these slot inverses.

Here's where Lisp comes in. The function that computes slot inverses is a library function that we don't control. Given that we can manipulate the symbol table, however, we can create a wrapper around the function body, and setf the wrapper to the symbol's function value. This will not catch all types of uses of the slot inversion function. It catches most of them though, and the result is a noticeable performance improvement. So, not only does Lisp allow us to apply targeted optimizations in software we have ourselves written, but it also allows us to apply optimizations in software we've inherited as libraries, based on the usage pattern of those libraries in the final application.