From: Dan Sugalski <dan@...>
Date: 2002-07-04T03:44:02+09:00
Subject: Re: Ruby implementation Q's

At 2:53 AM +0900 7/4/02, Justin Johnson wrote:
>If I could just come up with a way of (quickly) detecting the moment an
>object isn't referenced anymore....

...lots and lots of people would want to be your friend. :) It's a 
tough problem.

With static languages such as C++, you can often detect at compile 
time whether an object has any sort of outside references. Objects 
allocated on the stack, or dynamically allocated objects for which 
only stack references exist (which is detectable at compile time) can 
be destroyed when a stack frame is cleaned up on scope exit.

For dynamic languages, such as Ruby, Python, or Perl, or for 
non-stack objects in static languages, you need a more active way to 
check for liveness. The two traditional ways--in fact, the only two 
ways that I know of--are reference counts and tracing from a root set 
of containers/object pointers.

Reference counting is simple. Every time you take a reference to an 
object you increment its refcount, and every time you delete a 
reference you decrement the refcount. If an object's refcount ever 
goes to 0, you can immediately destroy the object. Nice and 
deterministic.

Tracing, on the other hand, actively goes and checks to see if 
objects are alive. It starts with a set of "known" object references 
(core interpreter structures, the stack, and perhaps some global 
references) and sees what objects they point to, and what objects 
*those* objects point to, and so on. Eventually you run out of object 
pointers, and you declare everything that hasn't been pointed to dead.

The upside to reference counting is its determinism. You know exactly 
when something will be cleaned up, which is often rather nice. The 
downsides, though are significant.

Reference counting is remarkably expensive. You wouldn't think 
so--it's just an increment, or decrement and test operation. Those 
are cheap. The expense is threefold. First, you do that 
increment/dec&test a *lot*. Second, you need to allocate space for 
the refcount in your object, which makes the object larger and 
generally means it takes up more cache lines on the CPU, and bringing 
those in is more expensive than not bringing them in. (Doing 
something generally being more expensive than not doing something) 
Thirdly, it makes the code you execute larger (to accommodate the 
inc/dec code) which means routines are larger and use more chip cache.

Reference counting is also error prone, as *every* *single* *place* 
you can potentially take or drop a reference needs to have ref count 
mangling code. Miss it in one spot and either things die prematurely 
or live forever. Subtle bugs, and nasty ones to track down.

Finally, reference counting doesn't collect circular garbage. If A 
references B, and B references A, then A and B will live forever even 
if nothing else references either.

Tracing collectors, on the other hand, have a separate set of 
advantages and disadvantages.

First, they tend to be cheaper overall. Yes, a full trace run is 
reasonably expensive, however you do them relatively rarely, so the 
cost is normally less than for a refcount scheme over the lifetime of 
a program.

Second, they don't leave circular garbage. This can in some cases 
reduce the memory footprint of your program, or clean up objects that 
need active destruction sooner than they'd otherwise be cleaned up.

Finally, while they're a pain to write (BTDT, though it's really not 
that bad) they concentrate the GC code in a single spot, which makes 
errors easier to deal with.

The big downside to a tracing collector is the lack of determinism. 
You can't know when an object will be destroyed, and if you're 
counting on GC for timely destruction of objects representing scarce 
resources you may have those resources tied up longer than you might 
otherwise like.

There are some techniques to lessen the potentially extended lifetime 
of objects when using a tracing collector, but they increase the 
expense, so they're often not done, or done sparingly. (For example 
at sub exit, or block exit, or something) Generally traces are made 
on demand, when you run out of a resource (filehandles, memory, 
whatever) so that's less of an issue, but if users expect a 
particular behaviour--files closed on  block exit if there's no 
reference to the filehandle outside the block--it can be interesting 
to balance performance against user expectation.

I'd really, *really* recommend picking up a copy of _Garbage 
Collection_ by Richard Jones and Rafael Lins (Wiley and Sons 
publisher, ISBN 0-471-94148-4) if you want to dive into more detail.
-- 
                                         Dan

--------------------------------------"it's like this"-------------------
Dan Sugalski                          even samurai
dan@sidhe.org                         have teddy bears and even
                                       teddy bears get drunk