[Axiom-developer] lisp speedups

[daly]

Another technique that significantly improves the speed of lisp
code is the use of declarations. In general, a function call in 
lisp has to have a case statement of the possible types of each
argument and needs to handle the possible types. However, if you
tell the compiler what the argument types are and the return types
are you can get significantly faster code. The best way to illustrate
this is to use the DISASSEMBLE function which will show you the code
that gets laid down by the lisp compiler. CMUCL and SBCL are very
good at optimizing code. GCL also does an excellent job. That's what
the .fn files are for in Axiom.

So, if you have a function + and you say:
   (+ a b)
the compiler cannot assume that a or b are anything so it has to
check for arguments such as lists. 

You can improve the calling code by using THE... as in
  (+ (the integer a) (the integer b))

Lisp can optimize a bit further if you know that the arguments will
always be less than a machine-sized integer, called a FIXNUM. Then
you can say:

  (+ (the fixnum a) (the fixnum b))

However you haven't told the compiler that the result will not
exceed a machine fixnum. You can do this with:

  (the fixnum (+ (the fixnum a) (the fixnum b)))

And now the compiler can improve the function call, potentially 
even inlining the + operation and reducing it to a single machine
add instruction. It can assume that the add will get two machine
sized integers and return a machine-sized result without overflow.

Type declarations can cause a huge speed improvement. CMUCL and
SBCL have amazing optimizing compilers that use type information well.

GCL can automatically generate the type information for all of
the functions in a file. If you first load the GCL file, gcl_collectfn.lsp
and then tell the compiler to emit the type definitions you'll get a .fn
file. So the sequence for optimizing is:

(load "gcl_collectfn.lsp")
(compiler::emit-fn t)
(compile-file "yourfile.lisp")
(load "yourfile.fn")
(compile-file "yourfile.lisp")

The first compile-file will generate the .fn, which contains the type
info (and you can hand-augment this if you like), and the second compile-file
will generate much faster code. Once you know this type information you can
hand code it in your original source file and eliminate the collectfn step.

You can do global declarations using PROCLAIM and DECLARE.

See http://www.lrdr.epita.fr/dload/papers/verna.06.imecs.pdf
"How to make Lisp go faster than C"

Tim