Re: GC strategies, was Compiler writers will love this language

Eric wrote:
>
> > [Pure reference-count garbage collectors have problems with circular
> > structures that point to themselves.]
>
> I notice here, that you refer to "pure" reference-count GC, implying
> that some GC's are "hybrid" and combine reference-counting and some
> other scheme (supposeddly mark-and-sweep). How would such a hybrid GC
> work? any papers on the subject?


There are different reasons for hybrids:


- Two languages (e.g. Java & Objective-C) using different memory
management strategies. In this case, the GC takes a single for itself
when there are references to a refcounted object within the GC, and
releases the reference when there aren't any more. The refcounted
client creates a temporary GC root when it first refs a GC managed
object, and deletes the root when its refcount falls to zero.


- Reference counting to reduce memory usage of mark-and-sweep. When a
refcount falls to zero, the object is definitely freeable, so you can
free objects earlier than the GC would, if you'd rather use less memory
and you don't mind extra memory accesses, cpu cycles, synchronization,
etc..


- Mark-and-sweep to collect cycles. The mark and sweep runs
occasionally to collect any cycles that might have come up. This is
potentially identical in implementation to the previous bullet, but
running less often.,


- Cycle hunting - when a refcount falls to any value other than zero,
you can scan the graph rooted at that object to see if all of its
references are cyclic. This is usually deferred: a list of released
objects is kept, and periodically checked for cycles. This might be
more efficient than the previous bullet because it only has to scan
objects which were unreferenced but not deleted, but there isn't any
guarantee that it is (some apps may modify a lot of references without
causing objects to become unreachable, and to arbitrarily large data
structures), and you have to account for the overhead of the write
barrier (each pointer write potentially has to update the scanning list
as well as the reference count). This idea hasn't been generating many
papers in the last decade or two, but its get all the same variations as
mark-and-sweep (generational, concurrent, whatever).




You could, of course, combine regions with reference-counts garbage
collection as well to eliminate cycles, as long as the cycles aren't
stored in a place where the regions wont free them.


CU
Dobes

Return to the comp.compilers page.
Search the comp.compilers archives again.