The Enbridge Inc. "REF" C++ Reference Counting Pointer Framework

REF provides much of the utility of automatic Garbage Collection, without giving up the C/C++ pointer semantics and efficiency you are used to, and without the non-deterministic overhead associated with most GC schemes.

Unlike other C++ Reference Counting Pointer frameworks, REF:

Requires no addition compilation or linkage to use. It is implemented in a single standard C++ header file.
Low size overhead. A ref::ptr<T> implements ref::ptr_tiny<T>, and is the same size as a T *, except for one small shared reference counter object (containing a C++ virtual table pointer, a T * pointer, and an integer) allocated the first time a dynamically allocated T object is referenced by a ref::ptr<T>. For improved efficiency, the reference counter can be easily added to the object itself, and ref::ptr automatically detects and uses it instead of allocating one. Adding the ref::counter requires 3 lines of code, or the use of a template at object allocation time. A ref::ptr_fast<T> is the size of 2 pointers, but is 100% as fast as a normal pointer for dereferencing.
Low speed overhead. Access to the object involves 1 extra virtual method invocation in addition to the normal pointer dereference, and is similar whether you've added a ref::counter to the object, or are using the automatically allocated one. Therefore, in most applications other than tight loops comprising millions of iterations accessing non-virtual methods or directly accessing the data members of the object, the ref::ptr<T> may be interchanged for a <T *>. Otherwise, simply dereference the ref::ptr<T> into a temporary variable to type <T &>, and use that in your central loop. Or, substitute a ref::ptr_fast<T> in speed-critical loops.
Maintains almost all normal C/C++ pointer semantics. For example, both ref::ptr<Base> and ref::ptr<Derived> can reference the same underlying object of class Derived, and all the correct pointer conversions are used.
Standard Template Library (STL) C++ Container friendly. Particularly useful when managing containers of dynamic objects. As soon as the last container forgets about a particular object, it auto-destructs! Imagine doing arbitrary std::set, std::map, or std::deque operations on containers of pointers to arbitrary objects, and never having to worry about deleting the objects when the containers are done with them. When they disappear from a std::set after a set operation, or when a std::map goes out of scope, the objects just disappear (unless some other ref::ptr still holds a reference.)

One perceived drawback that ref::ptr's have relative to full-blown Garbage Collection, is that co-referencing objects (objects that retain references to each-other), can prevent auto-destruction. This is usually easily avoidable. If you have objects containing ref::ptr's to other objects, that eventually point back to the original object, just make sure that one object breaks the "loop" of linkage when no longer required; they will then auto-destruct as appropriate. Otherwise, ref::ptr's seem highly efficient compared to most GC algorithms, are very safe and easy to use, and yield virtually all of the simplicity benefits of GC, without sacrificing space- or time- determinism.

If your code must be very space- and time-efficient, or has determinism requirements that cannot be met with the GC schemes available to you, then REF is an excellent choice. The space/time efficiency tradeoff of using ref::ptr<T>/ref::ptr_tiny<T> ( 1 x sizeof( T * ), but deference requires 1 virtual method invocation) vs. ref::ptr_fast<T> ( 2 x sizeof( T * ), but dereference is inlined) is totally within your control (see ref/ref.H). Both the "small" and "fast" versions are interchangable and assignable.

How-To

Here is an example of 3 ref::ptr<int>'s, managing a couple of dynamically allocated int objects. In this example, since the new <int> objects don't have their own ref::counter built in, ref::ptr<int> allocates one (shared by all ref::ptr's sharing the object).


#include <ref>

ref::ptr<int>		a( new int );		// new int 'A' on heap, 'a' holds ref::counter of 1 to 'A'
ref::ptr<int>		b;			// 'b's ref::counter is 0, and it's pointer ( *b, b->, ...) is 0.
b	= new int;				// new int 'B' on heap; 'b's ref::counter is 1
ref::ptr<int>		c;
c 	= b;					// 'b' and 'c' share ref::counter of 2 to 'B'
a	= c;					// 'A' freed; 'a', 'b' and 'c' share ref::counter of 3 to 'B'

Basically, just ensure that any dynamically allocated <object> is immediately assigned to a ref::ptr<object>. Then, make sure you only assign it between other ref::ptr's. When the last ref::ptr referencing it is assigned something else, the object will auto-destruct. Use the ref::ptr<object> as you would an (object *).

If you have control over the definition of a class, avoid allocating a dynamic ref::counter for each new object of the class by adding a built-in ref::counter: just add ref::counter<your_class> as a(nother) base class, and one virtual method:


     class your_class 
         : public ref::counter<your_class> {
         virtual your_class *__ref_getptr()  { return this; }
         /* ... the rest of your_class's declaration ... */
     }

To add a ref::counter to a class that you do NOT have control of (named "object", for example), derive a new class <rcobject> from the base class <object> and also the ref::counter<rcobject> base class, and add one new virtual method (the ref::counter methods must be virtual, in order to maintain proper pointer conversion and auto-destruction). This new <rcobject> is trivially convertible to <object>, and has a built-in ref::counter, avoiding the additional dynamic allocation for each new <object>:


class object { /* ... */ ; };

// Make an "object" having its own ref::counter; ref::ptr will use it..
class rcobject
  : public object
  , public ref::counter<rcobject> {
    virtual rcobject *__ref_getptr()  { return this; } // dereference the object
    /* ... */
};
ref::ptr<rcobject>	r = new rcobject;

An alternative method for adding a ref::counter to "object" is to use the ref::dyn<object> template:


// Add reference-counting and self-destruction to some other object
ref::ptr<ref::dyn<object> > o = new ref::dyn<object>

In both of these cases, the ref::ptr's will automatically detect and use the included ref::counter, instead of allocating one for each shared object. Use of ref::ptr's will be almost 100% as space-efficient as using a raw pointer to the object (one <int>, the reference counter, will be added to the size of the object)! No other dynamically or statically allocated objects of any kind are required for any housekeeping.

Other Implementations

The implementation of boost::shared_ptr<T> is comparable to ref::ptr_fast<T>. The size of each boost::share_ptr is 2 x sizeof( T * ), dereferencing is inlined (no virtual method invocations required), and a shared_counter is dynamically allocated for each group of shared_ptr<T>'s referencing a specific dynamically allocated T object.

The benefits of REF are several. First, the size of ref::ptr<T> is 1 x sizeof( T * ), at the cost of 1 virtual method invocation per dereference. So, if your application stores many, many pointers, then REF will cut your pointer storage space requirements by 50%. There is no equivalent in boost, that I am aware of.

Second, it appears that boost::shared_ptr always dynamically allocates a shared_counter object, whenever one (or more) smart_ptr's share a <T>. If your program creates many, many small T's, then the overhead of shared_counter allocated for each one will be significant (potentially doubling your dynamic memory requirements). Adding a ref::counter<T> as a base class of T will only increase the size of T by 1 integer and a virtual table pointer (the shared reference counter object). No other objects are then required for reference counting. Again, there appears to be no equivalent in boost.

Third, ref::ptr's are not thread-safe, and so do not have the overhead of thread-safety built into each reference increment/decrement. At first this may not seem to be a benefit, but I believe that it is. The details of transparently sharing dynamically allocated reference-counted storage between threads have proven too great for several widely supported implementations of std::string, produced by people much smarter than me, and all have been abandoned. Therefore, you may use ref::ptr's in multiple threads without protection, but do not assign or copy to/from them! Remember, copying one ref::ptr<T> to another involves a write to the shared reference counter, and destruction of the copy later involves another write! If you do copy, then all accesses to all copies must be encompassed by mutual exclusion intrinsics. In other words, treat them like any other shared object in the multi-threaded environment.

Examples

See the unit tests ref-test.C for many more examples. You can run the unit tests, and see their output here (the REF unit tests are implemented using CUT)

Define the preprocessor symbol REF_PTR_DEREF_FAST (see the GNU Make file GNUmakefile for an example ) to globally force ref::ptr<T> to implement ref::ptr_fast<T>, in applications where it is known in advance that speed is more important than space, all source code is available, and where compiled modules will never be shared outside of the compiled application.

Define the preprocessor symbol REF_PTR_COMPARE (see the GNU Make file GNUmakefile for an example ) to define functions that automatically compare ref::ptr<T> by their underlying pointers. This allows use of ref::ptr's as keys in sorted containers. If you wish to define such comparison methods yourself, you must put them in the namespace 'ref', or they will be hidden (probably by too many levels of template type deduction.)

Download

The latest version is always available in the ref-#.#.#.tgz file, here

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.