Skip to main content

Tracing algorithms

Before we understand what tracing algorithms are, we must first understand the meaning of the phrase “root set of references”. Essentially the root set of references are those references that are always accessible to an executing Java program. They constitute local variables, method arguments, class variables, and instance variables.


When triggered, tracing algorithms mark all objects on the heap that can be traced from the root set of references. These are objects that are directly or indirectly referenced by the root set. Let's consider these to be live objects. This forms the mark phase of the tracing algorithm. The mark phase is followed by a sweep phase, in which all objects that were not marked in the mark phase are garbage collected. Because of it's two phases, this type of tracing algorithm is also known as “mark and sweep” algorithm.


Advantages:

  • Can detect and handle cycles

Disadvantages:

  • The heap is fragmented, ater the sweep phase.


Having a fragmented heap will prevent us from making optimum use of the heap memory. To eliminate this problem, the mark and sweep algorithm has been modified into a compacting algorithm. We will discuss compacting algorithms in the next post.

Discuss this post in the learning forum.

Commercial Links



Note: This text was originally posted on my earlier blog at http://www.adaptivelearningonline.net
Labels:

Comments

Post a Comment

Popular posts from this blog

My HSQLDB schema inspection story

This is a simple story of my need to inspect the schema of an HSQLDB database for a participar FOREIGN KEY, and the interesting things I had to do to actually inspect it. I am using an HSQLDB 1.8 database in one of my web applications. The application has been developed using the Play framework , which by default uses JPA and Hibernate . A few days back, I wanted to inspect the schema which Hibernate had created for one of my model objects. I started the HSQLDB database on my local machine, and then started the database manager with the following command java -cp ./hsqldb-1.8.0.7.jar org.hsqldb.util.DatabaseManagerSwing When I tried the view the schema of my table, it showed me the columns and column types on that table, but it did not show me columns were FOREIGN KEYs. Image 1: Table schema as shown by HSQLDB's database manager I decided to search on StackOverflow and find out how I could view the full schema of the table in question. I got a few hints, and they all pointed to
Post a Comment
Read more

Fuctional Programming Principles in Scala - Getting Started

Sometime back I registered for the Functional Programming Principles in Scala , on Coursera. I have been meaning to learn Scala from a while, but have been putting it on the back burner because of other commitments. But  when I saw this course being offered by Martin Odersky, on Coursera , I just had to enroll in it. This course is a 7 week course. I will blog my learning experience and notes here for the next seven weeks (well actually six, since the course started on Sept 18th). The first step was to install the required tools: JDK - Since this is my work machine, I already have a couple of JDK's installed SBT - SBT is the Scala Build Tool. Even though I have not looked into it in detail, it seems like a replacement for Maven. I am sure we will use it for several things, however upto now I only know about two uses for it - to submit assignments (which must be a feature added by the course team), and to start the Scala console. Installed sbt from here , and added the path
1 comment
Read more

Inheritance vs. composition depending on how much is same and how much differs

I am reading the excellent Django book right now. In the 4th chapter on Django templates , there is an example of includes and inheritance in Django templates. Without going into details about Django templates, the include is very similar to composition where we can include the text of another template for evaluation. Inheritance in Django templates works in a way similar to object inheritance. Django templates can specify certain blocks which can be redefined in subtemplates. The subtemplates use the rest of the parent template as is. Now we have all learned that inheritance is used when we have a is-a relationship between classes, and composition is used when we have a contains-a relationship. This is absolutely right, but while reading about Django templates, I just realized another pattern in these relationships. This is really simple and perhaps many of you may have already have had this insight... We use inheritance when we want to allow reuse of the bulk of one object in other
3 comments
Read more