[R6RS] Enumerations proposal pre-draft

[William D Clinger]

I wrote six benchmarks to compare the speed of case dispatch
on consecutive fixnums versus symbols, with 10, 100, or 1000
case clauses with one fixnum or symbol each.  Each of the
benchmarks performs approximately one million case dispatches.

I benchmarked five compilers and four interpreters.  Larceny
was using sequential search for case dispatch on symbols, so
I wrote a 125-line patch to make its case dispatch on symbols
about as sophisticated as its case dispatch on fixnums.  This
patch took about an hour to write, and could be implemented
as a portable syntax-case macro.

Three of the compilers I benchmarked compile to C.  They
were unable to handle a case expression with 1000 clauses,
so those timings are absent.  Those timings are absent for
the interpreters also, because I didn't want to wait that
long.

Here are the averages of three runs, in seconds, on a
SunBlade 1500 with no other users:

                                  10             100            1000
                             fixnum symbol   fixnum symbol   fixnum symbol   
Larceny v0.91a w/patch         .04    .05      .07    .09      .14    .16
Larceny v0.91a                 .03    .04      .07    .21      .14   3.93
Chez Scheme v6.1               .04    .04      .18    .17     3.85   4.65
Compiler A                     .47    .48      .30    .28
Compiler B                     .06    .11      .02    .51
Compiler C                                     .07   6.27
Interpreter D                 1.46   1.27     9.25   7.14
Interpreter E                 1.78   1.79    11.08  10.87
Larceny v0.91a interpreter    3.48   3.61    15.68  16.42
Interpreter A                 5.24   5.27    19.50  20.03

The conclusions I draw from this are:

*  Most implementations could improve their case dispatch,
   especially case dispatch on symbols.

*  If a compiler makes about the same effort to optimize
   case dispatch on symbols as to optimize case dispatch
   on fixnums, then case dispatch on fixnums is only a
   little faster than case dispatch on symbols.

*  Case dispatch on special enumerated values will not
   be quite as fast as case dispatch on fixnums, but
   it might be very slightly faster than case dispatch
   on symbols.

*  On the other hand, case dispatch on special enumerated
   values might be slightly slower than case dispatch on
   symbols.

*  With current interpreters, it doesn't matter whether
   you dispatch on fixnums or on symbols.

I didn't write any benchmarks to compare the speed of
set computations, because I realized that singleton sets
in my proposal are basically equivalent to enumerated
values in Mike's proposal.  That means there is a uniform
way to rewrite any set computation that uses Mike's proposal
into an equally efficient set computation that uses my
proposal.

Will