Garbage Collector and Circular Reference

Garbage collector and circular reference

The .NET garbage collector can absolutely handle circular references. The very high level view of how the garbage collector works is ...

• Start with locals, statics and GC pinned objects. None of these can be collected
• Mark every object which can be reached by traversing the children of these objects
• Collect every object which is not marked.

This allows for circular references to be collected just fine. So long as none of them are reachable from an object known to be uncollectable then the circular reference is essentially irrelevant.

Note: I realize I've left out many fun details in order to keep this answer simple and direct

How does Java Garbage Collection work with Circular References?

Java's GC considers objects "garbage" if they aren't reachable through a chain starting at a garbage collection root, so these objects will be collected. Even though objects may point to each other to form a cycle, they're still garbage if they're cut off from the root.

See the section on unreachable objects in Appendix A: The Truth About Garbage Collection in Java Platform Performance: Strategies and Tactics for the gory details.

How does Python's Garbage Collector Detect Circular References?

I think I found the answer I'm looking for in some links provided by @SvenMarnich in comments to the original question:

Container objects are Python objects that can hold references to other Python objects. Lists, Classes, Tuples etc are container objects; Integers, Strings etc. are not. So, only container objects are at risk for being in a circular reference.

Each Python object has a field - *gc_ref*, which is (I believe) set to NULL for non-container objects. For container objects it is set equal to the number of non container objects that reference it

Any container object with a *gc_ref* count greater than 1 (? I would've thought 0, but OK for now ?) has references that are not container objects. So they are reachable and are removed from consideration of being unreachable memory islands.

Any container object reachable by an object known to be reachable (i.e. those we just recognized as having a *gc_ref* count greater than 1) also does not need to be freed.

The remaining container objects are not reachable (except by each other) and should be freed.

http://www.arctrix.com/nas/python/gc/ is a link providing a fuller explanation
http://hg.python.org/cpython/file/2059910e7d76/Modules/gcmodule.c is a link to the source code, which has comments further explaining the thoughts behind the circular reference detection

Circular references in Javascript / Garbage collector

Any half-decent garbage collector will handle cycles.

Cycles are only a problem if you do naive reference counting.

Most garbage collectors don't do ref-counting (both because it can't handle cycles, and because it's inefficient). Instead, they simply follow every reference they can find, starting from "roots" (typically globals and stack-based variables), and mark everything they can find as "reachable".

Then they simply reclaim all other memory.

Cycles are no problem because they just mean that the same node will be reached multiple times. After the first time, the node will be marked as "reachable" already, and so the GC will know that it's been there already, and skip the node.

Even more primitive GC's based on reference-counting typically implement algorithms to detect and break cycles.

In short, it's not something you have to worry about.
I seem to recall that IE6's Javascript GC actually failed to handle cycles (I could be wrong, it's been a while since I read it, and it's been much, much longer since I touched IE6), but in any modern implementation, it is no problem.

The entire point in a garbage collector is to abstract away memory management. If you have to do this work yourself, your GC is broken.

See MDN for more information on modern garbage collection and the mark-and-sweep algorithms that are used.

Circular references in Java and garbage collection

You are thinking too much in technical terms. The garbage collection is defined as any measure capable of reclaiming the storage of unreachable objects.

The Java Language Specification §12.6.1 defines:

A reachable object is any object that can be accessed in any potential continuing computation from any live thread.

A directed reference is a way, how running code may access an object, and, in fact, traversing these references is a typical way how garbage collector implementations detect the reachability of objects, but it must be emphasized that even the existence of, e.g. a local variable, referring to an object is not sufficient to prevent its garbage collection, if no “potential continuing computation” reads it.

This is what happens in practice when the JVM’s optimizer transforms the code, eliminating unused variables and dead code.

The linked section also explicitly states:

Optimizing transformations of a program can be designed that reduce the number of objects that are reachable to be less than those which would naively be considered reachable.

Not getting distracted by these technical details, it is enough to know that only the possibility to access an object is relevant to determine that it is not garbage. So regardless of how objects are interlinked with references, if no live thread can access them, they all are garbage.

Garbage collection of a instances with circular reference

Objects are only collected when there are no references that are accessible from a rooted location. Rooted locations are locations that are "in scope" throughout the entire application's lifetime, such as static variables, the stack, etc.

Since these objects have a cyclical reference, if either of them is accessible through a rooted reference (a local variable, a static variable, or anything accessible through another series of references that link back to a rooted reference), then neither are eligible for garbage collection. If neither object is accessible from a rooted reference, then both objects are eligible for garbage collection.

How does Java garbage collector deals with circular references when their access path is broken?

There's set of "root objects" which are considered always accessible: e.g., Thread references, static variables, class references. If some object can not be reached via link of references from these root objects, it considered to be available for GC, even if there are some references to that object.

---

Related Topics