RE: Best Ref-counting algorithms?

Torben Morgensen said:


> 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.


Reference counting is used extensively in the Meta-S parsing engine,
but I don't really think of it as a "garbage collection" mechanism in
the contexts it is used. It gives huge performance gains (not losses)
in those contexts, even though there are many references (through
pointers).


The copy-on-write semantics of RC, for instance, are an ideal
complement to parse memoization, since memoization of a parse requires
the repeated storing and fetching of intermediate parse trees, and RC
effectively reduces this operation to wrap-and-count rather than a
full, deep copy of what can be thousands upon thousands of small
objects. In conjunction with segmented memory allocation, memory
fragmentation over long runs where many small objects are created and
destroyed is also reduced considerably. The wrappers, being fixed in
size even when their underlying data may be of varying length (such as
in the case of string objects), are very effectively managed by
segmented memory allocation, in pools where all segments are of
identical length.


Which to say, objects that are pretty much state-constant after
construction (such as parse tree nodes) but are often copied and often
referenced are good candidates for RC, I have found. Reference
counting used in this way is effectively a form of implicit caching
rather than garbage collection.


I have also found that RC also greatly reduces memory complexity of
large grammars. For instance, huge tries (think hundreds of thousands
of entries), when wrapped in RC, no matter where referenced, can
behave as if owned by the code that needs them (thereby avoiding
explicit sharing), but are only held in memory once. The complexity of
the client code is reduced because it does not have to manage sharing
in any way and can behave as if it owns the trie (or whatever object
is RC'd), but the memory allocation, being lazy, improves speed and
reduces footprint overall.


Just my experience, others' mileage may vary.


--
Quinn Tyler Jackson

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