How can I speed up compilation of Common Lisp `IF` statements?

Question

I have a system that generates decision trees and converts them into nested Common Lisp if statements with predicates that check if a variable value is >= or <= a given integer e.g.

(LAMBDA (V1 V2)
  (IF (>= V1 2)
      (IF (<= V1 3)
          (IF (<= V2 3)
              (IF (>= V2 2) 16 (IF (>= V2 1) 6 0))
            (IF (<= V2 4) 10 0))
        (IF (<= V1 4)
            (IF (>= V2 1) (IF (<= V2 3) 6 0) 0)
          0))
    (IF (>= V1 1)
        (IF (>= V2 2) (IF (<= V2 4) 10 0) 0)
      0)))

I then use eval to compile the Lisp code, producing functions that run much faster than interpreting the original decision tree. This compilation step takes surprisingly long, though: a function with 5000 nested ifs takes over a minute to compile (in Clozure Common Lisp on a powerbook), even though generating the if statement took about 100 milliseconds. Why does such a simple structure take so long? Is there anything I can do to substantially speed it up, some declaration maybe? I'd greatly appreciate any pointers you can offer.

Answer 1

You could certainly (declare (optimize (compilation-speed 3))), and maybe reduce other qualities (see http://clhs.lisp.se/Body/d_optimi.htm#optimize).

However, I'd guess that the slow compilation is caused by the optimizations the compiler makes, so the result seems likely to be not so fast at execution time. But maybe not, you'd have to experiment.

I'd also think about what optimizations you could make yourself using your domain knowledge. Hints for that might also come from analyzing the output of disassemble on your generated functions.

Finally, maybe you can translate your decision trees into lookup tables, if the number of distinct values is not too big.

Answer 2

The actual portable function to compile functions is called COMPILE.

You can tell the Common Lisp compiler to invest less work via low optimize qualities for speed, space, debug and compilation-speed - whether this has any influence depends on the implementation.

The Clozure CL compiler is usually not the brightest one, but relatively fast. Generally I think the compiler maintainer might be able to give you more hints how to speed up compilation. Generally I would look for three

1. tell the compiler to do less work: no type inference, no code optimization, no generation of debug information, no space saving effort, ...
2. if it is necessary tell the compiler things which it would have to infer - like instead of type inference by the compiler, declare all the types during code generation. But that would mean that you actually need some advantage from type declarations like increased runtime safety or code optimizations.
3. the compiler itself may have speed penalties which may depend on the size of the source code. For example if that is quadratic, the compile time would increase by four if we double the code size. Only the compiler maintainers may know what to do in those cases - maybe they would need to implement more efficient data structures or similar....

The next option is to use a Lisp interpreter. They usually have very little definition time overhead - but the code usually runs much slower at runtime. In some problem domains it may be possible to follow a mixed approach: compile code which changes not very often and interpret code which changes often.