Re: Garbage Collection

["Thatcher Ulrich" <tu@...>]

On Oct 30, 2002 at 09:51 -0300, Roberto Ierusalimschy wrote:
> > "Lins's algorithm is lazy in the sense that the mark-sweep garbage
> > collection is performed on demand.  [...big snip...]  Like
> > generational garbage collection, Lins's method works best when
> > side-effects are comparatively rare, for example for programs written
> > in a functional style.  Its success also rests on the assumptions that
> > the great majority of nodes are uniquely referenced and can be
> > reclaimed without resort to garbage collection; and that the
> > sub-graphs traversed are sufficiently small to make the garbage
> > collection delay small.
> 
> Most of these are not true in Lua: most programs use mainly side-effects
> to do their jobs, and many nodes have more than one reference (because a
> single assignment or parameter passing duplicates the reference). Maybe
> that's why I forgot about it ;-)

Yeah, I agree it doesn't match Lua's requirements too well.

> In a related subject: I don't want to go into the merits of reference
> counting x games, but I feel that a correct implementation of reference
> counting in Lua is not going to be simple. For instance, everytime Lua
> pops its stack (a simple "L->top--", for instance) it is destroying
> references. The stack is pervasive in Lua's implementation, and to
> control correctly all these pushs and pops seems a difficult task. (More
> difficult yet if there is any concern with performance...)

You're right, popping the stack destroys a reference.  You can defer
the actual destruction of the reference, though, until something is
pushed into that slot in the stack, or until some later convenient
time, and destroy all the extra references at once.

I believe an incremental mark-sweep, and possibly also generational,
suffers from a similar problem: you must have a write-barrier to
enforce your invariants.  Any time you change a reference, some GC
checks must be done.  The different algorithms and variations have
different invariants, so there may be "safe" situations when you can
change references, but of course this is what makes these things so
complicated.

I think a generic write-barrier macro used throughout the Lua core, as
Russell Webb is suggesting, would be good for GC experiments.
Actually, I just looked at lobject.h in 5.0-alpha, and I think the
infrastructure is already in place:

sethvalue() and the other similar macros can serve as the write
barrier.  Just redefine those macros to the write-barrier code
(possibly a function call).

Does the Lua core always use the set* macros to change a Value's
state?  If so, then we're in good shape -- I think pretty much any GC
can be added without touching much of the rest of the core, by
defining those macros appropriately, and adding the necessary support
code.

-- 
Thatcher Ulrich
http://tulrich.com