Possible Memory Leak with stream-for-each

Possible Memory Leak with stream-for-each

[Abhijeet More]

Hi All,
I've been trying to use streams as defined in SICP using guile.
A little googling showed that an implementation had already been suggested here:
http://lists.gnu.org/archive/html/guile-user/2001-04/msg00220.html

However, when I use this to iterate through the stream I see that
guile's memory utilization keeps growing until the iteration is
complete . I'm using guile 1.6.8 (also tested 1.8.7) on linux. I
observe the memory utilization under top.
I tried the same thing with plt-scheme/racket and it did not show a
similar leak i.e .the memory growth was capped at a certain point
during the iteration. It did not grow beyond that point.

From a little more googling, it appears that a similar memory leak has
been discussed before but that investigation was not completed. Here
is the thread:
 http://sources.redhat.com/ml/guile/2000-03/msg00568.html

So my questions are:
1. Can it be confirmed that this is a leak in guile's garbage collection?
2. Are there any workarounds (for instance doing an explicit "(gc)"
somewhere in the definitions?
3. Any pointers on fixing the underlying issue?
4. I noticed that streams in guile (ice-9 streams) were not
implemented in the SICP way. In-fact they were implemented in a way
that makes recursive definitions impossible. Was this intentional?

Some code to illustrate what I'm trying to do:

Simply print all s-expressions in a file to another as follows :
(let* ((outport (open-output-file <OUT-FILE-NAME>)))
  (stream-for-each (lambda (x) (pretty-print x outport))
                   (port->stream (open-input-file <IN-FILE-NAME>) read)))

where port->stream is:
(define (port->stream port readproc)
  (cons-stream (readproc port) (port->stream port readproc)))

(defmacro cons-stream (a b)
  `(cons ,a (delay ,b)))

(define stream-null? null?)
(define the-empty-stream '())
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))

(define (stream-for-each proc s)
  (if (not (stream-null? s))
      (begin (proc (stream-car s))
             (stream-for-each proc (stream-cdr s)))))

I get the same behavior with the following definition:

(define-syntax cons-stream
  (syntax-rules ()
    ((_ ?car ?cdr) (cons ?car (delay ?cdr)))))

Thanks
Abhijeet

Re: Possible Memory Leak with stream-for-each

[Andy Wingo]

On Mon 19 Jul 2010 20:08, Abhijeet More <abhijeet.more@gmail.com> writes:

> 1. Can it be confirmed that this is a leak in guile's garbage
> collection?

Hi,

I can confirm this for Guile 1.9/2.0 at least. Gross... The code that I
used was, to first generate a test file:

  (with-output-to-file "/tmp/test"
    (lambda ()
      (let lp ((n 0))
        (if (< n 10000000)
            (begin
              (write '(foo))
              (lp (1+ n)))))))

Then execute the following code:

  (define stream-null? null?)
  (define the-empty-stream '())
  (define (stream-car stream) (car stream))
  (define (stream-cdr stream) (force (cdr stream)))
  (define-syntax cons-stream
    (syntax-rules ()
      ((_ ?car ?cdr) (cons ?car (delay ?cdr)))))

  (define (stream-for-each proc s)
    (if (not (stream-null? s))
        (begin (proc (stream-car s))
               (stream-for-each proc (stream-cdr s)))))

  (define (port->stream port readproc)
    (cons-stream (readproc port) (port->stream port readproc)))

  (stream-for-each
   identity
   (port->stream (open-input-file "/tmp/test") read))

And I see memory usage explode, yes, at the REPL, even if I disable
position recording via (read-disable 'positions).

> 2. Are there any workarounds (for instance doing an explicit "(gc)"
> somewhere in the definitions?
> 3. Any pointers on fixing the underlying issue?

I don't know. Ludovic? :) You have certainly found a bug, though. We
probably won't look into it for 1.8, but we will certainly try to fix it
for 2.0 (soon!).

> 4. I noticed that streams in guile (ice-9 streams) were not
> implemented in the SICP way. In-fact they were implemented in a way
> that makes recursive definitions impossible. Was this intentional?

I don't know TBH. SICP streams do have a problem, amply explored in
http://www.cs.rice.edu/~taha/publications/conference/sml98.pdf; but
beyond that, I don't know.

Perturbedly yours,

Andy
-- 
http://wingolog.org/

Re: Possible Memory Leak with stream-for-each

[Tristan Colgate]

FWIW, the code in srfi-41 now works out of the box (thanks to some
recent r6rs library fixes), with the exception of all the negative
unit tests, due to some exception handling issue I didn't really look
at. I don't know if it still shows the memory leak though.

On 20 July 2010 21:36, Andy Wingo <wingo@pobox.com> wrote:
> On Mon 19 Jul 2010 20:08, Abhijeet More <abhijeet.more@gmail.com> writes:
>
>> 1. Can it be confirmed that this is a leak in guile's garbage
>> collection?
>
> Hi,
>
> I can confirm this for Guile 1.9/2.0 at least. Gross... The code that I
> used was, to first generate a test file:
>
>  (with-output-to-file "/tmp/test"
>    (lambda ()
>      (let lp ((n 0))
>        (if (< n 10000000)
>            (begin
>              (write '(foo))
>              (lp (1+ n)))))))
>
> Then execute the following code:
>
>  (define stream-null? null?)
>  (define the-empty-stream '())
>  (define (stream-car stream) (car stream))
>  (define (stream-cdr stream) (force (cdr stream)))
>  (define-syntax cons-stream
>    (syntax-rules ()
>      ((_ ?car ?cdr) (cons ?car (delay ?cdr)))))
>
>  (define (stream-for-each proc s)
>    (if (not (stream-null? s))
>        (begin (proc (stream-car s))
>               (stream-for-each proc (stream-cdr s)))))
>
>  (define (port->stream port readproc)
>    (cons-stream (readproc port) (port->stream port readproc)))
>
>  (stream-for-each
>   identity
>   (port->stream (open-input-file "/tmp/test") read))
>
> And I see memory usage explode, yes, at the REPL, even if I disable
> position recording via (read-disable 'positions).
>
>> 2. Are there any workarounds (for instance doing an explicit "(gc)"
>> somewhere in the definitions?
>> 3. Any pointers on fixing the underlying issue?
>
> I don't know. Ludovic? :) You have certainly found a bug, though. We
> probably won't look into it for 1.8, but we will certainly try to fix it
> for 2.0 (soon!).
>
>> 4. I noticed that streams in guile (ice-9 streams) were not
>> implemented in the SICP way. In-fact they were implemented in a way
>> that makes recursive definitions impossible. Was this intentional?
>
> I don't know TBH. SICP streams do have a problem, amply explored in
> http://www.cs.rice.edu/~taha/publications/conference/sml98.pdf; but
> beyond that, I don't know.
>
> Perturbedly yours,
>
> Andy
> --
> http://wingolog.org/
>
>



-- 
Tristan Colgate-McFarlane
----
  "You can get all your daily vitamins from 52 pints of guiness, and a
glass of milk"

Re: Possible Memory Leak with stream-for-each

[Ludovic Courtès]

Hi!

The leak you describe seems to be that depicted under “Why the space
leak occurs” at <http://srfi.schemers.org/srfi-45/srfi-45.html>.

Am I right?

Thanks,
Ludo’.

Re: Possible Memory Leak with stream-for-each

[Abhijeet More]

On Sat, Jul 24, 2010 at 12:13 PM, Ludovic Courtès <ludo@gnu.org> wrote:
> Hi!
>
> The leak you describe seems to be that depicted under “Why the space
> leak occurs” at <http://srfi.schemers.org/srfi-45/srfi-45.html>.
>
> Am I right?

I don't think so. The leak described in SRFI-45 is due to a naive
implementation of stream-filter on SICP-like streams (odd or even).
SRFI-45 describes a way to implement streams so that the leak does not
occur with the naive implementation of stream-filter.

The leak I'm referring to happens with *stream-for-each*.
*stream-filter* is not involved in any way.
I doubt if that is the problem I'm describing - especially since the
same code doesn't cause a leak in PLT Scheme/Racket.

Thanks
Abhijeet

Re: Possible Memory Leak with stream-for-each

[Abhijeet More]

On Sat, Jul 24, 2010 at 12:32 PM, Abhijeet More <abhijeet.more@gmail.com> wrote:
>
> I don't think so. The leak described in SRFI-45 is due to a naive
> implementation of stream-filter on SICP-like streams (odd or even).
> SRFI-45 describes a way to implement streams so that the leak does not
> occur with the naive implementation of stream-filter.
[snip]

Now that I think about it though - it may be worth investigating
whether the stream-for-each implementation causes a similar
ever-growing sequence of pending-promises.
I'll see if this is the case.
The reason I feel strongly that this is not the problem is that the
same implementation (including cons-stream) does *not* cause a leak
with PLT Scheme/racket.
Thanks
Abhijeet

Re: Possible Memory Leak with stream-for-each

[Andy Wingo]

On Sat 24 Jul 2010 18:46, Abhijeet More <abhijeet.more@gmail.com> writes:

> The reason I feel strongly that this is not the problem is that the
> same implementation (including cons-stream) does *not* cause a leak
> with PLT Scheme/racket.

I think it's probably our bug, but I haven't had time to examine it
thoroughly.

Andy
-- 
http://wingolog.org/

Re: Possible Memory Leak with stream-for-each

[Abhijeet More]

On Mon, Jul 26, 2010 at 5:36 AM, Andy Wingo <wingo@pobox.com> wrote:
>
> I think it's probably our bug, but I haven't had time to examine it
> thoroughly.

FWIW - I tried using the SRFI-45 reference implementation for delay
and force (as-is from the SRFI reference implementation) and got the
same behavior.

To debug this further are there any useful places in the
stream-for-each implementation that I could do a gc-stats from? Or
would we need to look at the C implementation?

Can anyone suggest good starting points for this?
Thanks
Abhijeet

Re: Possible Memory Leak with stream-for-each

[Andy Wingo]

Hi Abhijeet,

On Fri 30 Jul 2010 02:38, Abhijeet More <abhijeet.more@gmail.com> writes:

> To debug this further are there any useful places in the
> stream-for-each implementation that I could do a gc-stats from? Or
> would we need to look at the C implementation?
>
> Can anyone suggest good starting points for this?

We started poking this a little at the GNU Hackers Meeting last
weekend. I say "we" but it was really Tibi (copied on the mail) who was
doing most of the work.

We printed out the object-address of the stream at the start of the
iteration, then ctrl-C'd in GDB somewhere in the middle. We then called
GC_print_heap_obj on that address and it printed as a two-word
object. We scm_display'd the address, and it was not a stream. (It was
used for something else.)

So, it's not the case that the beginning of the stream was being held on
to. Which is a bad thing -- it means that somehow something in the
middle was being held on to.

To really track this down we need a heap profiler. To make a heap
profiler, we need to hack libgc. libgc has some of the things we need
already, but some are only present in debug builds, which is
ridiculous -- one should always have the ability to profile the heap. We
need to figure out which value is being misidentified as a pointer to a
heap-allocated stream-pair.

That is my analysis anyway. The next step is to be able to expose the
back-pointer graph from libgc, and write analysis tools to figure out
which non-stream objects point to a stream.

Andy
-- 
http://wingolog.org/

Re: Possible Memory Leak with stream-for-each

[Abhijeet More]

On Sat, Jul 31, 2010 at 7:48 AM, Andy Wingo <wingo@pobox.com> wrote:

[snip]

> To really track this down we need a heap profiler. To make a heap
> profiler, we need to hack libgc. libgc has some of the things we need
> already, but some are only present in debug builds, which is
> ridiculous -- one should always have the ability to profile the heap. We
> need to figure out which value is being misidentified as a pointer to a
> heap-allocated stream-pair.
>
> That is my analysis anyway. The next step is to be able to expose the
> back-pointer graph from libgc, and write analysis tools to figure out
> which non-stream objects point to a stream.

[snip]

Andy,
Thanks! That's a great answer!
I'll see what I can do with these guidelines.
Abhijeet

Re: Possible Memory Leak with stream-for-each

[Abhijeet More]

On Sat, Jul 31, 2010 at 4:16 PM, Abhijeet More <abhijeet.more@gmail.com> wrote:

> Andy,
> Thanks! That's a great answer!
> I'll see what I can do with these guidelines.


Apologies - I haven't had a chance yet to look into using the libgc
library as you suggested.
Would it be possible to use valgrind massif instead of changing the
code to see what we need?

Also: I was trying to write an implementation that did not leak and
came across the following.
When I redefine "delay" and "force" as follows:
(defmacro delay (expr)
  `(make-promise (lambda() ,expr)))

(define (make-promise proc)
  (lambda() (proc)))

(define force
  (lambda (promise)
    (promise)))

there is no memory leak. I see a leak again when I introduce
memoization into the "make-promise" implementation above.
To me it looks like that the leak that we see is caused by memoization
of the "promise" objects created by guile's default version of force
and delay. At what point does guile decide that a memoization isn't
required anymore?
At this point I don't know guile code well enough to say this for sure.

Thanks
Abhijeet

Re: Possible Memory Leak with stream-for-each

[Tibi Turbureanu]

Hello guys,

On Sat, Jul 31, 2010 at 01:48:27PM +0200, Andy Wingo wrote:
> So, it's not the case that the beginning of the stream was being held on
> to. Which is a bad thing -- it means that somehow something in the
> middle was being held on to.

Andy, I remember you said at GHM that we might not use libgc correctly.

Related to this, I found some tips in README.QUICK:

[quote]
Replace calls to malloc by calls to GC_MALLOC, and calls to realloc 
by calls to GC_REALLOC.
Define GC_DEBUG before including gc.h for additional checking.
[\quote]

We also have GC_malloc_* calls in Guile and maybe we should have only
GC_MALLOC_* calls so that the debugging mode can work (just defining
GC_DEBUG before including gc.h gives a segfault).

There is also a warning:

[quote]
Do not store the only pointer to an object in memory allocated
with system malloc, since the collector usually does not scan
memory allocated in this way.
[/quote]

But I haven't studied the code yet to tell if we respect this.

What do you guys think?

Tibi

Heap profiler

[Ludovic Courtès]

Hello!

Andy Wingo <wingo@pobox.com> writes:

> To really track this down we need a heap profiler. To make a heap
> profiler, we need to hack libgc.

As a start, I suggest looking at these:

  - http://thread.gmane.org/gmane.comp.programming.garbage-collection.boehmgc/3392

  - “Understanding Memory allocations of Scheme Programs”, Serrano &
    Boehm, 2000, http://www-sop.inria.fr/mimosa/fp/Bigloo/bigloo-5.html

I miss ‘gc-live-object-stats’...

Thanks,
Ludo’.

Re: Possible Memory Leak with stream-for-each

[Ludovic Courtès]

Hello!

I believe this patch fixes the problem:

  http://git.sv.gnu.org/cgit/guile.git/commit/?id=f57fdf07d6374028f35bcb1ee748a94022deda6d

Basically ‘force’ was leaking memory because it uses ‘lock-mutex’, which
was the culprit (!).

Julian: Could you please review this patch?

Thanks,
Ludo’.

Re: Possible Memory Leak with stream-for-each

[Julian Graham]

Hey Ludovic,


On Thu, Sep 2, 2010 at 8:49 AM, Ludovic Courtès <ludo@gnu.org> wrote:
> I believe this patch fixes the problem:
>
>  http://git.sv.gnu.org/cgit/guile.git/commit/?id=f57fdf07d6374028f35bcb1ee748a94022deda6d
>
> Basically ‘force’ was leaking memory because it uses ‘lock-mutex’, which
> was the culprit (!).
>
> Julian: Could you please review this patch?

Sure.  That looks alright to me, especially in light of our discussion
on IRC.  Summary: The list of held mutexes is not weak; it's a list of
weak-car pairs.  So if a particular mutex in the list goes away, the
pair's still hanging around.  The patch introduces more explicit
cleanup of that mutex list.  (Thanks for clarifying that!)


Regards,
Julian

Re: Possible Memory Leak with stream-for-each

[Andy Wingo]

On Thu 02 Sep 2010 05:49, ludo@gnu.org (Ludovic Courtès) writes:

> Basically ‘force’ was leaking memory because it uses ‘lock-mutex’, which
> was the culprit (!).

You are a superhero, Dr. Courtès!!

A
-- 
http://wingolog.org/