Re: garbage collection thoughts... again?!

[Thatcher Ulrich <tu@...>]

On Wed, 28 May 2003, Mark Hamburg wrote:

> I agree that reference counting can work well. I've used it extensively in
> some C++ projects and I'm using it while doing Cocoa development. On the
> other hand...
>
> * Cycles are more common than you might think. Imagine a view system with
> pointers from parents to their children and pointers from children to their
> parents. The work around in many systems is to sacrifice safety by choosing
> not to count some references. Other safe work arounds increase the
> complexity of the implementation.

Yeah, good points.  At work, with a C++ game engine, we use
ref-counting.  I have done a lot of thinking and reading about how to
do an incremental collector, but haven't come up with anything at all
practical (or cost-effective to write, for that matter).  So we
continue to use ref-counting.  We use the following strategies to deal
with the cycles problem.

* use a weak pointer when you don't "own" the other object.  E.g. a
  child node would have a weak pointer to its parent.  This requires
  some awareness on the part of the programmer of when to use a weak
  pointer, but at least is safe.

* use raw pointers when you don't "own" the object and are sure
  someone else does.  This works OK with many common game-programming
  patterns.  It requires awareness on the part of the programmer, and
  is not very safe.

* instrumentation to detect illegal cycles.  This greatly reduces the
  effort of maintaining the above strategies.

To go out on a limb a bit, to some extent I take issue with the idea
that cycles are very prevalent.  I'm not sure if this is true of
typical Lua programs.  I mean, there are the Perl and Python existence
proofs; two very popular languages that have lots of similarities with
Lua.  It would be interesting to know how big a problem cycles are
perceived to be by the Perl and Python communities.

> * The overhead of doing reference counting gets expensive for parameter
> passing on the stack. A lot of time can be wasted incrementing and
> decrementing reference counts. There are work arounds for this but they are
> generally more complicated than simple implementations of reference counting
> or they sacrifice safety.

We generally do this:

void SomeFunction(const SPtr<SomeObject>& ptr)
{
	// ptr is a reference to an already-existing SPtr<>, so there's
	// no ref inc/dec overhead in the function call binding.
}

This is safe and easy, in my experience.  In any case, most
incremental collectors will need a write-barrier, which in practice is
probably worse than inc/dec of a ref count.

> Mark-and-sweep is simple and reliable. Its downside is that it is slow to
> collect garbage and it is tricky to make incremental.

I think one of the biggest practical benefits of ref-counting, which
none of the other approaches offer, is determinism & predictability.
It's my impression that 90% of the GC questions that show up on the
list are due to problems with the GC not being predictable.  These
questions come from ordinary programmers with straightforward
practical problems and concerns, but the answers, unfortunately, tend
to be pretty subtle and not very comforting.  At least in my opinion.

On the other hand, reference counting is relatively easy to explain
and reason about.  I think that's a tremendous advantage by itself.

For example (using made-up library functions):

    do
      local write_handle = open_file_for_write("somename")
      -- dump some info into write_handle
    end
    -- using ref-counting, we can be 100% confident that the
    -- contents of write_handle have been collected here.  I.e.
    -- that the write buffer has been flushed and the file
    -- handle has been closed.  So now it's safe to do:
    local read_handle = open_file_for_read("somename")
    -- pull in data from read_handle

> That being said, I could see a case being made for investigating reference
> counting for Lua as an alternative to an incremental, generational, fully
> buzzword compliant garbage collector.

Yeah...  I guess if the Lua authors are far along with the
buzzword-compliant collector, then I'm happy.  Otherwise, I think it's
an interesting topic.  Unfortunately I don't have time to experiment
by writing code, but apparently I do have time to rant :)

-Thatcher