Re: Best Ref-counting algorithms?

GPS <georgeps@xmission.com> writes:


> Torben Cgidius Mogensen wrote:
>
>> Christoffer Lernv <lerno@dragonascendant.com> writes:
>>
>>> If one would like to implement a fast GC using refcounting, should I
>>> implement something like in those papers, or are there better
>>> algorithms out there?
>>
>> If you want to implement a fast GC, you should not use refcounting.


> Reference counting is often more efficient in general than other GC,
> especially with modern computer systems, and this statement is
> dependent on a variety of factors.


> If a GC results in page transfers to/from the disk, then it will
> drastically slow down the program, and system.


> If a GC follows the roots, any pages that are stored in virtual
> memory on a disk will be transferred back into RAM, so as the
> program progresses it may experience significant pauses from
> transfers at unexpected times.


> Reference counting does not require scanning all roots.


The root set is typically fairly small compared to the heap, at least
in languages that use heap allocation a lot (such as OO languages and
functional languages), so having to scan the full root set is not a
major overhead. And with generational GC you can often do minor
collections while staying inside the cache.


> Reference counting (RC) in and of itself does not eliminate leaks.


Nor does any other automatic reclamation method -- liveness is
undecidable, so any automatic method must be conservative and leave
dead stuff around.


> Reference counting can require more memory than other types of GC,
> because a container is usually used that contains a refcount, and a
> union of some primitive storage for type(s).


While the counter is extra space, I don't think it is significant.
One machine word is sufficient, so it will only be significant for
very small structures. But the fact that objects stay in place after
allocartion and are freed to a free-list means that you either need
uniformly sized objects (like in LISP) or will get fragmentation.
This problem is shared with all non-compacting GCs.


> Without reference counting it is not uncommon for another type of GC to
> leak. Most operating systems use a C API, and when using threads, and the
> native API of the system, there can be races at times that are unexpected,
> or unexpected false references. Premature reuse of memory is often just as
> bad as a leak, and they both occur with most systems I know of that have
> used a form of GC.


Automatic GC should prevent premature reuse, otherwise it is buggy.


Torben

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