Re: Best Ref-counting algorithms?

"George Neuner" <gneuner2@comcast.net> wrote in message
> On Sun, 12 Jul 2009 13:41:59 -0700 (PDT), Christoffer Lernv
> <lerno@dragonascendant.com> wrote:


<snip>


> Reference counting is really primitive GC technology and you're better
> off not starting down that path unless your intent is to provide a
> library module that can't make assumptions about its environment.


I disagree.




> I haven't read Bacon's paper, but you'll note that Lins uses a marking
> scan as a backup to identify and break data cycles for the reference
> counter. Although the marking scan need not be run unless memory is
> tight, it significantly complicates the overall implementation.
>
> In fact, the marking scanner is nearly half the implementation of a
> more capable mark-sweep or mark-compact collector ... neither of which
> will have the reference counter's problems with circular data
> structures.


yeah.


my recommendation is to not complicate the ref-counting itself with
complicated cycle-breaking technology...




instead, a strategy which I have used, and which a number of other
"industrial strength" VMs use (the Python VM, and AFAIK SpiderMonkey, and
others...), is to combine together reference counting with something like a
mark/sweep or generational GC.


this way, the 2 systems work in parallel, with the ref-counting cleaning up
in the majority of cases, and falling back to the mark/sweep or generational
GC to deal with the situation of the heap having become full (often, with
all the cycles/... missed by the ref-counter).


the main advantage then is that the GC only runs a fraction as often, which
very quickly pays for itself with languages which spew garbage "like there
is no tomorrow" (where in a burst of activity one may find their heap filled
within a matter of seconds...).




of course, for other reasons, I have generally been moving to much more
memory and garbage-conservative implementation approaches, mostly trying to
find ways to avoid GC whenever possible (granted... one reason for this
being that, in general, my GC is not the most reliable GC around, and so
avoiding the GC running also helps avoid much of the risk of crashes...).


partly my GC's reliability issues though are because it is multithreaded,
and lacks a proper write barrier (I have a SW write barrier, but, ermm...
most of my code does not use it...).


it was actually a single threaded GC, but was made multithreaded through the
use of a few not-so-clean hacks a few years back...


as is, it almost makes sense to "re-engineer" the thing, AKA, to start with
a clean design and mostly new code, but while likely keeping the API intact.


(decided to leave out my elaborations on the idea...).






> If you're dead set on reference counting, you should investigate 1-bit
> reference counting. I don't have URL's to give you but they should be
> easy to find. The programming language is designed so that most data
> are not shared and then you only need a simple flag to say whether the
> item is shared and so needs special handling.
>


this sounds interesting, but I don't know much about this approach...

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