From: Dido Sevilla Date: 2006-10-25T17:10:34+09:00 Subject: Re: Ruby's garbage collector... On 10/24/06, Just Another Victim of the Ambient Morality 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.