I've often wondered whether writing a
cond-like macro that uses jump tables is worth the effort. To get an idea as to how much I should pursue this, I decided to take Tim Bradshaw's
ncase macro and pit it against
Tim admits that
ncase is meant to show what is possible with macros and that it may be the case it may not make any performance improvement at all. Still, I think it would be interesting to compare it and see the results, simply because I really don't know what will happen.
In addition to Tim's jump table, I wrote a simple jump table implementation called
switch that uses a hash table to look up the value and associates the body with a thunk; the hash table is computed with an
load-time-value to minimize table creation overhead.
switch has the disadvantage of performing a hash table lookup and calling a function with the advantage that the values to match can be anything you would compare with
To compare the running times, I generated functions that contain 10, 100 and 1000 branches respectively (plus the default branch). This was done for each of
switch. Each branch would compare a single integer and return that integer. For example, the body of
case-100 would look something like the following.
(case v (1 1) (2 2) ... (100 100) (t nil))
It's easy to see why I generated these function bodies with macros...
I ran each function one million times, making it hit the default case each time. The time required to run the function one million times on different Lisp systems are given below in milliseconds. These were run on a 2.16 GHZ 17" Macbook Pro running Mac OS X 10.5.7.
|SBCL 188.8.131.52.rc2|| || |
|CLISP 2.47|| || |
|ACL Free edition 8.1|| || |
I was quite surprised at the results. I ran these a few times to make sure I wasn't missing something. In particular, I'm drawn to the results from CLISP. It seems lookups with case is constant. The reason this is so compelling is that SBCL and ACL are quite slow in these cases. ACL seems to be very fast otherwise.
I'll have to take a closer look at the disassembled code to see what is going on (or perhaps you can mention something in the comments if you know). Regardless, it's something that deserves some more attention.
- SBCL took approximately 4 minutes to compile the
ncasewith 1000 branches. It also used up an awful lot of memory in the process. It took more than 10 seconds to compile the
switchwith 1000 cases.
- The code I used to get these numbers can be found on paste.lisp.org.