Lisp Jump Tables July 12th, 2009
Patrick Stein

A few weeks back, I posted about how I know that I have more to grok about Lisp macros. In that post, I needed to explain Lisp macros a bit for those not in the know. The example that I used was creating a jump table.

Geoff Wozniak just posted an article in his blog wherein he explores using a macro to do jump tables using an array of functions. He performed timing tests using Tim Bradshaw’s ncase macro versus case and switch.

The timing differences there are quite amazing. I’ve toyed around with optimizations quite a bit and have never seen Allegro outperform SBCL before this. It is also interesting that CLISP may already do this jump table optimization. I have never seen CLISP come anywhere close to SBCL or Allegro before this.

Update: Including timing numbers from my own machine

My machine is a 2.4GHz Intel-based Mac with 4GB of RAM. Here are the numbers that I get for this test. (All numbers in milliseconds).

  n case ncase switch
SBCL 1.0.29 10 166 149 207
  100 185 146 191
  1000 572 147 207
CLISP 2.47 10 115 211 188
  100 117 205 219
  1000 111 206 189
ACL 8.1 (heap-limited) 10 10 20 90
  100 20 10 90
  1000 1420 20 130
CMUCL 19f 10 120 120 180
  100 150 120 210
  1000 520 120 210
Clozure v1.3-r11936 10 19 15 128
  100 108 14 130
  1000 1214 14 117

Updates In Email

Email:

l