[racket] streams, recursion and running out of memory
Hi Matthew,
Thanks for your help. I really can't even pretend to understand the
make-coroutine code but this is what I'm seeing:
Original make-coroutine, without stream-ref pre-call => out of memory (1GB)
when running (prime-pi 500000)
Original make-coroutine, with stream-ref pre-call => runs (prime-pi 500000)
in about .4 sec
Alternate make-coroutine, with or without stream-ref pre-call => runs
(prime-pi 500000) in about 28 sec
All runs from "clean" state.
-joe
On Tue, Feb 21, 2012 at 10:25 AM, Matthew Flatt <mflatt at cs.utah.edu> wrote:
> I don't know the answer, but here's a piece of the puzzle that might be
> relevant.
>
> Try this alternate `make-coroutine':
>
> (define (make-coroutine fn)
> (let ([cont #f])
> (λ ()
> (call-with-continuation-prompt
> (lambda ()
> (if cont
> (cont)
> (fn (λ () (let/cc k
> (set! cont k)
> (abort-current-continuation
> (default-continuation-prompt-tag)
> void))))))))))
>
> The difference between this one and the one on the web page is that it
> uses a prompt to avoid capturing the continuation of the initial call
> to a coroutine (i.e., it uses a delimited continuation for the
> coroutine). For me, this variant makes `(prime-pi 500000)' work without
> ``(stream-ref prime-stream (inexact->exact (* 0.1 n)))'.
>
> My guess is that avoiding capture of continuations converts O(N^2)
> space usage into O(N) space for some N-deep forcing of streams. Using
> `(stream-ref prime-stream (inexact->exact (* 0.1 n)))', meanwhile,
> might similarly avoid an N-deep nesting at the point where O(N^2)
> behavior would kick in.
>
> I haven't studied the code enough to be certain that my explanation is
> right, but when I see surprising space consumption with laziness and
> undelimited continuations, my first guess is that undelimited
> continuations are holding onto too much.
>
> At Mon, 20 Feb 2012 17:19:02 -0800, Joe Gilray wrote:
> > Hi,
> >
> > I created an infinite stream of primes (using this interesting article:
> > http://matthias.benkard.de/journal/116)
> >
> > I tried to create a prime-pi function:
> >
> > (define (prime-pi n)
> > (let loop-count ([candidate-stream prime-stream])
> > (if (> (stream-first candidate-stream) n)
> > 0
> > (+ (loop-count (stream-rest candidate-stream)) 1))))
> >
> > (prime-pi 500000) grinds and runs out of memory
> >
> > But this little cludge makes it run just fine:
> >
> > (define (prime-pi n)
> > (stream-ref prime-stream (inexact->exact (* 0.1 n))) ; cludge added
> to
> > get the stream to pre-create enough primes
> > (let loop-count ([candidate-stream prime-stream])
> > (if (> (stream-first candidate-stream) n)
> > 0
> > (+ (loop-count (stream-rest candidate-stream)) 1))))
> >
> > What am I not understanding?
> >
> > Thanks,
> > -Joe
> > ____________________
> > Racket Users list:
> > http://lists.racket-lang.org/users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120221/016695ae/attachment.html>