Coding Tips {This text is (c) 1996 by Ronald Parr. You may distribute this freely, but you may not charge for it.} Intro ----- Getting reasonable performance out of arrays in Common Lisp is unreasonably hard. In some Common Lisp implementations, for example, a simple typo in a declaration, undetected and unreported by the compiler, can cause a 5-10X speed penalty. This document gives some general hints to help you avoid some of the traps that I have encountered while trying to squeeze he maximum speed out of my lisp code. Differences between Lisps ------------------------- The first thing that you should do when trying to speed up array operations is to get to know your lisp implementation. An approach that is good for one lisp my be disasterous for another. The qtest.cl file in the Quick Arrays package will give you some indication of the best approach for your system, but you should read the manuals if they are avaiable and do some experimenting on your own. At the end of this document, I'll include some tips for specific CL implementations. Optimization ------------ Some lisps make use of optimization information specified in forms such as: (declare (optimize (speed 3) (safety 0) (debug 0) (space 0))) while others pretty much ignore them. One bit of advice if you want to mess around with optimization declarations: depending upon your lisp implementation and OS, code with bugs that is compiled with safety 0 may crash your lisp or your entire machine. Many lisps will perform on-the-fly type checking and other error checking when the safety setting is 1 or higher, so you can save yourself a lot of trouble by debugging your code with a high safety setting. Type Declarations ----------------- Lisps vary widely in their ability to make use of type declarations. As with optimization declarations, they will sometimes be ignored and sometimes be exploited to great extent, so it pays to know what your lisp uses and what it ignores. One of the most annoying features of many lisps is that they ignore syntactically invalid type declarations without any kind of warning from the compiler or interpreter. A typo in a type declarations inside of a critical loop can have a devastating effect on your code's performance. Consider the following: (declare (type (simple-array double-float (* *)) x)) This declares x to be a simple array of type double-float. If you accidentally leave out the double-float: (declare (type (simple-array (* *)) x)) the resulting code may be 5-10 times slower. If you forget to put a variable name in: (declare (type (simple-array double-float (* *)))) you won't get any warnings from most compilers, but the declaration will, of course, be useless. There are a few important things you should know about using type declarations with arrays and in particular, the effect of the :element-type keyword argument to make-array. If you do not specify the :element-type keyword, most lisps will return vectors. According to the langauge specification, these cannot be typed so it is useless and sometimes confusing to apply a type declaration to such arrays. For example, suppose I have created an array with: (setf x (make-array '(10))) The type declaration: (declare (type (simple-array double-float (10)) x)) is incorrect since make-array returns a vector and vectors cannot have typed elements. However, if you create the array as follows: (setf x (make-array '(10) :element-type double-float)) then the type declaration will be valid. It is extremely important that you know what you are doing if you use typed arrays. Defining a typed array and using it like a regular array, or with incorrect type declarations can slow your code down and generate more garbage than regular, untyped arrays. In my opinion, you should not even try to use typed arrays unless you have access to CMU CL. I'm not saying that you need to use CMU CL for your runtime system, but CMU CL has the only compiler that I am aware of that will check type declarations and give informative messages on how to correct or improve your code. When you reach the optimization stage of your code devleopment process, I would suggest obtaining access to a machine that can run CMU CL and doing all of your optimzations in that environment. Even if your system is able to exploit typed arrays to produce code that is faster than quick array code, you may still want to use quick arrays because they generally provide a speed-boost over regular non-typed arrays with much less fuss than typed arrays and much less danger of producing dramatically slower code as a result of a typo. If you are using arrays of elements of mixed type, then you will probably want to use quick arrays as well. The (the type form) form ------------------------ This form is usually interpretted as an assertion about the type of of a form, something that is added for the purposes of runtime or compiler error checking. However, I have found that this form can improve performance in some lisps where the compiler takes this information to be a promise about the type of a form and removes type checking code. For example (* (the double-float x) (the double-float y)) may be faster than (* x y) Since typing these forms becomes tiresome and reduces the readability of your code, you may want to define macros like, d*, to indicate multiplication of two doubles. A downside of this approach is that the removal of type-checking code may cause crashes when a variable of the incorrect type is used and the safety setting low. Floating point types -------------------- Floating point performance will depend heavily on the type of floating point numbers that you use. Contrary to intuition, double floats are faster on many machines even though they require the manipulation of twice as many bits. The reasons can be traced to quirks in the C libraries used to compile your lisp implementation, or design trade-offs made in your CPU. For example, some CPUs don't have hardware for single precision operations at all, meaning that extra code must be added to convert between singles and doubles. You should do some simple experiments to figure out which floating point type is fastest on your system and then stick with that type. If your code will be used in multiple architectures, I would suggest defining a new type called fast-float with the deftype form and then using pragmas to conditionally define this type depending upon the environment. Specific Lisp Tips ------------------ Allegro CL (Unix): Allegro CL tends to ignore many type declarations, and gives no warnings about errors in declarations. It does appear to make use of (the type form) assertions to optimize code. Typed arrays can be a big win in Allegro CL if you can get the declarations right, a big problem if you get them wrong. If you are willing to put the effort in (runing your code through CMU CL can big a big help here) and you can live with arrays in which all elements are of the same type, then use typed arrays. Otherwise, use quick arrays. Be careful with code with a low safety setting. Allegro CL omits type checking and core dumps can result. CMU CL: When the speed optimization setting is high, CMU CL provides lots of useful feedback as it compiles code with declarations. Read through this carefully. If you are willing to work at it, you should be able to get your code to compile without warning messages, which means that CMU CL (and perhaps other lisps) can make full use of your declarations. CMU CL will generate very fast code for typed arrays. For mixed-type arrays, use quick arrays. MCL 3.9: MCL 3.9 tends to ignore type declarations, even syntactically invalid ones. Arrays created using the :element-type keywords are slower and more cumbersome than any other kind of array. Quick arrays appears to be a superior approach for all array operations in MCL 3.9.