Re: Best Ref-counting algorithms?

"Torben "Fgidius" Mogensen" <torbenm@pc-003.diku.dk> wrote in message
> 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. The
> main problem with refcounting is that an assignment to a pointer
> variable (which would otherwise just be a register-to-register transfer)
> requires two memory reads, two memory writes and a conditional jump, so
> it stresses the memory system far more than most other GC algorithms.


I have some experience in compiling for this cases, and there are
special-case optimizations by which large numbers of reference-count
adjustments can be eliminated.


similarly, most code is not likely performance-bound by how quickly it can
assign pointers...




> Refcounts should, IMO, only be used in the following circumstances:
>
> - Operations on heap pointers are very rare, so even a slow GC doesn't
> matter in the overall picture.
>
> - You need hard real-time guarantees.
>
> - The heap is shared between processes/processors with no central
> control.
>
> So refcounts are fine for such things as shared libraries (you don't
> very often add or delete references to these), but for a functional or
> OO language where you have many small heap structures with short
> lifetimes, it will give massive overhead.
>


you mean vs filling the heap with garbage and waiting for a GC cycle?...


IME, GC+refcounts, in practice, gives far better net performance than GC by
itself (mostly as it mostly eliminates a much bigger cost: the whole GC
process), and has the advantage of avoiding awkward and annoying pauses
typically caused by a GC (these are not just for "hard real-time"
requirements, as these delays can be very noticable and annoying even in
soft real-time apps, where the GC may run and momentarily effect the "flow"
of the whole system...).




the main cost of ref-counting is actually that of writing code to use it
(absent explicit compiler support), and not any such conceptual performance
cost...

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