Practical Common Lisp

not internal bookkeeping such as the garbage collector. Here's a trivial but useful profiling tool built with a few macros and GET-INTERNAL-RUN-TIME:

(defparameter *timing-data* ())
(defmacro with-timing (label &body body)
  (with-gensyms (start)
    `(let ((,start (get-internal-run-time)))
      (unwind-protect (progn ,@body)
        (push (list ',label ,start (get-internal-run-time)) *timing-data*)))))
(defun clear-timing-data ()
  (setf *timing-data* ()))
(defun show-timing-data ()
  (loop for (label time count time-per %-of-total) in (compile-timing-data) do
       (format t '~3d% ~a: ~d ticks over ~d calls for ~d per.~%'
               %-of-total label time count time-per)))
(defun compile-timing-data ()
  (loop with timing-table = (make-hash-table)
     with count-table = (make-hash-table)
     for (label start end) in *timing-data*
     for time = (- end start)
     summing time into total
     do
       (incf (gethash label timing-table 0) time)
       (incf (gethash label count-table 0))
     finally
       (return
         (sort
          (loop for label being the hash-keys in timing-table collect
               (let  ((time (gethash label timing-table))
                      (count (gethash label count-table)))
                 (list label time count (round (/ time count)) (round (* 100 (/ time total))))))
          #'> :key #'fifth))))

This profiler lets you wrap a with-timing around any form; each time the form is executed, the time it starts and the time it ends are recorded, associating with a label you provide. The function show-timing-data dumps out a table showing how much time was spent in different labeled sections of code like this:

CL-USER> (show-timing-data)
 84% BAR: 650 ticks over 2 calls for 325 per.
 16% FOO: 120 ticks over 5 calls for 24 per.
NIL

You could obviously make this profiling code more sophisticated in many ways. Alternatively, your Lisp implementation most likely provides its own profiling tools, which, since they have access to the internals of the implementation, can get at information not necessarily available to user-level code.

Once you've found the bottleneck in your code, you can start tuning. The first thing you should try, of course, is to find a more efficient basic algorithm—that's where the big gains are to be had. But assuming you're already using an appropriate algorithm, then it's down to code bumming—locally optimizing the code so it does absolutely no more work than necessary.

The main tools for code bumming in Common Lisp are its optional declarations. The basic idea behind declarations in Common Lisp is that they're used to give the compiler information it can use in a variety of ways to generate better code.

For a simple example, consider this Common Lisp function:

(defun add (x y) (+ x y))

I mentioned in Chapter 10 that if you compare the performance of this function Lisp to the seemingly equivalent C function:

int add (int x, int y) { return x + y; }

you'll likely find the Common Lisp version to be quite a bit slower, even if your Common Lisp implementation features a high-quality native compiler.

That's because the Common Lisp version is doing a lot more—the Common Lisp compiler doesn't even know that the values of a and b are numbers and so has to generate code to check at runtime. And once it determines they are numbers, it has to determine what types of numbers—integers, rationals, floating point, or complex—and dispatch to the appropriate addition routine for the actual types. And even if a and b are integers—the case you care about—then the addition routine has to account for the possibility that the result may be too large to represent as a fixnum, a number that can be represented in a single machine word, and thus it may have to allocate a bignum object.

In C, on the other hand, because the type of all variables are declared, the compiler knows exactly what kind of values a and b will hold. And because C's arithmetic simply overflows when the result of an addition is too large to represent in whatever type is being returned, there's no checking for overflow and no allocation of a bignum object to represent the result when the mathematical sum is too large to fit in a machine word.

Thus, while the behavior of the Common Lisp code is much more likely to be mathematically correct, the C version can probably be compiled down to one or two machine instructions. But if you're willing to give the Common Lisp compiler the same information the C compiler has about the types of arguments and return values and to accept certain C-like compromises in terms of generality and error checking, the Common Lisp function can also be compiled down to an instruction or two.

That's what declarations are for. The main use of declarations is to tell the compiler about the types of variables and other expressions. For instance, you could tell the compiler that the arguments to add are both fixnums by writing the function like this:

(defun add (x y)
  (declare (fixnum x y))
  (+ x y))

The DECLARE expression isn't a Lisp form; rather, it's part of the syntax of the DEFUN and must appear before any other code in the function body.[328] This declaration declares that the arguments passed for the parameters x and y will always be fixnums. In other words, it's a promise to the compiler, and the compiler is allowed to generate code on the assumption that whatever you tell it is true.

To declare the type of the value returned, you can wrap the form (+ x y) in the THE special operator. This operator takes a type specifier, such as FIXNUM, and a form and tells the compiler the form will evaluate to the given type. Thus, to give the Common Lisp compiler all the information about add that the C compiler gets, you can write it like this:

(defun add (x y)
  (declare (fixnum x y))
  (the fixnum (+ x y)))

However, even this version needs one more declaration to give the Common Lisp compiler the same license as the C compiler to generate fast but dangerous code. The OPTIMIZE