Fast Generic Dispatch for Common Lisp

ABSTRACT

We describe a technique for generic dispatch that is adapted to modern computers where accessing memory is potentially quite expensive. Instead of the traditional hashing scheme used by PCL [6], we assign a unique number to each class, and the dispatch consists of comparisons of the number assigned to an instance with a certain number of (usually small) constant integers. While our implementation (SICL) is not yet in a state where we are able to get exact performance figures, a conservative simulation suggests that our technique is significantly faster than the one used in SBCL, which uses PCL, and indeed faster than the technique used by most high-performance Common Lisp implementations. Furthermore, existing work [7] using a similar technique in the context of static languages suggests that perfomance can improve significantly compared to table-based techniques.

References

1. J. Bachrach and G. Burke. Partial dispatch: Optimizing dynamically-dispatched multimethod calls with compile-time types and runtime feedback. Technical report, 2000.
2. K. Driesen, U. Hölzle, and J. Vitek. Message dispatch on pipelined processors. In Proceedings of the 9th European Conference on Object-Oriented Programming, ECOOP '95, pages 253--282, London, UK, UK, 1995. Springer-Verlag.
3. E. Dujardin, E. Amiel, and E. Simon. Fast algorithms for compressed multimethod dispatch table generation. ACM Trans. Program. Lang. Syst., 20(1):116--165, Jan. 1998.
4. S. Harikrishnan and R. Kumar. Space efficient non-constant time multi-method dispatch in object oriented systems. SIGSOFT Softw. Eng. Notes, 37(2):1--6, Apr. 2012.
5. U. Hölzle and D. Ungar. Optimizing dynamically-dispatched calls with run-time type feedback. In Proceedings of the ACM SIGPLAN 1994 Conference on Programming Language Design and Implementation, PLDI '94, pages 326--336, New York, NY, USA, 1994. ACM.
6. G. Kiczales and L. Rodriguez. Efficient method dispatch in pcl. In Proceedings of the 1990 ACM Conference on LISP and Functional Programming, LFP '90, pages 99--105, New York, NY, USA, 1990. ACM.
7. O. Zendra, D. Colnet, and S. Collin. Efficient dynamic dispatch without virtual function tables: The smalleiffel compiler. In Proceedings of the 12th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA '97, pages 125--141, New York, NY, USA, 1997. ACM.
8. Y. Zibin and J. Y. Gil. Fast algorithm for creating space efficient dispatching tables with application to multi-dispatching. In Proceedings of the 17th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA '02, pages 142--160, New York, NY, USA, 2002. ACM.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers