Re: Incremental garbage collection coming to Lua soon?

[David Jeske <jeske@...>]

On Wed, Jul 30, 2003 at 03:57:13PM -0700, Mark Hamburg wrote:
> If going this route, I would recommend only counting references from tables
> and closures and avoid counting references from the stack together with a
> zero-ref-count list that lists objects that either have no references or are
> only referenced from the stack. Dealing with refcounts while storing to
> tables is probably a relatively small hit and the stack is already scannable
> for the existing GC.

This has the drawback that it makes finalizer semantics less
immediate, but I agree it does have the potential for increased
performance.

On Wed, Jul 30, 2003 at 10:49:50PM -0700, Taj Khattra wrote:
> see http://lua-users.org/lists/lua-l/2003-05/msg00444.html and its
> follow-ups for a previous discussion from a few months ago.

Thanks for this pointer. Here are a few other datapoints for your
ref-counting is good list:

1) Refcounting work is proportional to mutator changes, not heap
   size. Every copying or sweeping collector I've used breaks down as
   the heap gets even moderately big.

2) The most popular automatic memory management systems use reference
   counting including: Visual Basic, COM, Perl, and Python.

3) Pausing collectors are a constant nusance holding back the
   capabilities of languages with garbage collection.

4) The most popularly used sweeping/copying collectors exist for Java,
   which is notorious for it's pauses in interactive apps. 

5) One of the most commonly used techniques for tracking liveliness of
   shared datastructures in C/C++ programs is manual reference
   counting.

6) Reference counting cycle finders are basically mark-and-sweep
   collectors. In systems with large heaps and/or large allocation
   throughput, making incremental collectors perform is a
   challenge. Reference counting reduces pressure on the garbage
   collector by making many objects collectable without sweeping. It
   also allows the mark-sweep algorithm to ignore objects which can't
   hold references to other objects. 

7) In an incremental mark-sweep collector based on coloring, the
   mutator-marking scheme is doing work which is sufficiently like
   reference counting anyhow.

8) Copying/compacting collectors optimize something which isn't
   generally a problem for most programs (allocation time and
   fragmentation) and create side-effects which are unacceptable for
   many programs (uncontrolled pauses).

9) Copying/compacting collectors which use handles to facilitate
   object movement increase the overhead of using all pointers due to
   the the handle-indirection cost. For most programs this is worse
   than the increased mutator cost of reference counting.

> inferno/limbo uses a similar hybrid scheme: ref counting + background
> cyclic collector.  see http://lua-users.org/lists/lua-l/2003-05/msg00496.html.

At a glance it look very interesting. I'll enjoy reading it, thanks!

-- 
David Jeske (N9LCA) + http://www.chat.net/~jeske/ + jeske@chat.net