June 2000/Safe and Economical Reference-Counting in C++

Features

Safe and Economical Reference-Counting in C++

Vladimir Batov

Smart pointers keep getting smarter.

Introduction

This article discusses the implementation of a smart pointer reference-counting pattern, via a class called Handle. This implementation substantially improves on the design discussed in my previous article, "Extending the Reference Counting Pattern " [1]. When I wrote that article, most of the widely available compilers did not implement C++ templates as well, or as completely, as they do today. Therefore, despite many advantages, the original implementation had two serious limitations promptly pointed out by Scott Meyers [2]. It provided a rigid data construction mechanism (worked only with the default constructor) and did not support inheritance-based polymorphism. Considering these limitations, even I became convinced to abandon the idea in favor of a "more conventional" solution, which was more expensive in terms of memory consumption and performance.

Since that time, the widespread availability of powerful new language features, such as member function templates and template constructors, enabled me to revive and improve the original design. This new design overcomes the aforementioned limitations, and represents what I feel is a safe, economical, and flexible smart pointer.

Although there are a great many implementations of the reference-counting pattern (see [3-9] just to name a few), the design discussed in this article offers several advantages, which are perhaps rarely found in one implementation. I list a few of the most important here; you can read about the rest of them in the section of this article entitled Summary of Advantages and Known Limitations.

Handle<Data> is fully automatic. It creates Data instances for you when and the way you want them, manages the data (using reference counting), and deletes them when you no longer need the data.

It is safe. Handle<Data> maintains a strong association with the Data it represents. The existence of a Handle<Data> instance guarantees the existence and validity of Data (unlike unassigned instances of Data * or auto_ptr<Data>).

Handle is template-based rather than inheritance-based, such as the implementations described in [3-6]. The template-based approach does not impose requirements on the Data class, and thus allows the introduction of reference-counting functionality later in development, or with the use of legacy code.

Handle conveniently replaces pointers by closely matching their familiar syntax and behavior, and without the dangers associated with pointers and auto_ptr.

An Illustration

One of Handle<Data>'s strong points is its convenience. The Handle wrapper takes complete care of Data resource management while providing a familiar interface, and without sacrificing flexibility:
class Data
{ ...
   // Three ways to create a Data 
   // instance
   Data();
   Data(int, double);
   Data(const char*);
};

// Use Data::Data()
Data* p = new Data();
auto_ptr<Data> ap(new Data());
Handle<Data> dh = 
   Handle<Data>::create();      
Handle<Data> dh;
// Use Data::Data(int, double)
Data* p = new Data(1, 2.3);
auto_ptr<Data> ap(new Data(1, 2.3));
Handle<Data> dh = 
   Handle<Data>::create(1, 2.3);
Handle<Data> dh(1, 2.3);
// Use Data::Data(const char*)
Handle<Data> dh = 
   Handle<Data>::create("text");
Handle<Data> dh("test");
Unlike auto_ptr, Handle creates Data instances. This approach ensures consistent management of the Data resource — the same Handle class creates, controls access to, and ultimately deletes Data. Such encapsulation of functionality eliminates the need for explicit memory management (using new and delete), thus reducing chances for memory mismanagement:
Data*          dp;     // Unassigned.
auto_ptr<Data> ap;     // Unassigned.
auto_ptr<Data> ap(dp); // Trouble.
Handle<Data>   dh; // Internally creates a Data instance if the
                   // class has default constructor. Otherwise,
	          // simply does not compile.
dp->modify(); // Trouble
ap->modify(); // Trouble
dh->modify(); // OK
Handle<Data> instances (and their internal Data resources) are created using one of the following interfaces:

a family of template functions Handle<Data>::create(arguments)

a family of template constructors Handle<Data>Handle(arguments)

Both interfaces accept arguments intended for Data construction and readily transfer them to an appropriate Data constructor (if such a constructor exists). Therefore, if you want a reference-counted Data instance to be created with, say, the Data(int, double) constructor, you simply supply appropriate arguments when a Handle<Data> instance is created. The arguments you provide are passed to Data(int, double). In the transfer from Handle to Data, all attributes of the arguments, including const, are preserved:
class Data
{ ...
   // Different constructors for
   // const and non-const args.
   Data(const Arg&);
   Data(Arg&);
   Data(const Arg*);
   Data(Arg*);
};

Arg arg;
const Arg const_arg;

// Data::Data(Arg&) called
Handle<Data> dh = Handle<Data>::create(arg);
Handle<Data> dh(arg);
// Data::Data(const Arg&) called
Handle<Data> dh = Handle<Data>::create(const_arg);
Handle<Data> dh(const_arg);
// Data::Data(Arg*) called
Handle<Data> dh = Handle<Data>::create(&arg);
Handle<Data> dh(&arg);
// Data::Data(const Arg*) called
Handle<Data> dh = Handle<Data>::create(&const_arg);
Handle<Data> dh(&const_arg);
Apart from the decision not to support unassigned-pointer behavior, Handle has syntax and behavior similar to conventional pointers. Therefore, if you are not sure what to expect from Handle<Data>, just remember how Data * pointers would behave in the same situation. The following code shows some of the syntax and behavior similarities using pointers and Handles:
// Construction.
Data*              dp = new Data(...);
const Data*        cp = new Data(...);
Handle<Data>       dh = Handle<Data>::create(...);
Handle<const Data> ch = Handle<Data>::create(...);
// or alternatively
Data*              dp(new Data(...));
const Data*        cp(new Data(...));
Handle<Data>       dh(...);
Handle<const Data> ch(...);

// Non-const-to-const assignments.
cp = dp; // OK.
ch = dh; // OK.
// Const-to-non-const assignments.
dp = cp; // Error. Do not compile.
dh = ch; // Error. Do not compile.

// Inheritance-based polymorphism.
// Upcast

class Base {...};
class Derived : public Base {...};
class Other {...};

// OK.
Base*        bp = new Derived(...);
// OK.
Handle<Base> bh = Handle<Derived>(...);
// Error
Base*        bp2 = new Other(...);
// Error
Handle<Base> bh2 = Handle<Other>(...);

// Downcast

Derived*        dp = bp; // Error.
Handle<Derived> dh = bh; // Error.
Derived*        dp =
   dynamic_cast<Derived*>(bp);
Handle<Derived> dh = 
   bh.dyn_cast<Derived>();

// Functions accepting Base-based args.
void funcA(Base*);
void funcB(Handle<Base>);
void funcC(const Handle<Base>&);

// Passing Handle<Derived> args.
funcA(dp); // OK.
funcA(dh); // OK.
funcB(dh); // OK.
funcC(dh); // OK.
Implementation

Listing 1 shows the main header for the Handle template. The Handle class implements a lightweight proxy and manages data sharing (based on reference counting). The Data management and reference-counting infrastructure are encapsulated in a separate Counted class (line 16 of Listing 1).

Lines 20-38 show the basic destructor, default constructor, copy-constructor, and assignment operator. Nothing here is new, including the well-established technique for data sharing management (functions use and dismiss).

Lines 40-44 show the familiar conversion and access operators. Although I agree that providing an operator Data* method should not generally be recommended, real life calls for adjustments. On a few occasions I was tempted to take conversion operators out, just to put them back later to interface with third-party or legacy libraries that deal with Data * pointers directly.

Template versions of a copy constructor and assignment operator (lines 49-68) help Handle manage polymorphic objects in much the same way as pointers:
class Base {...};
class Derived : public Base {...};

Derived*        derived_p;
Handle<Derived> derived_h;
// Copy-constructors called explicitly
Base*        base_p(derived_p);
Handle<Base> base_h(derived_h);
// Copy-constructors called implicitly
Base*        base_p = derived_p;
Handle<Base> base_h = derived_h;
// Assignments
base_p = derived_p;
base_h = derived_h;
These template versions work similarly to their counterparts from the basic set — the only difference is that the template versions apply type conversion first. cast<Data> (lines 75-87) and _cast_test (lines 117-119) ensure safe static type conversion. _cast_test simply does not compile if the language does not support the requested type conversion.

The same mechanism provides support for the const attribute of the Data type:
Handle<const Data> const_dh;
Handle<Data> dh;
const_dh = dh;
Since Data and const Data are different types, the line const_dh = dh above causes the template version of the assignment operator to be called (lines 63-68). This assignment operator calls the function Handle<Data>::cast<const Data>,which in turn calls function Handle<Data>::_cast_test<const Data>. The compiler is happy with automatic conversion of the Data * to the const Data* (line 119) and the assignment goes through. The same mechanism prevents compilation of the statement:
dh = const_dh; // Error.
There are two template copy constructors (lines 49-54 and 56-61). They are very much the same except that the second one (lines 56-61) looks more like a typo to a seasoned C++ programmer — it accepts a non-constant reference. The reason for that is not immediately obvious without understanding how Handle objects are created. Therefore, I'll get back to the unusual copy constructor later.

Two include files (#included in lines 46, 47 in Listing 1) define Handle's interfaces for creation and construction. These files (Listings 2 and 3) have a lot in common. Both implement the same functionality (they create Handles) and have similar layouts. Both provide template families (create functions and Handle constructors). Each file is divided into separate groups for different numbers of incoming arguments. Then, to ensure proper handling of const argument attribues, every group lists all possible combinations of the arguments with and without the const attribute.

Consider the groups dealing with two arguments as an example (lines 28-45 in Listing 2 and lines 11-24 in Listing 3). The basic functionality remains the same throughout the files — create a new Handle-Counted-Data assembly using provided arguments:
// From create.h (Listing 2)
template<class Arg1, class Arg2>
static
Handle<Data>
create(Arg& arg1, Arg2& arg2)
{
   // Implicitly creates a Handle 
   // instance using private
   // Handle(Counted*)
   return new Counted(arg1, arg2);
}

// From unofficial.h (Listing 3)
template<class Arg1, class Arg2>
explicit Handle(Arg& arg1, Arg2& arg2)
: _counted(new Counted(arg1, arg2))
{
   _counted->use();
}
The functionality is replicated for all possible const and non-const combinations of the two arguments (lines 39-42 in Listing 2 and lines 18-21 in Listing 3). These sets of functions help to deliver arguments to an appropriate Data constructor without losing const attributes. For example,
class Data
{ ...
   // Subtly different constructors.
   Data(const Arg1&, const Arg2&);
   Data(      Arg1&, const Arg2&);
};

Arg1             arg;
const Arg2 const_arg;

Handle<Data> dh(arg, const_arg);
The object dh is created with Handle(Arg1&, const Arg2&) (line 19 in Listing 3), which invokes and transfers the arguments to Counted(Arg1&, const Arg2&) (line 57 in Listing 4), which creates an internal Data instance with the Data constructor that best matches provided argument types (line 53 Listing 4). In the example above the constructor will be Data(Arg1&, const Arg&).

The simplified versions of the include files (Listings 2 and 3) handle up to three arguments. The source on the CUJ web site (http://www.cuj.com) handles up to four. Although the files are likely to grow (according to the maximum number of incoming arguments you need to support), they have a very regular and easy-to-follow structure. Add support for more arguments when you need it.

It is the very general nature of Handle template constructors (Listing 3) that makes it possible to use the following syntax:
// Creates internal Data instance
// using Data::Data(int)
Handle<Data> dh(1);

// Creates internal Data instance
// using Data::Data(int, double)
Handle<Data> dh(1, 2.3);
Unfortunately, that friendly Data management syntax (it specifies how internal Data are created) overlaps with the syntax reserved for Handle copy-constructors. For example:
class Data
{
   ...
   Data(Handle<Other>);
};

// Create a new Handle-Other pair (a new
// Other instance and the first Handle
// pointing to it).
Handle<Other> oh(args);

// Create a new Handle-Data pair (a new
// Data instance and the first Handle
// pointing to it) using
// Data(Handle<Other>) constructor.
Handle<Data> dh = 
   Handle<Data>::create(oh);

// The following four lines do not 
// create new Handle-Data pairs (as the
// previous lines do) but rather create
// additional handles that point to the
// same data of the Other type as oh
// points to.

// Uses "unusual" template 
// copy-constructor.
Handle<Data> dh1(oh);   // 1.
// Uses basic copy-constructor.
Handle<Data> dh2(dh1);  // 2.
// Uses "unusual" template 
// copy-constructor.
Handle<Data> dh3 = oh;  // 3.
// Uses basic copy-constructor.
Handle<Data> dh4 = dh1; // 4.
Handle copy constructors are partial specializations of
template<class Arg1> 
Handle(const Arg1&);
template<class Arg1> Handle(Arg1&);
declared in unofficial.h (lines 3-9 in Listing 3). Therefore, the dh1-dh4 handles shown above are merely copies of oh. They are created using Handle copy constructors and point to the data initially created together with oh. What's more, if Other is not derived from Data, the lines will even fail to compile.

For this reason I introduced the Handle::create(...) functions — to provide a consistent interface for construction. It is the only interface that is able to create a new Handle-Data pair with a Data(Handle<...>) constructor.

That unfortunate inconsistency (and the only one, to my knowledge) "dethroned" the friendly Handle constructor-based interface and made it "unofficial." Nevertheless, I do prefer and use that syntax for its brevity and expressiveness. (Just keep in mind the special case.)

A Not-So-Conventional Pointer

Despite being similar to conventional pointers, Handle<Data> has a far stronger association with Data it represents. For the sake of performance and safe Data resource management, Handle<Data> is solely responsible for the complete life cycle of an associated Data instance — creation, access, and deletion. Therefore, a Handle<Data> instance guarantees the existence and validity of Data:
Data*          dp; // Unassigned, unusable.
auto_ptr<Data> ap; // Unassigned, unusable.
Handle<Data>   dh; // Creates a Data instance if the
                   // class has default constructor.
                   // Else, simply does not compile.
dp->modify(); // Trouble
ap->modify(); // Trouble
dh->modify(); // OK
The strong bond between Data and Handle<Data> supports the notion that objects should be declared when they are needed and, therefore, initialized. It differs from unassigned C-style declarations. This difference must be remembered when making the transition from raw pointers and auto_ptrs to Handles.
Data*          dp1, dp2, dp3;
auto_ptr<Data> ap1, ap2, ap3;
Handle<Data>   dh1, dh2, dh3;
Although the three lines look quite similar, the third one is far from being a mere replacement for the first two. This line actually creates three Handle<Data> instances together with Data instances. Thus, it is a proper replacement for:
Data* dp1 = new Data();
Data* dp2 = new Data();
Data* dp3 = new Data();
I understand that under rare circumstances the initialize-when-declared rule is difficult and/or inefficient to enforce. If that is the case, the function Handle::null (lines 103-108 in Listing 1) comes to the rescue:
// Create an empty Handle instance
// No Data are associated with the 
// handle
Handle<Data> h = Handle<Data>::null();

h->access_data(); // Trouble.
...
if (something)
   h = Handle<Data>::create(arg1);
else
   h = Handle<Data>::create(arg2, arg3);

h->access_data(); // OK.
Handle::null returns a special Handle instance — an analog of null pointer — that is not associated with any data. The instance is potentially dangerous, as attempts to access non-existing data are obviously not valid. Therefore, the construction of the instance is explicit and highly visible. So, if you use Handle::null instances and face a mysterious memory corruption problem, start looking for Handle::null calls and then make sure that the corresponding handles are used properly.

Performance

Additional functionality carries additional performance overhead. The cost of passing a Handle<Data> to a function is roughly twice as much as simply passing a Data * pointer. In other words, it takes twice as long to call an empty func(Handle<Data>) as to call an empty func(Data*). Most often the overhead is negligible comparing to the application's overall operational costs. For example, when sorting of an array of ten integer elements, the function qsort is roughly 100 times as expensive as the overhead required to pass in a pointer to the array.

Also, it is often possible to pass Handle by reference. A func(const Handle<Data>&) call does not activate the reference-counting mechanism and does not incur any additional overhead. However, Handle was not designed to be passed by reference as a general technique; you have to understand the implications of doing so.

To Be Developed

For various reasons I left out some functionality that I would still like to mention briefly.
Traditional C-style error processing (in which a function returns an error status rather than throws an exception) was one of the "features" of the original implementation [1]. Since then, I grew up to accept Stroustrup's arguments ([9] pg. 355-356) favoring the C++ exception mechanism over the traditional C-style error handling. And Handle::null looks sufficient to handle "exceptions that are not errors" ([9] pg. 374). In other words, conditions that are not "exceptional" enough to signify an error (for example, to indicate a not-found result of a find request). However, if you feel the need for Handle-based C-style error processing, take a look at the counter.h file posted on CUJ web site for a way to incorporate the functionality into Handle without performance sacrifice.

Handle in its presented form employs only the default memory allocation mechanism (global new and delete). The integration of custom allocators in the spirit of STL should be the next logical step in Handle development:
template<class Data, class Allocator =allocator<Data> >
class Handle {...};
Environment

The code for this article was developed and tested on SPARC Solaris 2.6 using gcc-2.95.2. I wouldn't be surprised if older compilers failed to support some of the newer features of the C++ Standard used by this implementation.

Summary of Advantages and Known Limitations

The Handle<Data> implementation here has several advantages over more traditional implementations. The following list is a recap of the advantages mentioned at the beginning of this article:

Handle<Data> is fully automatic.

It is safe.

It imposes no requirements on the Data class (such as modification to include a reference count).

It closely matches the syntax and behavior of conventional pointers.

In addition, Handle has some advantages not yet mentioned:

Handle allocates no additional memory blocks to accommodate reference-counting infrastructure (unlike [7, 8]). Therefore, it is quicker (allocates/deletes one memory block instead of two) and uses considerably less memory.

It uses one level of indirection to access both application data and reference-counting infrastructure.

Handle instances are truly lightweight objects, having a size of just one pointer (also unlike [7, 8]).

Handle clears up the eternal puzzle of the const Data* const syntax, in which it is difficult to remember which const modifies what. Handle<const Data> represents a non-constant handle to constant Data and const Handle<const Data> is clearly a constant handle to constant Data. Although not terribly important, this feature helps readability.

Handle provides "pointer semantics" and for many applications is a safe and trouble-free replacement for conventional pointers and explicit memory management (new and delete). I often find Handle to be an easier and safer alternative to the standard auto_ptr as well.

Following are a couple of limitations of the current design:
It is not capable of supporting multiple inheritance:
class A {...};
class B {...};
class C : public A, public B {...};

// Upcast.
Handle<A> ah = Handle<C>(); // OK
Handle<B> bh = Handle<C>(); // Problem
However, from my experience, multiple inheritance is an exceptionally rare beast. For my applications, the benefits of Handle generally outweigh this deficiency. However, if your situation is different, you must consider other alternatives.
Reference counting, as a programming concept, does not have many weak points. One of the most often mentioned is that it cannot handle cyclical references. A cyclical reference can occur when two or more objects possess reference-counted handles to each other. If the chain of references starting with any object leads back to that object, it is a cyclical reference. An example would be two instances having embedded handles pointing to each other:
class A
{ ...
   Handle<A> _other;

   void reference(Handle<A> ot) { _other = ot; }
}

Handle<A> a1;
Handle<A> a2;

a1->reference(a2);
a2->reference(a1);
Such a system will fail to handle destruction properly. In this case, there will be a memory leak when the handles go out of scope, because neither will be able to destroy its owned instance of A.

In the current design I do not implement exception handling. In failing to do so, I am not being deliberately malicious. Writing exception-safe software is not a simple task. Analysis of implications caused by exceptions would likely require an article of its own. Therefore, I deliberately avoided the issue. Although I currently use the Handle in its presented form, I consider the implementation being a reasonably well working concept rather than an industrial-strength product. Therefore, criticism and improvements are most welcome.

References

[1] Vladimir Batov. "Extending the Reference-Counting Pattern," CUJ, September 1998.

[2] Scott Meyers. Letter to the Editor, CUJ, December 1998.

[3] Scott Meyers. More Effective C++ (Addison-Wesley, 1996).

[4] Marshall Cline. C++ FAQ (part 5 of 9). http://www.faqs.org/faqs/C++-faq/part5 and http://www.cerfnet.com/~mpcline/c++-faq-lite/freestore-mgmt.html#[16.22].

[5] Paul T. Miller. "Reference-Counted Smart Pointers and Inheritance," C++ Report, October 1999

[6] Greg Colvin. Specifications for auto_ptr and counted_ptr. comp.std.c++, posted on 25 May 1995.

[7] Kevin S. Van Horn. "Smart Pointers," http://www.xmission.com/~ksvhsoft/code/smart_ptrs.html.

[8] Kenneth Ngai. "A Template for Reference Counting," CUJ, August 1997.

[9] Bjarne Stroustrup. The C++ Programming Language, Third Edition (Addison-Wesley, 1997), pp. 782-785.

Vladimir Batov is a senior software engineer currently working for Raytheon Systems Company (Marlborough, MA). During his 16-year career, he has participated in various software development projects including a full-scale nuclear power station simulator, Air Traffic Control systems, and high-availability communication, monitoring, and financial systems in Unix using C/C++. Batov has written several other articles on C++ programming for C/C++ Users Journal. He can be reached at vladimir@res.ray.com.