Re: Best Ref-counting algorithms?

"Hans Aberg" <haberg_20080406@math.su.se> wrote in message
> Christoffer LernC6 wrote:
>> I'm looking into GC using ref-counting.
>>


<snip>


> It depends on what resources you want to collect, and what
> implementation language you are choosing. If resources that should
> take a place at a specific time, like open files that should be closed
> in a C++ style destructor, that may force ordinary reference counts,
> as it may be hard to detect the point in time the last reference is
> used.


agreed.
long ago, resource-management problems of this sort were a real pain in my
case...




> A quick scan on the first paper above gives the impression that it
> uses a mark-scan from the root set. If the implementation language is
> C++, the problem is that there is no good way to find this root set
> (but perhaps in the next revision); the language does not
> cooperate. But if one can find it, any type of GC would do.
>


not necessarily "any" type of GC.


in particular, for more subtle reasons, I am not "particularly" sure I would
want to see reference-counting mixed with a conservative GC (thinking about
it, it could work though, so long as one keeps the ref-counts correct and is
careful when mixing ref-counted with non-refcounted memory...).


the problem then is with precise GC (and especially ref-counting) is that it
is a pain to use without explicit compiler support (such as in C). to make
it safe (and especially thread-safe), one ends up having to wrap nearly
everything in macros, manage roots, ... and it gets very tedious...


eliminating the precise GC aspect would at least make it less painful, as it
would eliminate the need to manage roots, but would still leave a whole lot
needing to be done via macros (such as assignments, ...).


if added to a GC, it would probably make sense to add it as an optional (and
explicit) feature (such as, when allocating an object, it is declared as
having a ref-count). it would also be necessary to be very careful where
ref-counted objects are used (such as, not freely putting them in memory
which could be destroyed while failing to update the ref-counts).


non-ref-counted objects would simply ignore ref-counting operations (they
would either be outside the refcount system, or initially created with a
count of "many").




then again, the GC could have a default conservative "destroy handler":
if destroying an object, if it looks like a reference, assume it is a
reference and update the count.


the problem here though, is that with a conservative GC there may be "false
positives", or, in this case, adjusting the ref-counts for objects which
were only being referenced by accident.


it is actually safer to not bother, such that if an object is destroyed and
the counts get out of sync, at least greater values are better than lesser
ones (as then, the object is left for the GC, and not freed prematurely).




then is conservative GC as is usual for conservative GC:
look for pointers in the data and bss sections;
look for pointers in the stack(s);
...




I could do this in a later revision of my existing GC, where I would drop
the thus far unused "precise" mode, allowing me to reuse the all important
bits for conservative refcounting.


alternatively, I could leave "precise mode" intact, but have the relevant
bits be located in the object header (vs the cell-bitmap, which only has 8
bits in which to manage the entire allocator and GC state, and which also
contains the ref-count for precise objects, where the same field is used
both for a ref-count and to identify the basic GC type).


putting the info in the obj-header would avoid me having to mess with the
core allocator machinery, and I currently have a "not very important" 16-bit
field, with which to mooch off a few bits for a refcount (while still
leaving the object marked as "conservative" in the bitmap). (note that the
object header is 8 bytes, with 32-bits as the size, and effectively limiting
objects to 1GB, where I may later use the top-2 bits to flag different
header layouts, such as possibly a header with a 64-bit size, and another
mini-header for small objects).


or such...




> The approaches might be combined: reference counts for the
> destructors, and another GC to collect the memory resources (with
> finalizers).
>


agreed, a good summary...

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