Re: Garbage Collection

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

On Oct 29, 2002 at 03:39 -0300, Roberto Ierusalimschy wrote:
> > Everybody refers to reference counting as though it cannot catch cyclic
> > structures. Rafael Lins, whom I believe is now in the Departamento de
> > Electronica e Sistemas at the Universidade de Pernambuco, produced
> > some beautiful gc reference counting algorithms that do catch cyclic
> > structures. See "Cyclic Reference Counting with Lazy Mark-Scan", UKC
> > Technical Report 75 (1991). I believe he is now a world-expert on gc,
> > and has co-authored books on the topic. Seek advice from your eminent
> > compatriots, ye progenitors of Lua.
> 
> I know him quite well, but I could never "extract" from him the details
> of this algorithm about cyclic reference counting. Curiosly, his main
> book about garbage collection (which is, I believe, *the* book about
> garbage collection) is from 1996 (so, five years after that paper), but
> it does not include that algorithm...

This is a very good book, by the way, clear and comprehensive.  I
recently went back and skimmed the chapter on reference-counting, when
the topic popped up on the list here.  In my copy, there's a
discussion of Lins's algorithm on pages 62-67.  I haven't read it in
enough detail yet to summarize it, but I'll quote a few summary
sentences from the book:

"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.  The drawback is that Lins traces garbage
whereas standard mark-sweep algorithms trace only active cells.
Unfortunately, implementations of functional programming languages
generate copious amounts of garbage: collection rates of over 80
percent of the heap are common.  No thorough comparisons of cyclic
reference counting against other methods have been carried out."

My spin: reference counting plus an occasional mark-and-sweep to get
the cycles is perfectly valid and correct, and relatively simple.  The
problem is, the mark-and-sweep is just as bad as it is currently,
because you have to traverse the whole active heap.  That's where
Lins's algorithm comes in -- it's an attempt to make the occasional
cyclic collection less painful.

However, pragmatically speaking, in many games you may be able to code
defensively and avoid creating (much) cyclic garbage, and therefore
avoid having to call the mark-and-sweep at all; or only call it at
certain convenient times.  With the addition of weak tables in Lua,
this becomes especially feasible.

-- 
Thatcher Ulrich
http://tulrich.com