Re: garbage collectors

[Maciej Stachowiak <mstachow@mit.edu>]

> 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.)

OK, this is possible, but it i shighly unlikely that the list will get
misidentifdied as live in the first place.

> 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.

Not true, only if the stack continues to have a false pointer to
it. There'd have to be such a false pointer on the stack on the fixed
portion of the stack. Only the C stack is conservatively scanned in
Guile, so the probability of such a misidentification, in partiular of
a persistent one, is low. Even this low probability problem could be
avoided by being marking some initial portion of the stack that should
not be scanned conservatively, but I think there is no need for even
that. 

Further, the list presumbaly shrinks at the end when you pop the queue
as well, and it would probably be easier to implement pop to remove
the cell at the head of the list anyway.

In any case, my window manager with an embedded Guile interpreter has
run for days or weeks at a time, and I've never seen it grow without
bound. Admittedly, this is not as big an app as (X)Emacs, but I've run
it for longer than most emacs invocations tend to last.

 - Maciej Stachowiak