Asp Forum - Ruby's garbage collector...

Just Another Victim of the Ambient Morality

10/24/2006 4:54:00 AM

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...

12 Answers

???? ??????

10/24/2006 5:00:00 AM

On Oct 24, 2006, at 8:55 AM, Just Another Victim of the Ambient
Morality wrote:

> Is there a name for Ruby's garbage collecting strategy?
>
>

semi-conservative mark-and-sweep

Will Pugh

10/24/2006 5:39:00 AM

I do not know much about the Ruby Garbage collector, but I know Java can
easily collect circular references. Most modern Java VMs use
Generational garbage collection.

The only "garbage collection" technique I can think of right now that
fails to collect circular references is ref counting.

I'd be interested in hearing about what kind of "pathalogical"
conditions you are talking about, but my guess is that they do not
actually prevent collection of inaccessible objects. Normally, they
either increase response time or create additional memory overhead.

The claim that "there is no perfect garbage collector" can be
generalized to "there is no perfect general allocation model". Any
memory allocation contains a host of trade offs. Java is actually
pretty advanced in a number of these, if you look at either the JRockit
VM or the more modern Sun VMs.

--Will

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...
>
>
>
>

Will Pugh

10/24/2006 5:48:00 AM

Just in case you want to learn more, here is a pretty good survey of GC techniques.

ftp://ftp.cs.utexas.edu/pub/garbage/...

--Will

Will Pugh wrote:
> I do not know much about the Ruby Garbage collector, but I know Java
> can easily collect circular references. Most modern Java VMs use
> Generational garbage collection.
>
> The only "garbage collection" technique I can think of right now that
> fails to collect circular references is ref counting.
>
> I'd be interested in hearing about what kind of "pathalogical"
> conditions you are talking about, but my guess is that they do not
> actually prevent collection of inaccessible objects. Normally, they
> either increase response time or create additional memory overhead.
>
> The claim that "there is no perfect garbage collector" can be
> generalized to "there is no perfect general allocation model". Any
> memory allocation contains a host of trade offs. Java is actually
> pretty advanced in a number of these, if you look at either the
> JRockit VM or the more modern Sun VMs.
>
> --Will
>
> 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...
>>
>>
>>
>>
>

???? ??????

10/24/2006 6:04:00 AM

> 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.

Conservative garbage collectors can leave some unused data if it
seems to look like
used object, however, ruby garbage collector can leave objects, that
have references from current stack.
So, after some calls, stack will change and unused objects will leave.

I don't know, what are this ideas (about impossibility of perfect
collector) are based on.

> 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?

No, Ruby doesn't have this limitation and Sun Java machine (I don't
know about others) doesn't
have such limitation. Old Microsoft Java machine had this limitation,
because it used
only reference counting.
CORBA libraries have this limitation because of reference counting.

Python will not reclaim objects in circle with defined __del__
method. As ruby objects
have no destructors (finalizators), Ruby has no such problems.

Ken Bloom

10/24/2006 1:51:00 PM

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...
I've added a signing subkey to my GPG key. Please update your keyring.

Robert Klemme

10/24/2006 2:09:00 PM

On 24.10.2006 15:51, Ken Bloom wrote:
> AIUI, Java uses mark-and-sweep garbage collection just like Ruby,

In fact Java's GC is much more complex. It uses mark and sweep among
other mechanisms.

Kind regards

robert

Rick DeNatale

10/25/2006 1:31:00 AM

On 10/24/06, Ken Bloom <kbloom@gmail.com> wrote:

> 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.

It depends on how you define unused.

Actually a GC should remove unusable objects, i.e. objects which are
no longer reachable, and therefore can no longer affect future
computations.

Of course no GC can predict whether or not a reachable object will
ever be used in the future. So 'memory leaks' are possible even with a
GC. One of, but certainly not the only, reasons that global variables
are frowned upon is that they are opportunities to accumulate
reference chains to objects which otherwise should be GCed.

On the other hand the worst thing a GC can do is to reclaim objects
which ARE reachable. That's why the Ruby GC doesn't claim objects
which are reachable via references on an execution stack. Someone
mentioned this in another post to this thread.

Reference counting was probably the first GC algorithm, it's safe in
the sense that it doesn't free reachable objects, but it doesn't free
non-reachable objects which form a self referencing set.

> 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 depends on the implementation, but most Java VMs use a form of
generational garbage collection. This was first invented by Dave
Ungar for the UC Berkeley implementation of Smalltalk, who observed
that most objects either quickly became dead (unreachable) or lived a
long time. Ungar's original 'generation scavenging' GC algorithm
allocates new objects in a small space called newspace, and when
newspace fills, it moves the live objects in newspace to a new
newspace, leaving the others behind. After an object lives a certain
small number of generations, usually 2**n for a small n (like 2 or 3)
objects get tenured, to a larger "old space" Old space gets
infrequently reclaimed by another algorithm, often mark-sweep. It's
called scavenging because, rather than freeing unused new objects, it
scavenges live ones before throwing away wholesale those left in the
old newspace.

Generational scavenging can also, but not necessarily, have nice
properties in virtual memory systems, since it tends to keep the young
object closer together, which tends to keep the working set smaller.

On the downside, these types of GC algorithms mean that the address of
an object changes over its lifetime, which makes the API for what ruby
calls extensions, and what Smalltalk calls primitives (i.e. code
written in C or another low-level language which deals with objects)
have to deal with volatile object pointers.

It also complicates implementing finalization since dead objects in
newspace are reclaimed by being left behind which makes their
detection more expensive.

> 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.

Of course this is an issue regardless of the GC algorithm, it really
relates to what I said earlier about a GC collecting objects
potentially still in use as a cardinal sin.

Actually the nice thing about Ruby's use of blocks for things like
IO#open is that it nicely handles a lot of cases for which
finalization is used in other languages, and finalization is best used
sparingly since it only gets triggered when and if an object is GCed.
Relying on finalization to free up non-object resources (e.g. to close
files) is not the best practice in general.

> 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++).

While mark and sweep does tend to 'stop the world', reference counting
is actually more expensive because of the amount of bookkeeping it
requires. Every assignment requires an increment of the ref count of
the object now referenced, an decrement of the ref count of the object
formerly referenced, and a check to see if that count has gone to
zero.

There are also variants of mark and sweep which allow it to be
incremental, which combines the lower overall overhead with the
ability to amorize the impact over time.

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denh...

Tomasz Wegrzanowski

10/25/2006 7:01:00 AM

On 10/24/06, Just Another Victim of the Ambient Morality
<ihatespam@rogers.com> wrote:
> Is there a name for Ruby's garbage collecting strategy?

It's "semi-conservative mark&sweep".

> 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?

Depending on what you want, it might be impossible.
Garbage collection destroys objects if it is sure they will never be
used again. Normally it works by having a set of "obviously live"
objects (like global variables, local variables and so on), and
following pointers (like instance variables) they contain to find out
which objects are live.

If object cannot be reached that way, it can usually be considered dead
(disregarding stuff like C extensions). But the other way it isn't really true.
Objects often contain pointers that cannot be followed, but GC might
not know that.

One common example:
a_big_object = BigObject.new
an_array = [a_big_object, b, c]
an_array.shift
return an_array
Of course at this point a_big_object is dead - the returned array
contains only b and c. But Array#shift is most often implemented
not by copying second element to first position etc., but by
simply marking the first element as inactive - internally an_array
is something like {:size => 3, :ignore_first => 1, :contents =>
[a_big_object, b, c]}. In some languages GC doesn't know how arrays
work,
so it thinks all objects linked from it are live - so it will not
reclaim a_big_object. Telling GC about standard arrays is easy, but
many data structures contain inactive links like that and
have similar problems.

Second common example (this is silly, but it actually happens a lot):
def sum_of_a_list(node, partial_sum=0)
if node == nil
return partial_sum
else
return sum_of_a_list(node.next, node.this + partial_sum)
end
end

So we ask for sum_of_a_list(make_a_huge_linked_list()).
Linked lists consists of many nodes - as we go deeper,
initial nodes of the list will become dead. But most GC systems
won't release them, as they're arguments to functions that didn't
return yet. Only systems with tail-recursion optimization (like Scheme)
will be able to free such nodes.

More general case:
def foo
a_big_object = BigObject.new
bar(a_big_object)
do_something_else_but_dont_touch_a_big_object
end
a_big_object is dead after bar returns. Some compilers
will know that, but most won't remove it as long as foo runs.

Then it gets even worse:
def foo
a_big_object = BigObject.new
a_widget.set_callback {
print "Called!"
}
end

Even when foo finished, a_big_object won't be released
because the callback closure still "sees" it.

And we could go on and on. These are all things that
some actually used GCs can deal with, while other
actually used GCs don't, not purely theoretical cases.

Perfect garbage collectors simply don't exist.
Then, they usually work quite well, and when they don't
there are simple workarounds like setting a_big_object = nil
after you're done with it.

> 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?

No "real" garbage collection has such limitation,
certainly neither Java's nor Ruby's. Perl and Python
do not have real garbage collectors ;-)

--
Tomasz Wegrzanowski [ http://t-a-w.blo... ]

Dido Sevilla

10/25/2006 8:11:00 AM

On 10/24/06, Just Another Victim of the Ambient Morality
<ihatespam@rogers.com> wrote:
> 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?

The claim, as you have stated it, is in fact false. A similar claim,
that there will always exist pathological conditions where your
collection strategy will fail to find objects that are *unused*, is,
however true. The basic mark and sweep garbage collector will always
find all *inaccessible* objects, and all proper garbage collection
strategies can be shown to do this eventually once the program has
reached a steady state. But not all accessible objects will ever again
be used by the program, even though they are reachable; such objects
are called semantic garbage: they are reachable, but deallocating them
would have no consequences to the operation of the program. Safely
collecting semantic garbage is a difficult task, in its fullest
generality it is actually impossible, as its solution is equivalent to
the halting problem.

> 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?

This statement is false. Neither Java nor Ruby have trouble collecting
garbage consisting of circular references. Ruby and Perl on the other
hand, use a reference counting "garbage collector" that *does* have
this limitation.

Robert Klemme

10/25/2006 8:33:00 AM

On 25.10.2006 10:10, Dido Sevilla wrote:
> This statement is false. Neither Java nor Ruby have trouble collecting
> garbage consisting of circular references. Ruby and Perl on the other
> hand, use a reference counting "garbage collector" that *does* have
> this limitation.

Um, this sounds pretty contradictory.

robert

comp.lang.ruby

Ruby's garbage collector...

Just Another Victim of the Ambient Morality

???? ??????

Will Pugh

Will Pugh

???? ??????

Ken Bloom

Robert Klemme

Rick DeNatale

Tomasz Wegrzanowski

Dido Sevilla

Robert Klemme

x Login to ForumsZone