Space leak or bad gc parameters?
Hi, This week, I have implemented streams as described in SICP in Erlang. I have used Eratosthenes's sieve as a test case, as described in SICP. I already had the same algorithm in scheme. My implementation of force and delay in Erlang is the most basic using a thunk as a promise (memoization is rather difficult to implement in Erlang, which means that, for example, SICP implicit stream definition of the Fibonacci sequence is rather inefficient). On the other hand, Erlang controls much better the heap with the sieve than gsi and asking for the 100 000th prime number is just a matter of time. Gambit gsi heap grows so fast that the algorithm is just useful for teaching. I wondered if this difference was related to the delay/force implementation and to the place of the call to cdr (that is delayed or not). I rewrote the streams algorithms in scheme so they were as closed as possible to Erlang. On gsi, this has not lead to any improvement. Setting a maximum heap size has only resulted in raising an exception.On Scheme48, the sieve runs like in Erlang though slower. Erlang alike algorithms are nevertheless much much faster (about three times for the sieve). I believe Scheme48 and Erlang use the same kind of garbage collector... So is there a way to better to tune Gambit garbage collector or is this a garbage collector algorithm problem? Thanks, DenisPs http://mitpress.mit.edu/sicp/full-text/book/book.html
Afficher les réponses par date
On May 16, 2015, at 5:21 PM, Denis Fourt <denis.prog@hotmail.com> wrote:
Hi,
This week, I have implemented streams as described in SICP in Erlang. I have used Eratosthenes's sieve as a test case, as described in SICP. I already had the same algorithm in scheme.
My implementation of force and delay in Erlang is the most basic using a thunk as a promise (memoization is rather difficult to implement in Erlang, which means that, for example, SICP implicit stream definition of the Fibonacci sequence is rather inefficient).
On the other hand, Erlang controls much better the heap with the sieve than gsi and asking for the 100 000th prime number is just a matter of time. Gambit gsi heap grows so fast that the algorithm is just useful for teaching.
I wondered if this difference was related to the delay/force implementation and to the place of the call to cdr (that is delayed or not). I rewrote the streams algorithms in scheme so they were as closed as possible to Erlang.
On gsi, this has not lead to any improvement. Setting a maximum heap size has only resulted in raising an exception. On Scheme48, the sieve runs like in Erlang though slower. Erlang alike algorithms are nevertheless much much faster (about three times for the sieve).
I believe Scheme48 and Erlang use the same kind of garbage collector... So is there a way to better to tune Gambit garbage collector or is this a garbage collector algorithm problem?
Thanks,
Denis Ps http://mitpress.mit.edu/sicp/full-text/book/book.html
_______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
I have just pasted it in gsi -:s so it should be ok, please have a look. I have also tried chibi and chicken and only scheme48 was able to achieve it with less than 60MB (although it was rather slow). Please tell me if you would like to see the more crude version with delay as a thunk. Denis ;; definitions : similar to the matching functions for lists(define-syntax cons-stream (syntax-rules () ((cons-stream a b) (cons a (delay b))))) (define empty-stream '())(define stream-null? null?) (define (stream-car stream) (car stream)) (define (stream-cdr stream) (force (cdr stream))) (define (stream-filter pred? stream) (cond ((stream-null? stream) empty-stream) ((pred? (stream-car stream)) (cons-stream (stream-car stream) (stream-filter pred? (stream-cdr stream)))) (else (stream-filter pred? (stream-cdr stream))))) (define (stream-ref stream n . default) (let loop ((s stream) (i n)) (cond ((stream-null? s) (and (pair? default) (car default))) ((<= i 0) (stream-car s)) (else (loop (stream-cdr s) (- i 1)))))) ;; an infinite stream of ints(define (int-from n) (cons-stream n (int-from (+ n 1)))) (define (erastho stream) (let ((n (stream-car stream))) (cons-stream n (erastho (stream-filter (lambda (i) (not (= (modulo i n) 0))) (stream-cdr stream)))))) ;;getting the 50th prime number,(stream-ref (erastho (int-from 2)) 50);;getting the 10000th prime number(stream-ref (erastho (int-from 2)) 10000)
CC: gambit-list@iro.umontreal.ca; lucier@math.purdue.edu From: lucier@math.purdue.edu Subject: Re: [gambit-list] Space leak or bad gc parameters? Date: Sat, 16 May 2015 19:29:50 -0400 To: denis.prog@hotmail.com
Show us the code.
Brad
Ps: Sorry about my email screw ups.
On May 17, 2015, at 1:13 AM, Denis Fourt <denis.prog@hotmail.com> wrote:
I have just pasted it in gsi -:s so it should be ok, please have a look. I have also tried chibi and chicken and only scheme48 was able to achieve it with less than 60MB (although it was rather slow). Please tell me if you would like to see the more crude version with delay as a thunk.
Denis
If you compile the program it runs fine and with as little as 20MB heap. The reason you are seeing a slowdown with the interpreter is that closures are not “safe for space” with the interpreter (but are “safe for space” with the compiler). Safe for space means that a closure (in this case the one hidden in the implementation of “delay” in cons-stream) will only remember its free variables. The interpreter keeps all “in scope” variables in the closure. This is a deliberate decision because it gives a better debugging experience (you can inspect the free variables of a closure x with ,(v x) followed by ,e) allowing a better understanding of the evaluation context. Marc
Thanks for the explanation, using gsc leads effectively to a normal behaviour. Denis
Subject: Re: [gambit-list] Space leak or bad gc parameters? From: feeley@iro.umontreal.ca Date: Sun, 17 May 2015 10:42:22 -0400 CC: gambit-list@iro.umontreal.ca To: denis.prog@hotmail.com
On May 17, 2015, at 1:13 AM, Denis Fourt <denis.prog@hotmail.com> wrote:
I have just pasted it in gsi -:s so it should be ok, please have a look. I have also tried chibi and chicken and only scheme48 was able to achieve it with less than 60MB (although it was rather slow). Please tell me if you would like to see the more crude version with delay as a thunk.
Denis
If you compile the program it runs fine and with as little as 20MB heap.
The reason you are seeing a slowdown with the interpreter is that closures are not “safe for space” with the interpreter (but are “safe for space” with the compiler). Safe for space means that a closure (in this case the one hidden in the implementation of “delay” in cons-stream) will only remember its free variables. The interpreter keeps all “in scope” variables in the closure. This is a deliberate decision because it gives a better debugging experience (you can inspect the free variables of a closure x with ,(v x) followed by ,e) allowing a better understanding of the evaluation context.
Marc
By the way, in that particular case it is also much faster (about 3 times) with gsc to create thunks to delay evaluation than using gambit delay macro. I suppose, gambit does some memoization of the result of the call of force. Is this the right thing to do? Denis From: denis.prog@hotmail.com To: feeley@iro.umontreal.ca Date: Sun, 17 May 2015 12:40:02 -0400 CC: gambit-list@iro.umontreal.ca Subject: Re: [gambit-list] Space leak or bad gc parameters? Thanks for the explanation, using gsc leads effectively to a normal behaviour. Denis
Subject: Re: [gambit-list] Space leak or bad gc parameters? From: feeley@iro.umontreal.ca Date: Sun, 17 May 2015 10:42:22 -0400 CC: gambit-list@iro.umontreal.ca To: denis.prog@hotmail.com
On May 17, 2015, at 1:13 AM, Denis Fourt <denis.prog@hotmail.com> wrote:
I have just pasted it in gsi -:s so it should be ok, please have a look. I have also tried chibi and chicken and only scheme48 was able to achieve it with less than 60MB (although it was rather slow). Please tell me if you would like to see the more crude version with delay as a thunk.
Denis
If you compile the program it runs fine and with as little as 20MB heap.
The reason you are seeing a slowdown with the interpreter is that closures are not “safe for space” with the interpreter (but are “safe for space” with the compiler). Safe for space means that a closure (in this case the one hidden in the implementation of “delay” in cons-stream) will only remember its free variables. The interpreter keeps all “in scope” variables in the closure. This is a deliberate decision because it gives a better debugging experience (you can inspect the free variables of a closure x with ,(v x) followed by ,e) allowing a better understanding of the evaluation context.
Marc
_______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On 05/19/2015 02:47 PM, Denis Fourt wrote:
By the way, in that particular case it is also much faster (about 3 times) with gsc to create thunks to delay evaluation than using gambit delay macro. I suppose, gambit does some memoization of the result of the call of force. Is this the right thing to do?
Yes; see, e.g., http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Promises... Brad
Thanks. Denis
Date: Tue, 19 May 2015 15:47:00 -0400 From: lucier@math.purdue.edu To: denis.prog@hotmail.com; feeley@iro.umontreal.ca CC: lucier@purdue.edu; gambit-list@iro.umontreal.ca Subject: Re: [gambit-list] Space leak or bad gc parameters?
On 05/19/2015 02:47 PM, Denis Fourt wrote:
By the way, in that particular case it is also much faster (about 3 times) with gsc to create thunks to delay evaluation than using gambit delay macro. I suppose, gambit does some memoization of the result of the call of force. Is this the right thing to do?
Yes; see, e.g.,
http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Promises...
Brad
participants (4)
-
Bradley Lucier -
Bradley Lucier -
Denis Fourt -
Marc Feeley