(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 declaration is used to tell the compiler how to balance five qualities: the speed of the code generated; the amount of runtime error checking; the memory usage of the code, both in terms of code size and runtime memory usage; the amount of debugging information kept with the code; and the speed of the compilation process. An OPTIMIZE declaration consists of one or more lists, each containing one of the symbols SPEED, SAFETY, SPACE, DEBUG, and COMPILATION-SPEED, and a number from zero to three, inclusive. The number specifies the relative weighting the compiler should give to the corresponding quality, with 3 being the most important and 0 meaning not important at all. Thus, to make Common Lisp compile add more or less like a C compiler would, you can write it like this:
(defun add (x y)
(declare (optimize (speed 3) (safety 0)))
(declare (fixnum x y))
(the fixnum (+ x y)))
Of course, now the Lisp version suffers from many of the same liabilities as the C version—if the arguments passed aren't fixnums or if the addition overflows, the result will be mathematically incorrect or worse. Also, if someone calls add with a wrong number of arguments, it may not be pretty. Thus, you should use these kinds of declarations only after your program is working correctly. And you should add them only where profiling shows they'll make a difference. If you're getting reasonable performance without them, leave them out. But when profiling shows you a real hot spot in your code and you need to tune it up, go ahead. Because you can use declarations this way, it's rarely necessary to rewrite code in C just for performance reasons; FFIs are used to access existing C code, but declarations are used when C-like performance is needed. Of course, how close you can get the performance of a given piece of Common Lisp code to C and C++ depends mostly on how much like C you're willing to make it.
328
Declarations can appear in most forms that introduce new variables, such as LET, LET*, and the DO family of looping macros. LOOP has its own syntax for declaring the types of loop variables. The special operator LOCALLY, mentioned in Chapter 20, does nothing but create a scope in which you can make declarations.