Performance

Student: Master, is Lisp slow?

Master: Lisp programs can be a fast as C programs, even faster.

Student: If that is so, why is my program slow?

Master: It is easy to write Lisp. It is easy to write slow Lisp.

Student: If I write fast Lisp will it look like C?

Master: It can, but you can also use the unique features of Lisp.

Common Lisp has acquired a reputation of being slow. This reputation it is based partly on fact and partly, perhaps mostly, on myth. For example, in reviewing a recent book on garbage collection, Doctor Dobbs Journal writes

only a small fraction of programmers have ever worked with garbage collected languages. In part, this has been because of garbage collection's historic association with interpreted, high-level, and (most importantly) slow languages such as lisp.

Over the past decades, considerable effort has gone in to making efficient Lisp implementations. Also, many of the modern compiler optimization techniques have come from Lisp and related languages. When push comes to shove, a Lisp program can be quite competative with a C program, for example, with benchmarks being within a few percent of C.

Dispite this, it is easy to write a program that works but is slow. For example, simply translating a floating-point intensive C program into Lisp without delcarations can be disappointing.

In any language, writing high performance software requires careful design, and understanding the underlying language model. This is particularly true in higher level languages, like Lisp, Java and even C++. Programmers are often suprised that their program can be made signicantly faster with a relatively small amount of effort.

Performance is an issue, but not the only issue.
- Gabriel

Papers

Fast floating-point processing in Common Lisp, Fateman, R.J., Broughan, K.A., Willcock,D.K., and Retig, D., 1995. ACM Trans. Math. Softw. 21, 1(Mar.), 26-62. Speed of floating-point intensive algorithms written in Lisp can be comparable to (within 25%) of the same algorithm written in C or Fortran. See also: Reid, J.K., 1996. Remark on "Fast Floating-point PRocessing in Common-Lisp", ACM Trans. Math. Softw. 22, 4(Dec.), p.496-497.

Point in Polygon Benchmark by John Watton and Mike Harper, A comparison of floating-point benchmark in several languages and language implementations. The benchmark computes if a point is inside a polygon.

Fannkuch Benchmark This is an analysis of an extremely sensitive integer benchmark written in Lisp and C.

Pseudoknot Benchmark A floating point intensive benchmark for functional compilers taken from a molecular biology application. Performance of over 20 function languge implemntations are compared to C performance. I think Lisp could show better here with a little tuning. The performance of the functional languages is quite remarkable considering that the C version cuts every possible corner (such as side-effecting global variables) while the functional programs were required to remain functional.

Courage in profiles Compares performance of Lisp and C versions of two 2,000 line programs. Demonstrates the importance of profiling. Slides

Freeing the Essence of a Computation A simple object oriented partial evaluator. How to go from a compact high-level expression of an algorithm to an efficient implementation.

Measure and Explore How to avoid the pitfalls in measuring performance. A useful microbenchmarking test harness.

Performing Lisp Tutorial - LUV'94 Slides Part 1 Part 2

Profiling Talk 1996 Slides. Talk on profiling and its pitfalls with Lisp and C++ examples. One single line change lead to a 4000 fold speedup. There is a performance quiz, the answers to which might suprize you. Learn the trick so valuable it is called "the Trick".

Jon Louis Bently, Writing Efficient Programs, Prentice-hall 1982. This is a wonderful book containing references to what has now become software folklore.

Richard P. Gabriel "Performance and Evaluation of Lisp Systems", MIT Press, 1985. This is a classic book on benchmarking written during a period or rapid evolution of Lisp systems similar to what is happening with Java today. Gabriel's benchmarks lead to considerable performance improvements to Lisp systems.


Ken Anderson