Tibor's Musings

Common Lisp Interpreted vs Compiled

Is there a difference between running interpreted and compiled Common Lisp code?

Your collaborators told you that:

I believe that the disappointment is largely related to the misunderstanding regarding Common LISP compilation method: Common LISP can NOT be executed interpreted - it is always compiled. [...] Accordingly, by proclaiming compilation of a file nothing is in fact accomplished, except that the compiled mirror is saved in a seperate file. This certainly cannot improve the execution [...]

This is wrong. Common Lisp offers both interpreted and compiled functions. See the language standard or any other Lisp book for that matter. (Some Common Lisp implementations may decide to compile everything though.)

You are using Allegro Common Lisp, so here's a short example with Allegro CL 6.2 on GNU/Linux, timing a recursive Fibonacci number calculator for an illustration.

Fibonacci interpreted vs compiled

(defun fib (n)
  "Calculate Fibonacci number for N recursively."
  (declare (values fixnum))
  (if (< n 2)
      (+ (fib (- n 1)) (fib (- n 2)))))

Firstly, fib.lisp running interpreted:

$ acl
CL-USER(1): (load "fib.lisp")
; Loading /home/simko/private/work/lang/lisp-tests/fib-test/fib.lisp
CL-USER(2): (describe #'fib)
#<Interpreted Function FIB> is a FUNCTION.
  The arguments are (N)
CL-USER(3): (time (fib 28))
; cpu time (non-gc) 14,810 msec user, 20 msec system
; cpu time (gc)     3,070 msec user, 0 msec system
; cpu time (total)  17,880 msec user, 20 msec system
; real time  18,046 msec
; space allocation:
;  21,597,594 cons cells, 1,143,644,184 other bytes, 5,224 static bytes

Secondly, fib.lisp running compiled:

CL-USER(4): (load (compile-file "fib.lisp"))
;;; Compiling file fib.lisp
;;; Writing fasl file fib.fasla16
Warning: No IN-PACKAGE form seen in
         (Allegro Presto will be ineffective when loading a file having
         no IN-PACKAGE form.)
;;; Fasl write complete
; Fast loading
;    /home/simko/private/work/lang/lisp-tests/fib-test/fib.fasla16
CL-USER(5): (describe #'fib)
  The arguments are (N)
CL-USER(6): (time (fib 28))
; cpu time (non-gc) 20 msec user, 0 msec system
; cpu time (gc)     0 msec user, 0 msec system
; cpu time (total)  20 msec user, 0 msec system
; real time  17 msec
; space allocation:
;  1 cons cell, 0 other bytes, 0 static bytes

In other words, (load ...) makes the function interpreted and leads to the runtime of 17880 ms, while (load (compile-file ...)) makes the function compiled and leads to the runtime of 20 ms.

General speedup tips

So, if you want to speed up your CL application, then:

  • make sure you're running compiled code, see (describe ...) in the example above, or better yet use (disassemble ...) and check the machine code (or bytecode) produced by the compiler
  • declare proper optimization settings, e.g. (declaim (optimize (speed 3) (safety 1) (debug 0) (compilation-speed 0) (space 0)))
  • profile the code to find weak spots, for example with CMU CL do (profile:profile-all) before calling your code, and (profile:report-time) after calling it. This will give you the list of weak spots, and for each weak spot do...
    • ... reduce consing as much as possible, think of better algorithms and data structures
    • ... declare variable types, e.g. a simple string: (declare (type simple-base-string x)) or a positive fixnum integer: (declare (type (integer 0 #.(- most-positive-fixnum 1)) n)
    • ... read compiler cost hints and make promises to the compiler, e.g. (the fixnum ...) so that it can stay with fixnum arithmetics

By doing so the Common Lisp implementations usually produce machine code that runs quite as fast as that produced by C++ compilers.

Optimisation anecdote

BTW, some time ago somebody challenged comp.lang.lisp about Lisp's presumed slowness with respect to a Coyote Gulch floating-point benchmark. The claim was that Common Lisp implementations will yield much slower code than C/C++. The result was that CMUCL and SBCL produced code that was faster than the GNU C++ reference. The debate can give you ideas on how to get things Coptimized in Lisp.

For the full thread, see: http://groups.google.com/groups?q=g:thl1632776609d&dq=&hl=en&lr=&ie=UTF-8&selm=165b3efa.0403011540.6edea34c%40posting.google.com&rnum=1.

For a concise summary and lessons to retain, read the story in Bill Clementson's blog.