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

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.

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.

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?

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