Reference counting done correctly

By Frans

Why did Microsoft choose for garbage collection in their new .Net platform? Is their an alternative? It is a fact that the Java is also using garbage collection for freeing the memory used by object that are no longer accesible. And it is also a fact that .Net is Microsofts version of Java.

Problems with garbage collection

But what are the problems with garbage collection? In .Net the destructor is only called when the object is removed during garbage collection. Because the destructor is only called long after the object has become unreachable from the program (execution unit), it cannot be used to perform certain tasks. This means that in some cases a finish method needs to be implemented. Especially for Managed C++ this has great implications, because the destructor is no longer called when the delete operator is called, as it is in normal C++. (This is one of the reasons why Managed C++ does no longer adhere to the ANSI C++ standard.) In C# the finish method is called Dispose, and with the using statement, calling of the Dispose methode can be enforced. Forgetting to use the using method, can lead to introduce tricky bugs.

Another problem with garbage collection is that it is an expensive operation, which cannot performed parallel to normal program execution. It is usually initiated when system resources are running out or when the system is idle. This means that at undeterministic moments the execution is delayed for a short time to give room for a garbage collection to be taken place. This is the reason why garbage collections in a real-time environment are avoided.

Why is garbage collection used at all?

A good question is, why is garbage collection implemented at all. Why not simply free the memory of an object that is being deleted (as it is done in C++)? There is one good reason, and that is that it is still possible that some other object is still referencing the object. And that causes serious problems in case you want to create a safe execution environment, because it creates a reference to a pointer to a piece of memory which is no longer in use, and is likely to be used for some other object in the future. Memory should thus only be deleted when it is no longer referenced to.

Reference counting

One of the most simply ways of keeping track if a piece of memory is being referenced, is to count the number references to it. (A problem with this is that one has to establish a upper limit of the maximum number of simultanious references to a piece of memory. In most cases it is possible to establish such an upper limit.)

But simple reference counting can keep memory allocated that cannot be reached any more. This is the result of circular references. Take for example a tree structure where the children contain a reference to their parent (which is a very common thing to happen). Now when a node with child node is removed, it is not freed because all child nodes still have a reference to the parent node. A garbage collection algorithm would free such objects, because it will discover that the node and all the child nodes (and all all possible other nodes below it) cannot be reached anymore, and can be flagged for deletion.

Different kinds of references

The reference from a parent node to a child node is a different kind of reference then that of the child node to its parent. Actually, there are three kinds of references: Because a component cannot be a part of itself, the component references form an acyclic directed graph or tree, depending on whether a child can have more than one parent or not. (The case that each child has at most one parent, does offer a number of important advantages will be discussed below.) It is obvious that an object can be deleted if it only has reverse component references to it. Thus reverse component references do not need to be counted. But excluding them from the count does not solve the problem. Although component references do not form cycles, the combination of component and aggregation reference still can.

The aggregration references can be divided into claiming and non-claiming. A claiming aggregration reference, means that the object being referenced should not be deleted as long as the reference still exists. A non-claiming aggregration reference should be removed (or made null) whenever the object being referenced is deleted.

Implementation of non-claiming aggregration references

The most obvious implementation keeps with each object a list of places that have a non-claiming aggregration reference to it. For performance reasons, it can be wise to use a double-linked list. That would introduce two additional pointers for each place where a non-claiming aggregration reference occurs, and one additional pointer for the object being referenced. This implementation is rahter expensive in use of memory and in terms of execution time, because several pointers need to be updated whenever references are made or removed.

An alternative implementation, is to make us of delayed deletion. The idea is not to remove the non-claiming aggregration reference immediately, but only when it is followed. For this to work, the object should be marked as deleted, and the memory it uses should not be freed until all aggregration references have been removed. For this we need a counter again. For this implementation two counters need to be used for each object that is being referenced. One counter for the composite and claiming aggregration references, and one for the non-claiming aggregration references. When the first counter is zero, it means that the object has been deleted, and that non-claiming aggregration references should be deleted. Only when both counters are zero, the memory is freed. A disadvantage of this approach is that it can take a very long time, until memory is freed of objects which have already been deleted, because non-claiming aggregration references are only freed when they are followed. (A solution would be a garbage-collection like algorithm that would check all non-claiming aggregration references to see if they need to be removed.)


Of course, the above strategy only works if all references are nicely removed, otherwise the counters never are reset to zero, and the memory is never freed. This means that whenever an object is deleted, all references it has to other objects should be removed.

Problems with claiming aggregration references

In practice claiming aggregration references are quite common. An object may not be deleted, when one of its components still has a claiming aggregration reference to it. One can either check this on deletion or to propagate each claiming aggregration reference up to all its parents (in the component hierarchy). Which of the two methods should be used, depends on the nature of the object model and the possible number of child objects an object can have. For the latter methode to work, objects need to have a reference to their parent objects. If an object have at most one parent, this can be easily stored in the object. If more than one parent object is allowed, a list is needed of reverse component references to the parents. Note that only the object to which there, or to one of its (nested) children, a claiming aggregration reference can occur, needs to have reverse component references to its parents.

In case objects can have multiple parents, there is a need for splitting the counter for the component references and the claiming aggregration references into two separate pointers. The (recursive) procedure to check if a component reference to an object can be removed, can conclude it is okay, if the object still has another parent. If this is not the case, it is not okay if there is a claiming aggregration reference to the object. If this is also not the case, then the procedure has to be called on all the child objects it has component references to.

Preventing cyclic component references

Above it was assumed that if the component references form an acyclic directed graph (or tree). But something has to be done to prevent cyclic component references to occur. The most easy way to prevent them is to enforce that each object has at most one parent, and that child objects may not switch parents. Without these restrictions, it is difficult to prevent cyclic component references automatically. Just blindly checking if a cyclic is introduced with a mutation, can be very expensive. Assiging level numbers to objects such that all child objects have a lower number than their parents could help. Keeping the numbering consistent during updates is not trivial, but doable.

Smart pointers

More software engineering stories