'(Mandelbrot Set in Lisp)

Not so long ago, I made a little movie. The numerically intensive code was written in C while the script to drive it was written in Perl. The C source file is sitting on my Athlon box which currently won't boot. The Perl code is rather ugly. If it weren't for these facts, I would go ahead and publish the code used to create the frames for that movie.

There is no need to despair.

I've taken a short break from Carbon Programming to revisit my old friend the Mandelbrot Set. This time I'm using Lisp for the whole works. Well, not the part that I will use iMovie and Quicktime for. But the frame calculations are done entirely in Lisp. And while the Perl code produced XPM files which I converted to TIFF with a graphic converter utility, the Lisp code is writing TGA files directly. I went with TGA because the format is nice and simple. That's basically the same reason I chose XPM with the Perl code except that with Lisp it is easier to write binary files than it is with Perl and XPM is a text based format.

So I have frames being produced by the Lisp code. Another thing I did was improve the basic algorithm. My C program calculated all the pixels in each frame. This chews up a lot of CPU cycles while inside the set because there is no escape from there. The Lisp code is using two seperate but complimentary strategies to reduce computations.

The heavy lifting is done by an escape function. It's really just a loop that is allowed to run some number of times. If the value of Z never grows beyond a certain value within that number, the point being computed is assumed to be in the set. Sometimes a point in the set will repeat itself. It's like running around in a circle. The well known Fractint program had a simple mechanism for detecting this condition. I've used it in the escape function to bail out early if periodicity is detected.

The other technique tries to reduce the number of points that need to be calculated in the first place. What I do is recursively divide the map into quarters. When all the points in the boundry of a quarter have the same escape value, I can just fill in the rectangle. The image at the top of the page shows what this looks like. I simply turned off the fill function to produce that image to show how the subdivision works. It also looks kind of cool.

There is a prevailing myth that Lisp is slow. Some people think the language is interpreted like Perl or Python. For most implementations this hasn't been true for longer than Perl or Python have even existed. Another possible contributer to the myth is the fact that Lisp uses garbage collection (no, Java did not invent this). Well, Lisp can be slow. But it doesn't have to be. Lisp offers ways to make the "hot spots" fast.

I won't go into the various facilities Lisp offers to profile code to see just what does need to be optimized here. I will just point out a few things that allow the code I'm using to be reasonably fast.

The most obvious is the DECLARE form. In a few strategic locations in the code I've declared the types the variables will hold so that the compiler can produce more efficient code instead of the more general code it produces to find out what types it is dealing with at runtime. This allows the OPTIMIZE declaration to work. The compiler may also be able to do some type inferencing but I'm not sure about that.

The other thing I'm doing is not taking advantage of the fact that Lisp has built in complex numbers. In most situations, I would go ahead and use complex arithmetic if I needed it. But by using slightly more complicated code and handling the real and imaginary parts separately I save a few math operations in the innermost loop.

I'm sure that someone with better Lisp chops than I have can produce even faster code. But the code I do have is pretty good. Using the SBCL ANSI Lisp implementation, the calculation of a frame runs in constant space. No memory is allocated during the run. Not all the array referencing is open coded, but some of it is. Basically the code is about as fast as it would be in C. C's pointer arithmetic could probably allow ever so slightly faster code, but not faster by enough to be worth writing the program in C.

Other optimizations that are possible are algorithms taking advantage of the fact that each frame of a movie is close to the previous frame. That gets complicated though. Also, I'm more interested in producing wallpaper or poster type images. The movie is just a side thing. I could also save space by directly outputting to a video format rather than individual images. I'm not doing that because the video is not the primary reason for the code. Also, having individual frames lets me play with the color palette after the fact. In fact, I am saving separate data files so that I can play with the color mapping in unlimited ways.

As I mentioned, my Athlon box is not currently bootable. I'll fix it one of these days. In the meantime, I've drafted my webserver into service making frames. It's only a 566Mhz Celeron based machine, but it has an idle CPU most of the time so it can use the exercise. Linux does a fair job of task scheduling so Apache still can serve content to my visitor and I can still use SSH to login and run Emacs and Gnus. Internet latency does a fair job of hiding the fact that the box is busy while the frames are being calculated.

Xeno's Xoom is now ready for download! It sure did take a long time to compute. If you are interested, you may also take a look at the source code. Comments are welcome. Humans should have no trouble figuring out my e-mail address. Also check out my page on Mandelbrot Set Attractors.