Problems with optimizing Common Lisp code

Before I go any further : let me state upfront that knowing Lisp has changed me as a programmer for the best. It’s been an invaluable experience that I’ve carried into every corner of my career and every other language that I’ve coded with.

Now that we have that out of the way let’s move on…

There are a number of problems with Common Lisp that go unmentioned in the community. The fact that a prominent member of the CL community has recently highlighted these(at ILC 2009 no less) could be viewed as a break-through for the language in itself. The show-stoppers in my opinion from personal experience and which I’ve faced in trying to write code that performs acceptably in time and space :

“Hard to compile efficiently: It’s too hard to write a high-quality Common Lisp compiler that generates very efficient code. Certainly experience to date has validated this: not that it’s impossible, but that it’s very hard. Truth be told, SBCL and Clozure CL, both considered excellent implementations, do not generate very good code. To be sure, partly this is because generating excellent code has not been one of the things most Common Lisp users need as much as other language improvements, and so this has not been given the highest priority. Nevertheless, I think the maintainers of those implementations would agree that writing a compiler that generates excellent code is very hard. And ideally, the programmer should not have to write a lot of type declarations to get this efficient code, Lisp claiming to be a dynamically-typed language, although it is hard to produce competitive code for, say, addition, when runtime type dispatching is needed.

Furthermore, at the time Common Lisp was designed, it was assumed that many common use cases and patterns could and would be optimized by a “sufficiently clever compiler”. (I’m talking here about higher-level optimizations than peephole optimizers. For example, a “reduce” can be compiled more efficiently in certain patterns, and many sequence functions can be compiled to better code if you know at compile time that certain keyword arguments aren’t being used.) Unfortunately, nobody demonstrated such a compiler at the time, and it turned out to be far harder to do than the designers had anticipated. (The phase “sufficiently clever compiler” is used only in an ironic sense, these days!) There was a hope that a common, portable front-end of a compiler would be created and made available to everybody, that would do these optimizations, but that never happened.”

Small programs should run in a small amount of physical memory (working set). They should not have poor paging performance, and they should start up very quickly. Ideally, Common Lisp compiled code should be just as viable for writing little scripts as PERL is.

“Fundamental problems with the Common Lisp Language” – Daniel Weinreb @ ILC 2009

Besides CL compilers having a hard time generating efficient code, actually writing comparably efficient code (compared with other languages) in CL could be a less painful experience. Not to say that some of this isn’t simply related to my own ignorance about idiomatic performance/space enhancing techniques in writing CL. Still I believe that I know enough about the language to go as far and say that it’s easier to write such code in C than in Common Lisp. Having to continually tune, avoid (or completely switch off) garbage collection to get acceptable performance is no fun at all. Also to make things worse many GC features such as in SBCL are not documented in the manual. On the other hand, even though C is more verbose, the costs are known upfront in a C implementation, clear decisions can be made. To CL’s shame I’ve even had this experience with Java. Ofcourse there are some standard techniques for optimizing in CL that are common across compilers. i.e. Choose the correct data structures and re-use them, add type declarations to the code etc.
These are basically the same habits you’d follow with other languages. Still with CL it’s more difficult to tell how to optimize E.g. optimizing CL code for SBCL could be very different from optimizing code in Clozure and both will be different compared with a commercial compiler such as Allegro. Ah Allegro CL. If the Allegro CL compiler was ever open-sourced then how different things would be. What are the chances of that ever happening ? But back to techniques for writing performant CL code, what are the standard texts for this ? I’ve obviously missed them.

Now on the other hand : some of “black-magic” compiler optimizations that you can encounter can be quite difficult to follow. One case : I had written an algorithm that I expected to have a specific run time performance that the SBCL compiler then optimized, effectively changing the algorithm that had been implemented and therefore improving the run time. I’d actually prefer that Common Lisp compilers did not do this kind of optimization automatically. I prefer explicit and intended changes to my code before seeing a change in performance and/or memory usage.

Besides having a hard time dealing with optimization issues the CL hacker has still to contend with stability problems on at least 2 of the open-source CL compilers : SBCL and Clozure CL. To be fair : some of the encountered instability may be due to 3rd party CL libraries related to threading and streams. But why do we have to spend countless hours at this point debugging such commonly used libraries ? Many could even argue that some of these libraries are actually our reference implementations no less. In some cases it makes writing real-world applications almost impossible without having to pay for a commercial Lisp system.

Accounts of strange Lisp stability issues are not scarce (but may be implementation specific) :

The solutions(if they exist) are often not encouraging.

Let’s re-emphasize : I’m incredibly grateful for the open-source CL implementations. They just have not worked out for us so far in some of the specific real-world use cases I’ve encountered. Of course your mileage may vary !

I’m thinking about covering stability and performance in more technical detail with examples in future articles. This will also make clear that the author is not necessarily a CL neophite. Honestly though I’m very wary of this based on past attempts. These can be very touchy topics in the community sometimes resulting in personally having to deal with nasty backlashings.

Until next time, thanks for watching…