Garbage collection in Objective-C and C#

In C#, or more precisely CLR .Net, developers are freed from manually allocating and freeing the memory for managed objects. But for unmanaged resources, developers must dispose them explicitly, otherwise memory leaks. In Objective-C, it's very similar to C/C++, you must and must only release objects you create.

Both languages have implemented an automatic garbage collection mechanism with two different algorithms, Reference counting by Objective-C., and Mark-sweep-compact by CLR .Net.

In Objective-C, when an object is initialized, it has a reference count of 1. when it is retained by some other object, its reference count is incremented by 1. When it receives a release message, its reference count is decremented by 1. When the reference count of an object is 0, the system treats it as garbage and deallocates the memory it occupies. Reference counting is an algorithm easy to understand. Compared with other garbage collecting algorithms, one strong point of reference counting is that it won't suspend applications from running during garbage collection. Reference count is incremented or decremented while the application is running. Developers are responsible for maintaining the reference count of objects they create by sending retain or release/autorelease messages to the objects.

But when there are cyclical references among objects, reference counting does not quite work. To work around retain cycles, Objective-C introduces weak reference. For example, x holds a strong reference to y, while y has a weak reference to x. X cannot be deallocated if any other object holds a strong reference to it. But when no object has a strong reference to x, even though y has a weak reference to x, x can be deallocated. In CLR .Net there is also a weak reference type, which I will talk about it later.

CLR implements a generational mark and compact garbage collecting mechanism. Objects are allocated in an area called the managed heap. The managed heap is different from the native C runtime heap in that it is a reserved continuous block of memory. Traditionally, objects are scattered in the native heap wherever the system can find a spot that is large enough to hold an object. The managed heap is continuous and hence it is really fast to allocate space for new objects. The managed heap is divided into 3 sections, generation 0, 1 and 2. CLR has a NextObjPtr pointer to keep track of where to put the next object. Each generation has a size limit. The size is not fixed. The garbage collector collects the statistics of your application and adjusts the size of each generation as it goes.

Now let's look at how the garbage collector works. When a method in your application gets executed, primitive types are stored in the stack. Reference types are created in Generation 0 on the managed heap. The NextObjPtr gets updated and point to the next available spot. When the method finishes execution, the stack gets cleaned up right away, but the reference types are not. The garbage collector does not deallocate reference types until Generation 0 is filled. How does it know? It could be a test against a threshold value, or the NextObjPtr points beyond Generation 0. The garbage collector will then kicks in and starts marking. It starts from the reference objects used in the current method, the so called roots, traverse to build a reference graph of all other objects referenced by the roots - they are marked as reachable objects. All non-reachable objects are treated as garbage and deallocated. Cyclical reference of objects is not an issue here. As long as these objects are not referenced by a root object, they are deemed as unreachable and will be swept. Any objects survived in the sweep are then compacted and promoted to Generation 1.

When garbage collector kicks in, all running threads are suspended so that garbage collector can analyse the managed heap and build the reference graph. When objects are compacted and moved, all pointers to these moved objects are updated to point to the new addresses by the garbage collector.

Once the garbage collection completes, the application resumes running. New objects are allocated in Generation 0. When Generation 0 is filled, garbage collector starts again. Will it clean up Generation 1? It all depends on if Generation 1 is filled or not. If not, garbage collector will not examine Generation 1. The fact may be that the objects stored in Generation 1 are not used any more and are truly rubbish, but garbage collector will leave them in memory unless Generation 1 is running out. The garbage collector will then work on Generation 1. Objects survived the collection in Generation 1 are compacted and promoted to Generation 2. Again, the garbage collector only cleans up Generation 2 when Generation 2 is filled. Survived objects in Generation 2 just stay in Generation 2. The idea of generational garbage collecting is to improve performance because examing all generations each time is expensive. The garbage collector may not compact objects each run. If the gap in memory is small, it will not compact to save the effort of moving objects around and updating the references to these objects.

So we can see some of the ideas behind the garbage collecting mechanism in CLR .Net:
1. The newer the object the shorter its life cycle might be.
2. The older the object the longer it tends to stay.
3. The more continuous the available space in the heap, the faster to allocate new objects.
4. The fewer generations to examine, the faster the garbage collecting runs.

Similar to Objective-C, .Net has a WeakReference type. E.g. these types can be referenced by other objects but that does not prevent them from being deallocated by the garbage collector. The WeakReference type may be used in a caching mechanism. But since garbage collection is not deterministic and may be more frequent than one would expect, it may not be a good way of implementing caching.

In summary, Objective-C encourages developers to leave as few memory prints as they could. While the desinger of CLR .Net believes memory management is not an easy task and therefore should be taken over by the system - performance can be sacrificed for the sake of safety.