A Template for Reference Counting
Kenneth Ngai
Reference counting is a well known technique for improving performance, particularly when manipulating large or complex objects. Less well known are all the problems that arise in debugging reference-counting code — unless you can get someone else to do it for you.
Reference counting is an object-oriented concept that improves efficiency by allowing objects that are assigned to each other to share the same memory. For complex objects, significant performance gain can be realized by deferring the expensive copy operation until the values are actually changed, if ever. With this technique, you can eliminate the use of pointers and still be able to copy large objects without incurring any unnecessary performance penalty. To implement a class that supports reference counting, a shared data structure must be declared to store variables that normally would have been created as member objects in the class. These objects cannot be declared as class members because they must be visible and shared among all instances of the class. Access to the shared data is provided by a class function that returns a pointer to the shared structure. A pointer to a reference counter is also needed to keep track of the number of class objects referencing the shared data structure. Although the reference counter itself is not a class member, the pointer to the reference counter is a class member.
When a new reference object (class instance) is constructed, memory is allocated for a reference counter and a shared data structure. The object initializes its pointers with the addresses of the allocated memory. The reference counter is initialized to a count of one. The reference counter increments when another reference object is assigned the current reference object (using an assignment operator or a copy constructor).
If two or more objects reference the same data, and one of the reference objects threatens to change the value stored in a data object, the object that wants to make the change can no longer reference the shared data. It must allocate memory for its own data structure and reference counter, copy the contents of the shared object, and decrement its associated reference counter. Only then can it change the stored value.
The reference counter also decrements when a reference object is destroyed. When the last reference object is destroyed, the memory for the shared data structure, as well as the memory for the reference counter, is deallocated.
The Template Class
To implement reference counting reusably, I employed the C++ template feature to develop a generic base class. C++ templates offer the search-and-replace behavior of C++ macros, with the added benefit of strong type checking. See Listing 1 for the source code. The template implements all the mechanics necessary to support reference counting. In addition, to enforce data encapsulation, all methods related to reference counting are private and thus hidden from programmers. The function GetData provides the only way to access the shared data structure. GetData is overloaded with both constant and a non-constant versions. The const GetData accesses member objects for read-only purposes. The non-const GetData calls the function CopyOnWrite, which duplicates the member objects whenever the reference count is greater than one. The C++ compiler determines which GetData function to use based on whether or not the const keyword is declared in the calling function. This is good OO design because it encourages programmers to differentiate between data access and data manipulation functions. Failure to declare a read-only function constant will still generate correct code, but it instructs the compiler to use the non-constant version of GetData, which will be less efficient if the data values have to be first duplicated.
Listing 2 shows an implementation of class Company using the template. Notice that a structure is declared for storing the member objects of Company. The copy constructor in the structure is crucial since it is used by CopyOnWrite to duplicate a copy of the data. (Depending on the compiler, failure to declare a copy structure may cause a compile error.) If the member objects need to be initialized, the default constructor for the class must do so. There are no other restrictions that I can think of for using the template. This class was tested with Microsoft Visual C++ (V4.2 and 5.0). It should work also with any compiler that supports templates. I recommend using reference counting for classes that contain long strings or arrays. For classes with simple data types, you may not see the benefits because of the overhead in implementing the reference counter and the extra level of indirection needed to access data members. o
Kenneth Ngai is a project leader in the Technology department at Johnson & Higgins, an insurance brokerage firm in New York. His projects include developing MFC extension libraries for client/server database applications. Kenneth Ngai has a BS in Industrial Engineering from Columbia University and can be reached via email at [email protected].
