[plt-scheme] quote-syntax vs. quote

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?
 > 
 > The compiled form of a `quote' expression is an immediate constant, but
 > the compiled form of a `quote-syntax' form involves an indirection
 > through the Scheme stack. (The indirection is necessary because the
 > meaning of a `quote-syntax' expression depends on the phase in which
 > the code is executed. Without the indirection, code in a module body
 > would have to be duplicated for every instantiation.)
 > 
 > The indirection alone couldn't account for a x5 slowdown, but it might
 > trigger closure allocation that makes a significant difference. For
 > example, a `lambda' expression that contains only a quote expression is
 > a compile-time constant, whereas a `lambda' expression that contains a
 > `quote-syntax' creates a new closure every time that the expression is
 > evaluated.

I've managed to come up with a minimal program that triggers the
slowdown.  I think it might be related to your `lambda' example but I
can't quite tell exactly what's going on here...

  (module null-syntax mzscheme
    (provide null-syntax)
    (define-syntax (null-syntax stx)
      (syntax-case stx ()
	(_ #'(quote-syntax ()))))
    null-syntax
    null-syntax
    null-syntax
    ...repeated 5000 times...
  )

(I couldn't come up with a way to do this with a loop rather than 5000
copies of the expression, sorry.)  When I load this file, it takes
over 5 seconds:

  Welcome to MzScheme version 206.1, Copyright (c) 2004 PLT Scheme, Inc.
  > (time (load "null-syntax.ss"))
  cpu time: 5310 real time: 5341 gc time: 140

But if I replace `quote-syntax' with `quote', it takes no time at all:

  Welcome to MzScheme version 206.1, Copyright (c) 2004 PLT Scheme, Inc.
  > (time (load "null-syntax.ss"))
  cpu time: 230 real time: 233 gc time: 90

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.

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??

--dougo at place.org