[plt-scheme] quote-syntax vs. quote

At Wed, 21 Apr 2004 07:12:22 -0400, Doug Orleans wrote:
> Matthew Flatt writes:
>  > At Mon, 29 Mar 2004 04:25:35 -0500, Doug Orleans wrote:
>  > > I've been trying to track down some unbearable slowness in my code,
>  > > and I finally isolated it to a quote-syntax expression, which changing
>  > > to quote instead results in a 5x speedup.  I'm pretty sure that the
>  > > slowdown must be happening somewhere further down the dataflow, but I
>  > > thought I'd ask just to be sure: is there some reason why quote-syntax
>  > > would be an order of magnitude slower than quote?

I assumed originally that your question was about run time. But your
example program is about compile-time slowness, right?

> I can also get a similar speedup by commenting out the `module' and
> `provide' lines, so it seems to have something to do with module
> expansion.

Not quite. If you replace `module' by `let', it's the same slowdown.

> The time is quadratic, by the way-- if I use 10000 copies of
> `null-syntax' instead of 5000, it takes 26 seconds rather than the
> expected 10 or so.  What's going on??

Yep, a stupid quadratic-time algorithm is lurking in there. Thanks for
tracking this down. I've fixed it in the exp- and v299-tagged code in
CVS.

Details:

As MzScheme expands code, syntax objects accumulate a lot of context
that will never be used. As the last step of compilation, MzScheme
tries to simplify syntax under `quote-syntax' to throw away useless
information.

Furthermore, many syntax objects in an expression or module have the
same simplified information. To make .zo files smaller (and to make
them load faster), MzScheme checks whether a simplification result is
the same as a previous simplification result. But this check was
implemented as an O(n) operation for n previous simplifications. (Since
each `(quote-syntax ())' in your module is generated by a different
macro invocation, they're all different, making the time quadratic
overall.)

If you use `begin' instead of `module', then the `begin' is spliced
into the top-level, and each `(quote-syntax ())' is simplified
independently, so it didn't trip over the quadratic-time algorithm.


Matthew