Re: Garbage collection

["Thatcher Ulrich" <tu@...>]

On Oct 27, 2002 at 04:35 -0000, tom7ca wrote:
> > No need to get religious. M&S may be appropriate for you but not for
> > problems like ours. We have no idle time. 
> 
> As I said, the current Lua collector may well not work for you. 
> So, something needs to be done.  The question is: what?
> 
> > Reference counting spreads the collection hit. 
> 
> The problem is that it doesn't in general.  Reference
> counting can give you worse collection hits than even
> Lua's simple garbage collector, because a single assignment
> can result in very large numbers of objects becoming
> unreferenced.

A couple observations:

1) David's reference-counting system collects incrementally, based on
   what he's said so far.  So it's not true, as far as I can tell,
   that his system can cause bad collection hits.

2) You are correct that the traditional reference-counting approach
   (delete an object when its last ref is released) can potentially
   cause huge chains of objects to be deleted.  I.e., this is the case
   when you have a large tree of objects, which is rooted at a single
   global variable, and you set that variable to nil.  However,
   whether this is actually a problem is definitely application- and
   program-dependent.  In the specific case of game development,
   traditional reference counting is very common in C++ engines, and
   very effective (in my experience).  The "bad collection hit" tends
   to occur exactly where you want it to: when you're trashing the old
   "level" (i.e. big chunk of game content), and getting ready to load
   the next one.

   If this is actually a problem in practice, it's very easy to fix:
   just put unreferenced objects on a "garbage list", to be freed
   incrementally.

> If you need real-time performance or soft real-time performance,
> the way to do it is to implement a real-time or soft real-time
> memory manager.  But reference counting isn't one of those, 
> and implementing it for that purpose is a waste of time.

Well, in the specific case of game development, based on my experience
and discussions with other game developers, I think you're giving bad
and unfounded advice here.  If you have real-world experience to the
contrary, I'm all ears.

The real-time requirements of game programs may not fall squarely
under your definitions of hard or soft real-time.  I wrote some notes
about it here:

http://lua-users.org/wiki/GarbageCollectionInRealTimeGames

(I just added the last note, about reference counting.)

> Implementing a real-time or soft real-time garbage collector
> isn't all that hard.  Why not just solve the problem and
> do things right?

Well, it's not trivial, either.  But PaulV posted a patch that does
incremental mark-and-sweep.  See archives for a link.  However, it
still needs some bug-fixing.  I think it would be great if people
tried this patch and helped fix the bugs.

On the other hand, the average game developer might be more likely to
adopt a reference-counting approach, for two main reasons 1) it's
straightforward and familiar to many game programmers (so they
understand the tradeoffs, and what bugs look like), and 2) it's more
deterministic, so bugs in the GC tend to be easier to find and fix.

-- 
Thatcher Ulrich
http://tulrich.com