Re: Best Ref-counting algorithms?

"Hans Aberg" <haberg_20080406@math.su.se> wrote in message
> Christoffer LernC6 wrote:
>>> It depends on what resources you want to collect, and what
>>> implementation language you are choosing.
>>
>> I'm playing around with a ref-counting based (memory) GC for a
>> language I have yet to construct.
>
> But what language are you planning use for the implementation? If you
> choose C++, then it is hard to find the root set. Suppose you create
> object for use in your language; then global objects and those in th
> stack should be registered somehow for the tracing, but those on the
> heap should not, as the are live when they can be traced from the other.
>


for C and C++ and implementing custom languages, it is not really that much
of a problem in practice.


The main reason is that, since the person is writing the compiler
and/or interpreter, they can directly keep track of whatever
references may exist within their little VM-managed language, making
precise GC and ref-counting fairly easily (especially if, as has been
suggested, a single-threaded implementation is possible...).


I guess it may be noted that there is another possible strategy, namely that
one "could" try to implement their own scheduler (rather than using the OS
scheduler), such that the GC would be able to manage threads by itself (for
example, it could pause all its managed threads during GC).


as-is in my case, I use the OS scheduler, but otherwise create-threads/do
TLS/... via a GC-provided API mostly so that the GC knows about them.


in my case, this also wraps the threading mechanism, so that I can use the
same threads API/... on both Windows and Linux.




now, the great problems are if:
the language is "C-like" (AKA: with raw pointers and like);
one tries to have fine-grained integration with native code;
multithreading becomes involved (this quickly turns a simple GC into a big
mess);
the VM has an extensive C or C++ based utility library (mostly a problem as
then lots of code may end up having to use the GC from C, which can become
very painful, and error prone as one may end up invariably mis-handling
memory references "here and there", which can be disasterous with precise GC
and refcounting);
...


actually, in practice "external integration" has been the main killer of
precise GC's in my case, where typically one will make a language or
interpreter with the intent of either operating it from C-land, or using it
to interface with or control stuff in C-land.


however, the choice in GC strategy becomes a major problem, as it
effectively creates a fragile wall with the outside world, and the effort
required both to maintain this wall, and to allow interfacing through this
wall, can often become terribly awkward.




so, more often, I have ended up falling back to conservative GC, if
anything, because it makes interfacing with the outside world less
problematic...


however, ref-counting+conservative GC may be worthwhile, as it may still
allow ref-counting without many of the complexities and costs of precise GC
(AKA: elaborate root management...).

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