Based on comments from my previous post on jump tables, I decided to follow-up with a slightly more comprehensive analysis.
Below is the running time, in milliseconds, to execute a given
case-style macro one million times with n branches; each execution resulted in the code taking the default case. These running times include the changes suggested by Juho Snellman (seconded by Duane Rettig) to make the times somewhat more accurate, that is, use
funcall on a function object instead of a symbol.
A '—' means that I could not get the given use case to compile.
|Jump table running times (ms)|
|Clozure Common Lisp 1.3-RC1||case||ncase||switch||case/tree|
|ACL (free edition) 8.1|
|Lispworks Personal 5.1.1|
I should point out that you shouldn't put much stock into the n = 1000 case since any
case macro that uses 1000 or more cases is almost certainly pathological. Duane made this point in the comments of my previous post and I think it's important to consider. It might be tempting to say that CLISP has a "better"
case macro since it has the same performance on 10 elements as it does for 1000; however, this would miss the point that most other Lisp systems are about 6-9 times faster in the vast majority of cases. Even n = 100 is probably so rare that you'd never see it in daily work unless you went digging.
Below is a bar graph of the performance of
case/tree relative to
case. Each bar represents the relative difference for the performance of a given macro on n branches compared to
case; I omitted the case of n = 1000 since I can't see it being practical. A value of 0 indicates it is equivalent to
case. For example, in Lispworks, the
ncase macro is 5 times faster with 100 branches than case (represented by the dark blue colour █ bar). Conversely, in Clozure CL, the switch macro is about 7 times slower with 10 branches than the case macro (the red colour █ bar).
What is clear from the graphs is that
switch doesn't provide any benefits over
case (when the cases are all single integer values, anyway). Also, using
case/tree is of some benefit when the number of cases is large, except when using Allegro CL or CLISP. Probably the most interesting aspect is that
case/tree tend to be slightly worse for small numbers of branches.
There are still some interesting questions that could be explored here (Can a compelling use case for
switch be made? How often do large branch
case expressions appear in actual code?), but it seems to me that jump table macros are, for the most part, of academic interest only. You can probably feel pretty confident that using
case is sufficient.