[racket-dev] An implementation of 'case' based on Clinger's "Rapid Case Dispatch in Scheme"

On Sun, Jul 22, 2012 at 4:15 PM, Robby Findler
<robby at eecs.northwestern.edu> wrote:
> I don't have any good guesses as to which files trigger the problem,
> but you could time 'raco make' to try to hone in specific files. Run
> 'raco make' once to build all of a file's dependencies (or just have
> finished a raco setup run) and then delete compiled/file_rkt.zo if
> file.rkt is the file you want to time and run 'raco make' on it.

Thanks. I'll give that a try.

>
> But 7-15 seconds seems like it could easily just be because it takes a
> very small amount of time more per case expression and there are a lot
> of case expressions.

Right -- and I'm hoping to eliminate, or at least to minimize, that
very small amount of time.

However, it's possible that I was wrong about the cause of the bold
time difference. Today I updated my 'case-v3' branch with the changes
that have been committed to the plt master branch since the two
diverged, and I separately cloned the current plt master to a
different directory. (Previously, I had been using a tarball as the
control.) And I started running the build tests again. That's still
going on, but so far, the preliminary results are the opposite of the
ones from the other day. My 'case-v3' branch tends to build slightly
faster.

Obviously, there are any number of things that can account for the
build time difference: background processes eating up CPU, physical
file location on disk, etc. If the numbers continue to come out as
they are now, I'll just conclude that the build time really isn't
significantly affected one way or the other.

>
> Have you considered a hybrid approach where you first count the number
> of clauses and only use your new implementation when it is above some
> threshold?

My implementation does something like that; it counts the number of
constants, rather than the number of clauses. That's what Clinger's
version does, too, and it's probably very slightly more expensive than
just counting the clauses, but I doubt the difference is noticeable.
The syntax-case clause looks like:

[(_ v [(k ...) e1 e2 ...] ... [else x1 x2 ...])
       (if (< (length (syntax-e #'(k ... ...))) *sequential-threshold*)
           (syntax/loc stx (let ([tmp v])
                             (case/sequential tmp [(k ...) e1 e2 ...]
... [else x1 x2 ...])))
           (syntax/loc stx (let ([tmp v])
                             (case/dispatch   tmp [(k ...) e1 e2 ...]
... [else x1 x2 ...]))))]

... where case/sequential build an if-then-else tree.

-Jon


>
> Robby
>
> On Sat, Jul 21, 2012 at 10:25 PM, Jon Zeppieri <zeppieri at gmail.com> wrote:
>> I implemented a version of 'case' following Clinger's design from
>> "Rapid Case Dispatch in Scheme"
>> [http://scheme2006.cs.uchicago.edu/07-clinger.pdf]. (This came up a
>> while back on the users list:
>> [http://lists.racket-lang.org/users/archive/2011-September/048301.html].
>> In my case, I've been writing a virtual machine, and the opcode
>> dispatch could benefit from a faster 'case.')
>>
>> On Clinger's micro-benchmarks at
>> [http://www.ccs.neu.edu/home/will/Research/SW2006/case.sch], my
>> implementation performs the same as racket's current 'case' on small
>> expressions and outperforms it as the expressions get bigger.
>>
>> So, for example, on the f10 and s10 benchmarks (testing case
>> expressions with 10 fixnum and 10 symbol constants, respectively),
>> both implementations run in 6-7 milliseconds on my machine, whereas on
>> f1000, my implementation runs in 63-67 milliseconds while the current
>> racket implementation takes about 3 seconds.
>>
>> I had previously sent a pull request on the racket github site, but
>> Eli mentioned that it would be better to discuss the matter here
>> first. In that pull request, I mentioned a few caveats, the first of
>> which is that my implementation tends to produce larger code. As a
>> data point: the total size of all the .zos in the collects tree is
>> 102485877 when compiled with my implementation and 102272930 compiled
>> with the current one, so the difference represents about 0.2% of the
>> current size.
>>
>> A more serious issue, in my view, is that the new implementation
>> appears to slow down the full build (raco setup) by about 7-15 seconds
>> on my machine. Since the full build takes a long time to complete,
>> I've been trying to use smaller benchmarks to find out what, exactly,
>> is slower. I could definitely use some help with this; I think I've
>> barked up several wrong trees.
>>
>> For example, at one point I was trying to test expansion performance like this:
>>
>>    time raco expand file.rkt > /dev/null
>>
>> until I realized that, in at least one case, I was testing the
>> pretty-printer as much as anything else.
>>
>> In the github thread, Vincent mentioned the syntax.rktl tests at
>> collects/tests/racket/syntax.rktl. Averaging 5 runs of "time racket -f
>> syntax.rktl" results in:
>>
>> Clinger 'case'
>> ==========
>> real 0m0.810
>> user 0m0.648
>> sys  0m0.129
>>
>> Current 'case'
>> ==========
>> real 0m0.807
>> user 0m0.644
>> sys  0m0.130
>>
>> So, not much difference there.
>>
>> The chameneos benchmark (under
>> collects/tests/racket/benchmarks/shootout) was interesting. It uses
>> case expressions, but only small ones. The expanded code is very
>> similar for both implementations, but the current version seems to
>> perform very slightly better. However, I don't know if this is an edge
>> at runtime or at expand time (or compile time). I've begun to wonder
>> if just adding more code to the expander, whether or not it's used,
>> might be the issue.
>>
>> I'd appreciate any help in trying to determine exactly where the
>> performance difference lies.
>>
>> The latest version of the code is at:
>> https://github.com/97jaz/racket/blob/case-v3/
>>
>> The only changed files are:
>> https://github.com/97jaz/racket/blob/case-v3/collects/racket/private/more-scheme.rkt
>> https://github.com/97jaz/racket/blob/case-v3/collects/racket/private/case.rkt
>> [added]
>>
>> Note that the current version is in the 'case-v3' branch, if you
>> decide to clone my git tree. (My initial version is in the master
>> branch, and a second version is in branch 'case-v2' if anyone cares to
>> compare them.
>>
>> -Jon
>> _________________________
>>   Racket Developers list:
>>   http://lists.racket-lang.org/dev