From: Ken Bloom <kbloom@...>
Date: 2006-10-24T22:55:20+09:00
Subject: Re: Ruby's garbage collector...

On Tue, 24 Oct 2006 04:54:04 +0000, Just Another Victim of the Ambient
Morality wrote:

> Is there a name for Ruby's garbage collecting strategy?
>     I'm on a web forum and the topic of garbage collection came up. 
> There's a claim that you can never make a "perfect" garbage collector.  In 
> other words, there will always exist (pathological) conditions where your 
> collection strategy will fail to find inaccessible objects.  At least, 
> that's my best understanding of the claim and it strikes me as... false.  I 
> can understand that the task is non-trivial but simply impossible?  Can 
> that be right?
>     Furthermore, according to some, Java (a friendly Ruby competitor) is 
> incapable of collecting, specifically, circular references.  I was just 
> wondering if Ruby had the same limitation?
>     Thank you...

If it's mathematically impossible for a garbage collector to find every
unused object, I certainly wasn't told about it when I took compilers
class a couple years ago.

AIUI, Java uses mark-and-sweep garbage collection just like Ruby, and both
can handle circular references. The downside to mark-and-sweep garbage
collection is the fact that mark-and-sweep can take a while at random
points in the program, so it's not advisable for real-time programming,
and could cause noticable delays in interactive programs. It also means
that objects holding other resources (like file handles) may keep those
resources open indefinitely if they are not manually closed. Ruby handles
this by allowing you to use a block to scope the sue of such resources,
such as

open("file") {|f| ... } # after the block, f is now closed.

Reference counting (used by Perl) keeps a count of how many pointers there
are to each object and frees those objects when the reference count
reaches zero. This can't free circular references because every object in
the circle has a pointer to it from something else in the circle. The
solution when using this kind of system is to keep circular structures
encapsulated in some other object which is written in such a way as to
break the cycle when its reference count drops to zero (in Perl where all
pointers are reference counted), or which can use uncounted pointers
for the circular stuff can take care of disposing of the objects itself (in
C++ where reference counting requires you to create a special pointer
class like a ref_ptr<T>). The advantage to this method is that you know
exactly when your objects are disposed, it works well across processes
(for example COM uses it), and it can be mixed with uncounted code quite
easily (as I mentioned regarding C++).

-- 
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
I've added a signing subkey to my GPG key. Please update your keyring.