plt/racket — pull request #120 by 97jaz (2012-07-19 23:30:30+00:00)
Title: New 'case' implementation, based on Clinger's "Rapid Case Dispatch in Scheme"

On Clinger's microbenchmarks [http://www.ccs.neu.edu/home/will/Research/SW2006/case.sch], the new implementation performs the same as the current one for small case expressions (approx. 10 constants), and outperforms it as the size increases. Benchmark numbers are at the end of this message.

Considerations:

1) The new implementation tends to produce larger code. The byte-compiled benchmark suite, for example, is 82650 bytes using the current implementation and 95133 bytes using the new one.

2) For the most part, I'm using Clinger's threshold parameters, which were tuned for Larceny/Twobit and may not be optimal for Racket.

3) I'm not entirely confident that my use of syntax-local-lift-expression is proper.

4) Unlike Clinger's version, mine can use a combination of binary search and table lookup for fixnum/char dispatch.

Representative benchmark run:

key:
f: N fixnum constants
s: N symbol constants
c: N char constants

Racket's current 'case':
=================
f10
--------------------------------------------------------
case:1:100000
cpu time: 6 real time: 7 gc time: 0

s10
--------------------------------------------------------
case:one:100000
cpu time: 7 real time: 6 gc time: 0

f100
--------------------------------------------------------
case:1:10000
cpu time: 52 real time: 52 gc time: 0

s100
--------------------------------------------------------
case:one:10000
cpu time: 55 real time: 55 gc time: 0

c100
--------------------------------------------------------
case:
:10000
cpu time: 48 real time: 48 gc time: 0

f1000
--------------------------------------------------------
case:1:1000
cpu time: 1948 real time: 1946 gc time: 0

s1000
--------------------------------------------------------
case:one:1000
cpu time: 3047 real time: 3044 gc time: 0
=================

New 'case' implementation
===================
--------------------------------------------------------
case:1:100000
cpu time: 7 real time: 7 gc time: 0

--------------------------------------------------------
case:one:100000
cpu time: 7 real time: 6 gc time: 0

--------------------------------------------------------
case:1:10000
cpu time: 20 real time: 20 gc time: 0

--------------------------------------------------------
case:one:10000
cpu time: 42 real time: 43 gc time: 0

--------------------------------------------------------
case:
:10000
cpu time: 36 real time: 37 gc time: 0

--------------------------------------------------------
case:1:1000
cpu time: 50 real time: 50 gc time: 0

--------------------------------------------------------
case:one:1000
cpu time: 67 real time: 67 gc time: 0