This is the mail archive of the guile@cygnus.com mailing list for the guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: garbage collectors


>From owner-guile@cygnus.com Mon Nov 17 16:27:47 1997
>To: Jens-Ulrik Holger Petersen <petersen@kurims.kyoto-u.ac.jp>
>cc: guile@cygnus.com
>Subject: Re: garbage collectors 
>Date: Mon, 17 Nov 1997 15:36:32 EST
>From: Maciej Stachowiak <mstachow@mit.edu>
>
> [...]
>I am not a Guile developer, but I do not think this is a serious
>problem. The way conservative GC works in Guile, the number of garbage
>objects that will fail to be collected is limited by the size of the C
>stack. Assuming the C stack does not grow without bound (if it does,
>you have more serious problems), then there will be, to first
>approximation, only a fixed memory overhead.

I may have missed something, but...

As I understand it, this is not necessarily correct; the memory
leaked can be unbounded.  Consider a program that processes data
managed by a queue, where the queue is represented as an ordinary
list, with head and tail pointers into that list.  (Assume that
popping an item off the front of the queue is nondestructive of
the list itself, i.e., bumping a pointer through the list, and
that new items are pushed onto the rear of the list destructively,
as is common for efficiency.)

If the conservative GC ever misidentifies any element
of the queue as live after it's dead, every element of the
queue will be considered live ever after.  Since the list
just keeps having new elements pushed onto the rear, but
never modified after that, it grows without bound and
the GC retains the whole thing.

On the other hand, the Cedar folks have had long-running programs
in their system for many years, and conservative GC generally
works well in practice.

As far as I know, the only programs that commonly misidentify
non-live data as live are those that have lots of effectively
random (e.g., compressed) data in conservatively-scanned memory.

> And the only objects that
>are likely to be protected forever when they should be collected are
>those that are aliased by the fixed portion of the C stack,
>i.e. whatever stack you build up before you go into your event
>dispatch loop. This is likely to be fairly small.
>
> - Maciej Stachowiak
>
>