Abstract

The .NET Garbage Collector (GC) provides high-speed allocation and de-allocation of memory on the heap.  It is important that application abide by the simple rules set out, failure to do so will drastically impact the performance of the entire .NET platform.  This article explains how the garbage collector works and then discusses some performance and interaction issues and solutions. 

The garbage collector arranges memory in three distinct categories called generations.  When the object is first created, it is placed in generation 0, or another generation based on the size of the object (see table below).  Generation 0 objects are constantly checked if they need destruction as this is highly probable.  Generation 1 objects are scanned frequently, but not as frequently as Generation 0.  Finally Generation 3 objects are the older and bigger objects that will only be checked

Memory allocation

When the application is first loaded into memory, the CLR automatically creates a managed heap for objects to be placed on.  The managed heap consists of four storage bins, namely generation 0, 1, 2 and the Large Object Heap. 

All objects that are smaller than 85Kb are placed on the Generation 0 managed heap and objects greater than 85Kb are placed on the Large Object Heap.  Both the Generation 0 and LOB heaps have a Next Object Pointer which indicates the position in the heap where the next object is to be placed.  After an object positioned on the heap, the NextObjPtr moves by the size of the object to the next available free position.

1		Object A is inserted into the managed heap at the location of the NextObjPtr.
2		After the object is inserted the NextObjPtr moves along the heap by the size of Object A to the next free position.
3		Object B is then inserted at the NextObjPtr.
4		The NextObjPtr moves along the managed heap by the size of Object B to the next free position.
5		This process repeats for every object that needs to be created.

 Unlike malloc in C++ managed insertion is faster. In C++ a link list of memory blocks has to be searched looking for a block that is large enough to contain the object.  Once the block is found, it needs to be split by the object size and then a new link-list item created for the remaining free memory.  In managed allocation, the NextObjPtr is always at the correct position for new objects.  Thus, memory acquisition is faster in managed code.

The ugly ... this managed allocation model has two serious flaws.  The first is that it presumes memory is infinite and it can merrily append to the end of the heap until the application exits.  Secondly, it does not reclaim unused memory and this remains in the heap.  These two "serious" problems are easily overcome by the the garbage collector.

Identifying collectable objects

In this section, the mechanism the Common Language Runtime uses to identify objects that are reclaimable. Whenever the garbage collector runs, it will scan all objects searching whether the object is reclaimable and if it is reclaimable it is then freed from memory.  This is simply done by determining whether the application is currently using the object on the heap or not.

As an application executes, the running method and all of its return variables, arguments and internal variables are stored on the stack.  As each method and calls other methods so are these child methods pushed onto the stack.  Reference type objects when created by the new keyword are created on the heap.  However  the new operator returns a pointer to the memory location where the object was created.

Look at the following code:

   class Point
    {
        public int X;
        public int Y;
    }
    ...
            Point p;
            p = new Point();

When a program executes, it defines a reference variable (Point p; ).  This reference however stores a pointer to an object on the heap of type Point. The reference however does reside on the stack and contains the pointer.  Initially the value of the pointer is set to null which indicates that it does not reference any valid heap object.

The p = new Point(); statement is complex as the new operator creates an object on the heap of type Point and returns a pointer.  The variable p is then assigned using the assignment (=) operator the return value of the new operator. 

The object on the heap is thus bound to the reference type on the stack, which is called rooted.  The garbage collector manages this rooting mechanism and is shown in the diagram below:

When the method containing the reference type exits and is popped of the stack, the heap object no longer is being used.  This is called an un-rooted object.  The diagram below illustrates this:

The object on the heap is now ready for collection and the garbage collector will collect it.

Rooted objects and nested objects

Rooted objects are objects that are either used by static variables or the stack and are easy to determine by walking the stack.  However these objects may include nested or inner objects and these in turn other objects building a complete object model.  The garbage collector prior to collection treats all objects on the stack as collectable.  It then starts identifying rooted objects by walking the stack.  Each object is then interrogated for its internal objects and these objects are then also checked.  Within a short period of time the garbage collector has a complete object graph of all objects.  Any object that is not identified as rooted or leaf objects are ready for collection.

The garbage collector the maintains this state so that it does not need to re analyze all these objects again.    It however implements a effective mechanism to determine whether inner objects have change and perhaps refer to other objects, this is done through write barriers.

Generations

As briefly mentioned above, the Common Language Runtime divides managed heap memory into 3 Generations and one Large Object Heap.  This is to assist in optimizing the speed at which objects are collected.

The general assumptions the garbage collector makes

1. The larger the object in memory, the more likely the object is to stay in memory for longer time is highly probable.  This assumption presumes, the bigger the object, the more intense the process to create the object and programmers will only create big objects when necessary and possibly keep them in memory for longer, i.e. in some cache.
2. The longer an object stays in memory, the chances that it will stay in memory for longer is greatly increased.
3. All objects are deemed as invalid and need to prove they are rooted, if they are un-rooted they are reclaimed.

Most running applications create a lot of small objects for a short period of time and destroy them soon afterwards.  The GC has been optimized for this type of behavior and thus creates different heaps, discussed below

When collection is done all objects on this heap 256Kb (very small and thus processed quickly) are scanned to ensure that they are still rooted to some threads stack.  It also analysis all the objects used by the rooted object and builds a tree structure of the object hierarchy.   The scanning algorithm not only identifies nested objects, it tracks for circular references and double linked items.

Any object found not to be rooted or used by a rooted object is up for collection.  These objects are then marked for collection and will be discussed below.

Items that are still valid are then moved from Generation 0 to Generation 1, thus completely emptying out Generation 0.  These new generation 1 items are repacked and memory optimized.  Likewise when the Garbage collector collects Generation 1 objects, any objects that are still used are moved and repacked onto the Generation 2 heap.  The Generation 1 heap is only 2 Mb and is also processed quickly.

When items are moved from Generation 0 to 1 to 2, their physical memory locations are changed and all reference variables that use these objects are also updated.

The Generation 2 heap and the Large Object heap are only collected when the GC performs a full garbage collection.

At runtime the Garbage Collector may adjust  the sizes of Gen 0, 1 and 2 due to load on machine.

Sample

In the sample below, a new object (L) needs to be inserted by a new operator; however the Generation 0 heap is full and the garbage collector runs.

In scanning valid and invalid objects the GC determines object A, G, K are still in use and Objects B, C, D, E, F, H, I and J need to be collected and moved to the collection mechanism.  Objects A, G and K are repacked and moved into Generation 1 with all references to them updated.  This effectively clears Generation 0.  The new object L is then inserted to Generation 0.

As with generation 0, the same mechanism applies to Generation 1 objects and when Generation 1 is full it will move and repack items to generation 2.

When garbage collection is performed

Garbage collection is performed in the following conditions.

• A new item needs to be created in the Generation 0 heap (which is initially 256Kb) and there is insufficient space for the new object.
• When overall system memory is low.
• The GC.Collect() method is executed.
• When the extents of memory pressure are reached.
• The limit of unmanaged resource is reached.