'(Apress Fractal Contest)
Apress, the publisher of the very good Lisp tutorial, Practical Common Lisp by Peter Seibel, is sponsoring a fractal generator contest. I have decided to take a shot at one of the prizes using code based on the fractal code I used for my latest fractal movie. I've stripped out some excess code and substituted a Lisp JPEG encoder in place of my TGA writing code. The encoder comes from the cl-jpeg package on Debian/Sarge. There's only the one Lisp file to do all the work and it looks to be portable across pretty much any ANSI Common Lisp implementation.
The deadline for the contest has passed. Here is my Readme file. See below for the sources.
Apress Fractal Contest Submission
By
David Steuber <david@david-steuber.com>
This entry is written in ANSI Common Lisp. The code has been
optimized for SBCL but it should work under any ANSI CL
implementation. The make script and the run script both assume SBCL.
Please have a recent version of SBCL installed on your system to run
this code for the contest. A binary that was built for Linux on x86
(any distribution of recent vintage should do) has been included in
the bin directory for your convenience.
Included files:
* Readme -- This file.
* make -- A simple shell script to build the fractal generator using
SBCL.
* run -- A simple shell script to run the fractal generator from the
command line. The existence of the bin files is assumed.
* sampleinput.txt -- The file supplied by Apress used to test this
fractal generator.
* bin/sbcl -- SBCL 0.9.3.3 built from CVS on Debian Sarge with a 2.6
kernel and sb-thread enabled.
* bin/apress-fractal.core -- SBCL 0.9.3.3 core file generated by
./make (not GNU make!).
* src/apress-fractal.lisp -- ANSI CL fractal generator code and JPEG
code with licenses included in the source text. The fractal code
is written entirely by David Steuber. The JPEG code is from
Debian's cl-jpeg package and written by Eugene Zaikonnikov. Kevin
Rosenberg apparently packaged it for Debian. David Steuber
heavily modified the code (mostly by removal of the decoding
portion) to reduce computational overhead of producing fractal
images in JPEG format. Many compilation notes remain, so further
optimization is possible.
How to rebuild the bin files:
If you are running a non-Linux x86 compatible system (such as OS X)
then you can rebuild the bin directory files using the make script.
You must have a working copy of SBCL in your $PATH before running
the make script! To build the bin directory, type
./make
in your terminal. The make script will start SBCL and then compile
and load the src/apress-fractal.lisp file. Then a core file will be
created and SBCL will be copied to bin. This will allow the run
script to work. If make doesn't run, you can type 'sh make' instead
or chmod +x make then ./make.
How to run the fractal generator:
Just type './run input.txt' (without the quotes) in your terminal.
input.txt is the name of the file with the fractal bounds data and
is not included. It must conform to the same format specified by
the contest page. See sampleinput.txt for an example. The
specified outputpic/ directory will be created with one JPEG file
for each line in input.txt. The Unix time utility will work in the
usual fashion if this is how you plan to time code from the command
line:
time ./run input.txt
The fractal generator wastes a bit of time by letting you know its
progress.
Experimenting with apress-fractal.lisp:
It is possible to run the fractal generator from any ANSI CL
compliant Lisp. This code was developed on Mac OS X 10.3.9 under
OpenMCL from recent CVS sources. It was tested under SBCL 0.9.3.3
and clisp 2.33.2 under OS X. It has been reported to work under
ABCL by piso of #lisp. It has been run under SBCL 0.9.3.3 on Debian
Sarge (Intel Celeron 566 CPU). The supplied binary files in bin are
from running ./make on Debian Sarge and should work on any Linux
system with a 2.4 or later kernel (threading is not used) such as
Red Hat 9.0 on an x86 compatible processor.
The details of running apress-fractal.lisp depend on your Lisp
environment. Using Emacs + SLIME + slime-supported-lisp, load
apress-fractal.lisp into a buffer and do C-c C-k to compile and load
the file. When the Lisp has finished compiling, go to the
*slime-repl* buffer and try:
CL-USER> (generate-fractals-from-input-file "input.txt")
Use the correct path name for input.txt.
If you suffer brain damage and want to try using a lisp directly,
you can do that too. eg, start SBCL:
david@interloper:~/usr/src/apress-fractal
$ sbcl
This is SBCL 0.9.3.3, an implementation of ANSI Common Lisp.
More information about SBCL is available at
NOTICE! The appress-fractal.lisp file contains a minor error. I've fixed it in the apress-fractal.lisp.txt file, but not in the apress-fractal-contest-entry.tar.gz file. The problem is an incorrect type declaration in the (defclass mset-map ...) form. OpenMCL checks against the type and doesn't compile it. SBCL 0.9.4 and CLisp 2.33.2 let it go. A future version of SBCL will catch this error and refuse to compile the code.
- All the sources and a Linux/x86 binary in tar.gz format
- The Lisp code which is all you need to play with the generator
Winners Are Announced
Apress announces the winners of the Fractal Programming Contest. I am not one of them. #lisp is all atwitter. I congratulate the winners, particularly Mathias Helm with his PHP entry that managed to zip through the fractals in an amazing 2 minute 28.7 seconds. I must admit to being very impressed by that time. I'm looking forward to seeing his code published by Apress along with the input.txt file used for the contest.
I ran my fractal code on vega using the sampleinput.txt file. My SBCL code only managed to come in at just over three seconds as shown here:
david@vega:~/usr/src/apress-fractal $ time ./run sampleinput.txt Generating fractals from "sampleinput.txt" DONE real 0m3.139s user 0m3.097s sys 0m0.030s david@vega:~/usr/src/apress-fractal $ time ./run sampleinput.txt Generating fractals from "sampleinput.txt" DONE real 0m3.107s user 0m3.077s sys 0m0.031s david@vega:~/usr/src/apress-fractal $ time ./run sampleinput.txt Generating fractals from "sampleinput.txt" DONE real 0m3.127s user 0m3.097s sys 0m0.030s
If instead one decides to run my code in CLisp on the exact same hardware, the results are of course far worse:
david@vega:~/usr/src/apress-fractal/src
$ clisp
i i i i i i i ooooo o ooooooo ooooo ooooo
I I I I I I I 8 8 8 8 8 o 8 8
I \ `+' / I 8 8 8 8 8 8
\ `-+-' / 8 8 8 ooooo 8oooo
`-__|__-' 8 8 8 8 8
| 8 o 8 8 o 8 8
------+------ ooooo 8oooooo ooo8ooo ooooo 8
Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2004
[1]> (load (compile-file "apress-fractal.lisp"))
Compiling file /home/david/usr/src/apress-fractal/src/apress-fractal.lisp ...Performing compile-time optimization.. please wait.
Done.
***snip a bunch of compiler notes***
[2]> (time (generate-fractals-from-input-file "../sampleinput.txt"))
Real time: 120.436554 sec.
Run time: 120.44069 sec.
Space: 1454721176 Bytes
GC: 2272, GC time: 6.89292 sec.
NIL
[3]> (quit)
Bye.
My time on CLisp is faster than the winning PHP time. This doesn't mean anything though because the sampleinput.txt file is not necessarily the file used for the contest.
Once Apress publishes the winning code along with the input.txt file used for the contest, I can compare my times. I'm fairly certain that SBCL wins hands down. CLisp I'm not so sure about because the JPEG encoder is also Lisp. The PHP code will at least have had a chance to use a C library for the JPEG encoding.
Murphy vs Moore
Fast Lisp code loosing to slow PHP code seemed to be an unnatural state of affairs. So I sent an e-mail to Apress. I asked on the Apress forums. I didn't bother to consider that people at Apress are rather busy. I had put enough work on my submission that I just wasn't thinking about that. I wanted to know what was up. Early Friday morning of September 23, 2005, Roger Yeh of Apress responded:
Hello David:
How are you? I am looking at http://www.david-steuber.com/Lisp/Apress-Fractal-Contest/ and it looks great. Unfortunately I did not receive a submission from you. In fact, the latest email I received from you was on July 29th (see attached). I remembered how you were interested in doing the fractal generator in SBCLisp and I was actually a little surprised when I didn't see it.
I wonder if you still have the email which contains your submission. If so, can you email it to me? I looked hard at my August 15th emails yet couldn't find anything from david@david-steuber.com.
Sorry this happens. From your site it's obviously that you've put a lot of time onto this project. Please believe that we are trying our best to ensure the fairness of the contest.
regards
roger
Uh oh.
I responded to Roger's request by resending my contest entry mail. I was dismayed when this came back:
From: postmaster@email.steuber.com [mailto:postmaster@email.steuber.com]
Sent: Friday, September 23, 2005 5:21 AM
To: david@david-steuber.com
Subject: Delivery Status Notification (Failure)
This is an automatically generated Delivery Status Notification.
Delivery to the following recipients failed.
xxx@Apress.com
yyy@Apress.com
zzz@Apress.com
Reporting-MTA: dns;email.steuber.com
Received-From-MTA: dns;david-steuber.com
Arrival-Date: Fri, 23 Sep 2005 05:15:40 -0400
Final-Recipient: rfc822;xxx@Apress.com
Action: failed
Status: 5.2.3
Diagnostic-Code: smtp;450 5.2.3 Msg Size greater than allowed by Remote Host
Final-Recipient: rfc822;yyy@Apress.com
Action: failed
Status: 5.2.3
Diagnostic-Code: smtp;450 5.2.3 Msg Size greater than allowed by Remote Host
Final-Recipient: rfc822;zzz@Apress.com
Action: failed
Status: 5.2.3
Diagnostic-Code: smtp;450 5.2.3 Msg Size greater than allowed by Remote Host
My contest attachment was apparantly too large for one of the mail servers along the way. This isn't Apress's fault or Roger Yeh's fault. Different MTA's are configured to different sized message body limits.
The only thing I can infer from this is that Roger Yeh did not receive my e-mail just as he said. I just wish I received a notification failure then when I could have done something about it. It would've been nice to have my name on the winner's page.
Update
Apress has now published source code of entries along with the input.txt file used for the contest.
