Chain reaction in garbage collection

Question

I have a very fundamental question in Java. I searched for this everywhere but just could not find a solution anywhere.

I am trying to read about deleting a binary tree. Before dwelling into DFS, BFS etc, I was thinking that if I just release all active references to the root of the tree, the entire tree should get GCed automatically. What I mean is if I just drop the only active reference to the root, then the root must get GCed and hence, there are no more active references to the children of root and they should get GCed. This must continue as a chain reaction till the entire tree is GCed. Am I right or is something wrong with my analysis?

Assumption: All nodes are referenced by only its parents and nobody else.

Related: http://stackoverflow.com/questions/176745/circular-references-in-java — nhahtdh, Sep 20 '12 at 01:26
Java GC should clean up everything when your program can no longer refer to the chunk of memory, by my understanding. — nhahtdh, Sep 20 '12 at 01:27
Yep, you're totally right. As a general rule, the GC is really, really smart. — Louis Wasserman, Sep 20 '12 at 01:34
When you lose reference to any graph, even cycled, it is GC'ed. Tree is a simp[le graph from GC's point of view. — Alexei Kaigorodov, Sep 20 '12 at 03:22

Stephen C · Answer 1 · 2012-09-20T03:43:05.463

In a general sense you are right. That could happen.

However, in a particular sense, most garbage collectors don't work like that. When you remove the last link to the root of your tree, the GC doesn't kick in immediately. Rather, it waits until it is a good (e.g. efficient) time to run. Then it traces all objects that are still reachable (i.e. NOT garbage), deals with them, and then reclaims the rest. (Indeed, for the best garbage collectors the process of "reclaiming the rest" is very cheap.)

The exception to this are the reference counting (so-called) garbage collectors, where removing the last reference can indeed trigger an immediate cascade of deletions. But reference counting is not used in mainstream garbage collected languages because it is slow and because it cannot reclaim data structures with cycles. Certainly, no Java implementation I've ever come across used reference counting for garbage collection.

Chain reaction in garbage collection

1 Answers1