H-World - Docs - Reference Counting

The idea of reference counting

H-World is written in C++ which does not support garbage collection or some other method of automated memory management by itself. After I had some very bad experiences with explicit memory management in another project (Simutrans) I searched for ways to get semi-automated memory management with C++.

The idea of reference counting is simple: count how many references to a object exist, and if that count drops to zero, the object is obviously no longer needed by the program and can be deleted. This can be implemented by using overloaded operators and template classes in C++.

Reference counting in it's pure form provides automated memory management, but it cannot manage double linked or cyclic data structures because the reference count never drops to zero in such structures. To allow double linked and cyclic structures being cleaned up properly requires to break the double links which is not possible with pure reference counting. (In the next section I'll describe how to avoid cycles at all).

H-World uses a weaker, semi-automatic still reference counting approach. References can be set to nil meaning that they no longer reference any object. Thus the programmer can tell the memory management system when he thinks a object is no longer needed. This way the programmer can break cyclic structures and make them available for cleanup by the refernce counting system. But now, that refernces can be nil what are the advantages? Why not just use plain pointers and explicit memory management?

The references have the advantage, to be always bound to a object, or not to be bound. Pointers can be dangling, that means they can point to some invalid memory area. Dangling pointers (unlike NULL pointers) can't be checked by the program, and are very dabgerous, causing data corruption or program crashes upon dereferencing.

References have the advantage of checkability, they can be checked if they are bound, or unbound. Dangling pointers can't be checked. Thus references avoid one of the worst problems: dangling pointers. In short the checkability of references allows to write more robust code.

H-World uses a template class to implement references (called handles in H-World). This template class replaces pointers, and provides the same operations like pointers, with the addition of deleting objects if their reference count drops to zero. This way H-World gets the checkability advantage and the automated deleting of unused objects. The only drawback is, that double linked structure must be broken up explicitely before the elements get cleaned up. But maybe double linked and cyclic structuires can be avoided at all? The next section sketches an idea.

How to avoid double linked structures

It seems double linked and cyclic structures can be avoided at all by using the following approach:

Assume A references B and B references A. (A->B, B->A). Even if neither A or B are referenced by something else (and thus could be cleaned up) their reference count is still 1 because they reference each other and reference counting won't clean them up.

But the double link can be broken by introducing a new entity C. The parts of B that are needed by A are moved into C. Now A is changed to reference C instead of B. B is changed to reference C, because B needs the things moved into C. And B still references A. (A->C, B->C, B->A)

This structure has no cycle anymore! We had assumed that A and B are not refernced by someone else, and are due to be cleaned up. Now reference counting can do the cleanup. B is not references by anyone in this example and gets cleaned up. If B is removed, A is no longer referenced by B and gets cleaned up too. Now noone references C anymore and C gets cleaned up too. This is exactly what we wanted to have!

It seems the described approach can avoid double (or cyclic) links in most cases and thus make reference counting a nearly general purpose memory management method.

Was this article interesting to you? Did you find mistakes or want to make suggestions?
Feedback (good or bad) is always welcome!
You can reach me by e-mail: Send feedback.