John Fremlin's blog: How to optimise Common Lisp under SBCL: introduction

People occasionally ask me vague questions about how to optimise their programs. Generally, that's because their programs don't have challenging performance demands, and they've wisely postponed thinking about it. Continue not thinking about it and skip this series of posts.

Firstly, I am specifically talking about optimisation as in making something working go faster, and as most code doesn't get to the stage where it works, is generally irrelevant. Like scaling to large workloads, it is largely of theoretical interest to your typical engineer, and a great deal of nonsense is written about it by engineers who have never really needed to do it and are therefore free to confirm whatever bias they started with. Here is a general attempt to provide a concrete guide to optimisation, giving examples from tpd2: a program in Lisp that is comparable in speed to the best equivalent programs in more machine-orientated languages.

One way of looking at it, is that optimisation is about avoiding doing unnecessary things, and doing the necessary things faster. Quite often, it actually makes a program simpler and clearer to understand. A better engineer than me will write a program that is both simpler and faster than mine. These two aims are generally achieved together.

Secondly, there is a saying made famous by Knuth that premature optimisation is the root of all evil. Inexperienced engineers tend to worry greatly about performance in irrelevant places, and their idea of what is inefficient is often utterly misguided. Think rationally about whether the effort is well spent, and take measurements to determine whether your theories are correct. Modern compilers and hardware architectures are very sophisticated. Don't make complicating optimisations without measuring their benefit even if you vaguely know what you are doing. This is especially important, given that Lisp environments are complex and often introduce unexpected inefficiencies, and do not have compilers on a par with GCC.

The other danger is that your planned design has no hope of meeting its performance requirements, and a few minutes considering it could save you a rewrite later. If you actually have a performance challenge, then consider it from the outset. How will the data flow through your program? A few realistic back-of-the-envelope calculations can save an expensive rewrite, and give you an idea of what is important.

Thirdly, despite the inauspicious start, this series of posts is not about vague generalisations. It is about SBCL, which is the highest performance Common Lisp implementation today, and how best to use the tools it provides.

Continued.

UPDATE 20100109 — There are no inefficient languages! Thanks to drewc.