Efficient Method Dispatch in PCL
This paper describes a mechanism for implementing CLOS method dispatch
efficiently on stock hardware, in the current generation of Common
Lisp implementations. This mechanism is implemented in the newest
version of PCL, a portable implementation of CLOS, and runs in more
than ten Common Lisps. This work is based on a careful analysis of
the behavior of existing CLOS programs. The method dispatch mechanism
differs from previously published work in three important ways.
First, the use of a new hashing algorithm improves memoization table
density and distribution. Second, the selection of memoization table
format based on the dynamic history of each generic function makes it
possible to store information in the memoization tables more
efficiently and do the runtime method dispatch more quickly. Third,
lazy updating techniques are used to speed interactive programming
environment response without undue degradation of program execution.
Go to to Selected Papers page.