Macro expansion time unexpectedly quadratic

[mnieper]

Let COUNT be a (huge) integer. By my experiments with Chez Scheme, the expansion time of the following program is quadratic (or worse) in COUNT:

(import (rnrs))

(define-syntax foo
  (let ((count COUNT))
    (lambda (stx)
      (syntax-case stx ()
	((_ e)
	 (if (zero? count)
	     #''done
	     (begin
	       (set! count (- count 1))
	       #'(foo (+ 1 e)))))))))

(display (foo 0))
(newline)

These are running times reported by my local machine:

COUNT	Time
5000	0.5 s
10000	1.5s
20000	6.1s
40000	29.8s
80000	2m35s

The marks and substitutions algorithm should be able to expand the program in linear time. I also tested the program with Guile, whose expander is based on an old version of Chez's expander and Guile shows approximately linear behavior:

COUNT	Time
5000	0.05s
10000	0.4s
20000	0.6s
40000	1.2s
80000	2.5s

[burgerrg]

It appears to be the macro expander's tracking of source information for the (display (foo 0)) line that causes the quadratic behavior. If you put the definition alone into a file and load it, then type (foo 0) at the repl, it will run as fast as you expect, because (foo 0) at the repl has no source information.