[gambit-list] gc problems with streams/recursions

Christian christian at pflanze.mine.nu
Sun Oct 30 16:49:00 EST 2005


Hello

While playing with streams, I think I've noticed that the stream
"head" is not garbage collected while traversing the stream even if it
is not referenced by user data structures anymore.

There also seems to be a (independent?) problem releasing memory when
streams are long (thus recursion is deep). I'm getting out of memory
errors when "there shouldn't be", and need to run (##gc) manually to
be able to continue calculations (entering ,c in the debugger resumes
calculation correctly): it looks like gambit is starting to fill up
all available memory if the recursion depth is bigger than something
between 20000 and 35000.

The two issues happen in both interpreted and compiled code.

$ ulimit -S -v 300000
$ gsc
> ; (compile-file "test.scm")
> (load "test")
> (test 35000)
repeat the test call several times, it will give
*** ERROR IN ##bignum.make -- Heap overflow
after about 10 invocations.
Same thing with
> (test-2 35000)

This can be repeated "forever" without hitting out of memory errors:
> (test 20000)
or this
> (test-2 20000)

(There are two implementations of stream-take below (one commented
out), choosing the other one doesn't change the situation.)

This is with Gambit Version 4.0 beta 14 on Debian ppc. With beta 15 on
Debian x86, the out of memory situation already happens with a test
argument of 25000.

What I'm especially wondering is this: the output list from take only
needs about 600000 bytes. So if the stream would be deallocated while
stream-take is still walking it, much longer streams should be
possible (at least 10 times longer). Do you have an explanation or a
solution?

Thanks
Christian.


;; test.scm

(declare
 (block)
 (standard-bindings)
 (extended-bindings)
)

;; stream library

(define *stream-strict* #f)
(set! *stream-strict* #t)

(define @force ##force)
(define @promise? ##promise?)
(define @car ##car)
(define @cdr ##cdr)
(define @pair? ##pair?)
(define @null? ##null?)

(define (stream-force strm)
  (if (@promise? strm)
      (@force strm)
      (if *stream-strict*
	  (error "not a stream: expected promise, got:" strm)
	  strm)))

(define stream-car
  (lambda (strm)
    (let ((p (stream-force strm))) (if (@pair? p) (@car p) (error "stream-car: not a pair:" p)))))
(define stream-cdr
  (lambda (strm)
    (let ((p (stream-force strm))) (if (@pair? p) (@cdr p) (error "stream-cdr: not a pair:" p)))))

(define (null-stream? strm)
  (let ((l (stream-force strm)))
    (cond ((##pair? l) #f)
	  ((##null? l) #t)
	  (else (error "null-stream?: argument out of domain:" l)))))

; (define (stream-take strm k)  ;; returns a list, not a stream.
;   (if (and (##fixnum? k) (##fixnum.>= k 0))
;       (if (##fixnum.= k 0)
;           '()
;           (or (and (not (null-stream? strm))
;                    (let ((res (cons (stream-car strm) '())))
;                      (let iter ((res-tail res)
;                                 (strm (stream-cdr strm))
;                                 (k (##fixnum.- k 1)))
;                        (if (##fixnum.zero? k) res
; 			   (let ((p (stream-force strm)))
; 			     (and (##pair? p)
; 				  (let ((res-next (##cons (##car p) '())))
; 				    (##set-cdr! res-tail res-next)
; 				    (iter res-next
; 					  (##cdr p)
; 					  (##fixnum.- k 1)))))))))
; 	      (error "stream-take: stream too short")))
;       (error "stream-take: k is not a positive fixnum:" k)))

(define (stream-take strm k) ;; returns a list, not a stream.
  (if (and (##fixnum? k) (##fixnum.>= k 0))
      (let recur ((strm strm) (k k))
        (if (##fixnum.zero? k) '()
	    (let ((p (stream-force strm)))
	      (if (##pair? p)
		  (##cons (##car p)
			  (recur (##cdr p) (##fixnum.- k 1)))
		  (error "stream-take: stream too short")))))
      (error "stream-take: k is not a positive fixnum:" k)))


(define-macro (scons a r)
  `(delay (cons ,a ,r)))


;; the actual program

(define (fib-stream)
  (letrec ((strm
	    (scons 0
		   (scons 1
			  (let recur ((2behind (let ((s strm))
						 ;(set! strm #f); make gc possible? no, doesn't help.
						 s)))
			    (delay
			      (let ((a (stream-car 2behind))
				    (r (stream-cdr 2behind))
				     )
				(cons (+ a (stream-car r))
				      (recur r)))))))))
    strm))

(define (fib-stream-2) ;; (misses the first two values of the fib series)
  (let recur ((pprev 0)
	      (prev 1))
    (delay
      (let ((cur (+ prev pprev)))
	(cons cur
	      (recur prev
		     cur))))))

(define t #f)

(define (test n)
  (time (set! t (stream-take (fib-stream) n))))

(define (test-2 n)
  (time (set! t (stream-take (fib-stream-2) n))))

;;end




More information about the Gambit-list mailing list