Performance of Lisp systems

ABSTRACT

This paper describes the issues involved in evaluating the performance of Lisp systems. We explore the various levels at which quantitative statements can be made about the performance of a Lisp system, giving examples from existing implementations wherever possible. Our thesis is that benchmarking is most effective when performed in conjunction with an analysis of the underlying Lisp implementation and computer architecture. We examine some simple benchmarks which have been used to measure Lisp systems, and examine some of the complexities of evaluating the resulting timings. This paper will explain in detail the technical issues and trade-offs that determine the efficiency and usability of a Lisp implementation; though there will appear to be a plethora of facts, we will only discuss those aspects of a Lisp implementation that we feel are the most important for evaluation. Throughout we will talk about the impact of these issues and trade-offs on benchmarks and benchmarking methodologies.

REFERENCES

• 1: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 2: Henry G. Baker, Jr., Shallow binding in Lisp 1.5, Communications of the ACM, v.21 n.7, p.565-569, July 1978 [doi>10.1145/359545.359566]
• 3: Raymond L. Bates , David Dyer , Johannes A. G. M. Koomen, Implementation of Interlisp on the VAX, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.81-87, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802138]
• 4: Rodney A. Brooks , Richard P. Gabriel , Guy L. Steele, Jr., An optimizing compiler for lexically scoped LISP, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.261-275, June 23-25, 1982, Boston, Massachusetts, United States
• 5: Rodney A. Brooks , Richard P. Gabriel , Guy L. Steele, Jr., S-1 Common Lisp implementation, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.108-113, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802141]
• 6: Burton, R. R, et. al. Interlisp-D Overview in "Papers on Interlisp-D", Xerox Palo Alto Research Center, CIS-5 (SSL-80-4), 1981.
• 7: Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981 [doi>10.1145/356850.356854]
• 8: Correll, Steven. S-1 Uniprocessor Architecture (SMA-4) in "The S-1 Project 1979 Annual Report", Chapter 4. Lawrence Livermore National Laboratory, Livermore, California, 1979.
• 9: R. J. Fateman, Reply to an editorial, ACM SIGSAM Bulletin [doi>10.1145/1086803.1086804]
• 10: Foderaro, J. K., Sklower, K. L. "The FRANZ Lisp Manual", University of California, Berkeley, Berkeley, California, April 1982.
• 11: Martin L. Griss , Eric Benson , Gerald Q. Maguire, Jr., PSL: A Portable LISP System, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.88-97, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802139]
• 12: Butler W. Lampson, Fast procedure calls, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.66-76, March 01-03, 1982, Palo Alto, California, United States
• 13: Larry M. Masinter, Interlisp-VAX: a report, Stanford University, Stanford, CA, 1981
• 14: Masinter, L. M., Deutsch, L. P. Local Optimization For a Compiler for Stack-based Lisp Machines in "Papers on Interlisp-D", Xerox Palo Alto Research Center, CIS-5 (SSL-80-4), 1981.
• 15: Steele, Guy Lewis Jr. Data Representations in PDP-10 MacLisp, Proceedings of the 1977 MACSYMA Users' Conference. NASA Scientific and Technical Information Office, Washington, D.C., July 1977.
• 16: Steele, Guy Lewis Jr. Fast Arithmetic in MacLisp, Proceedings of the 1977 MACSYMA Users' Conference. NASA Scientific and Technical Information Office, Washington, D.C., July 1977.
• 17: Steele, Guy Lewis Jr., Sussman, G. J. The Dream of a Lifetime: A Lazy Scoping Mechanism, Massachusetts Institute of Technology AI Memo 527, November 1979.
• 18: Guy L. Steele, Jr., An overview of COMMON LISP, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.98-107, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802140]
• 19: Teitelman, Warren, et. al. "Interlisp Reference Manual", Xerox Palo Alto Research Center, Palo Alto, California, 1978.
• 20: Daniel Weinreb, Lisp machine manual, Massachusetts Institute of Technology, 1981
• 21: Weyhrauch, R. W., Talcott, C. T., Scherlis, W. L., Gabriel, R. P.; personal communication and involvement.
• 22: White, J. L., NIL: A Perspective, Proceedings of the 1979 MACSYMA Users Conference, July 1979.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles

General Terms:
Performance