Thursday, July 16, 2009

Jump tables follow-up

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.

At the request of Michael Weber, I included his ecase macro, except that has been renamed to case/tree and changed slightly to accept a default case.

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
n 10 45 52 361 42
100 278 51 443 68
1000 3447 51 725 88
SCBL 1.0.29.54.rc2
n 10 54 60 222 63
100 218 59 203 88
1000 2029 60 222 112
ACL (free edition) 8.1
n 10 40 50 280 50
100 40 50 270 50
1000 4160 40 340 70
Lispworks Personal 5.1.1
n 10 43 44 288 48
100 258 43 237 54
1000 3064 277 69
CLISP 2.47
n 10 363 550 615 804
100 390 549 693 1332
1000 368 549 612 1898

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 ncase, switch and 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).

jump-tables.png

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 ncase or 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 ncase and 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.

5 comments:

informatimago said...

Lisp is a programming programming language. Therefore while I'd agree that it'd be pathological to _write_ a 1000-clause CASE, I'd not be so fast to discard their use in generated code. Or do you want to make the life of the DSL designers and macro writers miserable? Of course, we can always fall back to TAGBODY, but who knows better how to implement an efficient 1000- or 10,000-clause CASE than the implementer?

Geoff Wozniak said...

@informatimago: I'm not arguing that there is not a use case for jump tables, just that they probably don't arise very often. I think the data makes clear that they can be of use, but in limited circumstances. (And certainly, it will be up to the implementor to make that decision!)

Brad Lucier said...

The paper "Rapid case dispatch in Scheme", which Will Clinger presented at the 2006 Scheme Workshop, may be relevant here. Clinger's paper and the benchmarks he used for his tests can be found at

www.ccs.neu.edu/home/will/Research/SW2006/

Gambit Scheme has since implemented the approach that Clinger suggests.

grant rettke said...

Writing a 1K+ case statement might be pathological; but compiling down to that certainly is not. Why throw out a reasonable use case just because it isn't common for you quite yet? Potential Lisp macro writers everywhere just got dissuaded because of the benchmarks; and from reading your excellent post that most certainly was not your intent! :)

John Fremlin said...

Could you post the source code for these new tests?

Is your switch macro still using a hash-table -- perhaps O(log n) complexity? (Not clear at all as we have small n) -- instead of an array with O(1) complexity lookups?