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.