• Post Reply Bookmark Topic Watch Topic
  • New Topic

Implement a Garbage Collector  RSS feed

 
Shraddha Jain
Greenhorn
Posts: 27
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If u were to implement a Garabage collector, how wud u do it? simply put how would know when an object has no references to it?
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There are two broad categories of GC algorithms: 1) reference counting, and 2) "mark and sweep."

Reference counting is what it sounds like: for every object, you keep a count of how many times it is referenced inside the object itself. Every assignment to a reference variable has to include code to increment or decrement these counts. When a count reached zero, an object can be collected. Although this sounds simple, it actually has some important problems, the worst of which is that "cycles" -- two objects each referencing each other -- will prevent objects from being collected. It also uses lots of extra memory, and because assignments become so complicated, it's actually quite slow.

In a mark and sweep algorithm, the collector periodically starts at the "roots" of memory (stack frames of all threads, static fields) and marks every object that can be reached. When it is through, unmarked objects are unreachable and can be collected. This technique isn't fooled by reference cycles, needs only one extra bit of memory per object for the mark, and adds no overhead to other operations.

All Java garbage collectors are based on some kind of mark and sweep algorithm. In general, Java uses "generational" collectors, in which the heap is divided into "generations"; objects that have been around a long time are moved into generations that are examined only infrequently by the GC. It has been observed that most brand-new objects are garbage-collected very soon; the longer an object exists, the less likely it is that it will ever need to be collected.
 
vidya sagar
Ranch Hand
Posts: 580
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
HI Ernest, Really nice to read your explanation
 
Shraddha Jain
Greenhorn
Posts: 27
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i have read about this, lets take up the reference counting algorithm , how can i keep a count of references?
i'm trying to implement this garbage collector using the reference counting algorithm
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, it couldn't be simpler to implement. Every time an assignment is made to a reference variable, you increment and decrement the counter(s) for the referenced object(s). When you find an object has a count of zero, you decrement the counts of all the objects it holds as fields, and then delete the object. If, when decrementing the field objects, you find more zeros, then you continue to do the whole thing recursively, as long as necessary.

You obviously can't implement this in Java for Java objects, not transparently, anyway. It has to be part of the underlying language machinery. Are you implementing your own JVM? If so, then you'd want to hook this into the code for all the "store" bytecodes, putfield, etc.
 
Ayub ali khan
Ranch Hand
Posts: 395
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Ernest,

Thank you for your valuable inputs on this question, it was a good question as well !!

Thanks Ayub.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!