Quadratic work done by (for/list ... (in-producer ... ) ... )

[clinbr]

I've stumbled on a performance bug while running code from an old mailing list thread comparing alternatives to using generators. It was introduced in commit 5e94a90.

I've attached a more thorough benchmark script with results, but the short of it is that the function produced by

(define (make-real-generator N)
  (generator
   ()
   (for ([i (in-range N)])
     (yield i))))

used in the form

(length (for/list ([x (in-producer (make-real-generator 40000) void?)])
               x))

takes around 20 seconds from commit 5e94a90 onwards but took around 0.4s beforehand.
The for/vector form is unaffected and had similar runtime to for/list beforehand. The slowdown looks (vaguely) quadratic:

#<procedure:make-real-generator> 
with for/vector
N=40000 cpu time: 359 real time: 363 gc time: 21
N=20000 cpu time: 170 real time: 170 gc time: 8
N=10000 cpu time: 85 real time: 85 gc time: 3
with for/list
N=40000 cpu time: 19545 real time: 19610 gc time: 4538
N=20000 cpu time: 4168 real time: 4178 gc time: 628
N=10000 cpu time: 1001 real time: 1003 gc time: 68
10000

The code that produced the above snippet is attached: quadratic-for-list.test.rkt.txt

The results:
after.txt
before.txt

Apologies for the ugly formatting!

[mflatt]

Thanks for the report!

The root problem here is Racket's implementation of continuations, where continuation capture or restore can take O(N) time for a continuation of size N. Each access of the generator is working in a longer continuation.

The short-term solution is probably to change the for[*]/list expansion back. The long-term solution is probably a better implementation of continuations.