Smart Pointers Reloaded

href="http://twimgs.com/ddj/cuj/images/cujexp0310alexandr/smart_ptr.zip">Click here for the source code that accompanies this article.

Judging by the fact that the late Generic<Programming> installments appeared in co-authorship, it might look like your's truly is losing his mojo. Disturbing as this might be, the thought doesn't stop me in the least from proudly introducing David B. Held as this month's guest star.

David, one of the whizzes at Boost [1], crafts great library components and, on occasion, engages in lively debates with the undersigned. Dave and I met there and on comp.lang.c++.moderated, another great hang-out place if you enjoy programming and exchanging opinions within the confines of a friendly community.

If you tune into Boost or comp.lang.c++.moderated, you could hardly miss the discussions on smart pointers. Truly, smart pointers are an evergreen subject of conversation, coding preoccupation, and scrutiny. Strings would follow closely. But while the C++ Standard calmed string-mania by offering a less-than-perfect but definitely functional string design, the quest for "the" smart pointer is relentless, because, let's face it, auto_ptr just doesn't cut it.

Nowadays, there seem to be two main approaches to smart pointers:

• Policy-based design, promoted by the Loki::SmartPtr model and described in Modern C++ Design [2].
• A fixed design, chosen carefully and implemented with craft. This approach is promoted, among others, by the Boost [1] shared_ptr component.

Each model of smart pointer has advantages and disadvantages, the relative weights of which are sometimes subjective.

The good news is that the Boost smart pointer has been accepted as part of the C++ Standard Technical Report 1. The Technical Report contains features that will likely be part of the next revision of the C++ Standard. David and I are working on a second proposal, which is designed to supersede (by inclusion) the current proposal. This plan depends on a number of technical and political stars getting aligned properly, however.

This article presents a refined smart pointer implementation, written by David, starting from Loki::SmartPtr. We'll discuss a number of challenges and solutions that are often encountered in the context of a policy-based design, and we'll make some measurements on the tradeoffs imposed by commonly-used policy combinations.

Mailcontainer

Lately I've been getting an unusually high volume of emails from readers, so I said I'd inaugurate the Mailcontainer section (Mailbag sounds so, um, Smalltalkish). I plan on including the most interesting emails here. Please vote (again via email, which confers to email the closure property) if you'd like me to keep this section.

Credit should always go to (considered harmful... ah, Freudian slip) where it's due, and good names are important, so here's an email I got from Sam Lindley:

I was recently browsing the CUJ website: www.cuj.com when I came across the text: "...The inimitable due of ScopeGuard fame hits again..." I thought that sounded rather familiar. Sure enough, I posted a (somewhat frivolous) message to comp.lang.c++.moderated, just over 3 years ago asking whether my simple class 'ScopeGuard' was well-named. This was part of a thread on what to call the "Resource Acquisition Is Initialization" idiom. (Try a search on groups.google.com for "ScopeGuard Lindley" [3]) The only reply argued that my class wasn't well-named, which was fair enough, given that my class was just a very simplified special case of what you described in your ScopeGuard article 6 months later. [...] I'm not really bothered about you stealing my name ;-) and I like the article. But I am curious... as to whether you realized I'd used it previously.

I didn't remember having seen the post, but then I saw I did participate in that thread (which I had forgotten as well)! Memory has weird ways. Most likely, I did retain the name someplace in unaddressable memory, to conveniently "invent" it later. Thanks Sam.

Smart Pointers: Can't Live With 'Em, Can't Live Without 'Em

When it comes to smart pointers, there's only one person who knows the one true right way to implement them—and that person is you. Quot homines, tot sententiae, the Latin bard said [4], and although he isn't available for comment, I'd bet money he had smart pointers in mind when writing that.

Amid the many variations, two schools of thought have developed over time.

One school argues that programmers should choose the most commonly needed features of a smart pointer, and carefully craft a smart pointer class around them; there are certainly many choices, and within the implementation space, there are also many decisions to make. The result is a nicely distilled smart pointer that is appropriate and useful to a large range of applications. A good representative of such a school of thought is Boost's smart pointer library, contributed to by many, either through direct development, or ideas aired on the Boost mailing list. So such a smart pointer's declaration would look like this:

template <class T>
class classic_sp;

Another school of thought, pioneered by Modern C++ Design, is to apply policy-based design to smart pointers. I'll assume you know about policy-based design (if not, see my book Modern C++ Design).

The way a policy-based smart pointer would look is:

template
<
    typename T,
    template <typename> class OwnershipPolicy = ref_counted,
    template <typename> class ConversionPolicy = disallow_conversion,
    template <typename> class CheckingPolicy = assert_check,
    template <typename> class StoragePolicy = scalar_storage
>
class pb_sp;

While its baroque syntax might induce vertigo at first, the design of a policy-based smart pointer is flexible, letting you customize the pointer in unbounded ways by tinkering with its template arguments. The pros of such an approach are flexibility, adaptability to unforeseen needs, and efficiency. Also, the design decisions (policies passed) are part of the type of the smart pointer, which might be an advantage or a disadvantage, depending on context. At any rate, if dynamically-bound behavior is what you want, you can, of course, define a policy that implements that and use it throughout—whereas you cannot retrofit extra type checking into a classic design. What is achievable with a specialized smart pointer is often implemented more easily by customizing the relevant policies.

Loki's policy-based smart pointer was received with reticence by many. The most important concerns pertain to portability to non-compliant compilers. Another justified social concern is that there is "too much flexibility" going on. Murphy's Law for library writers would be "if something is customizable, then everybody in a team will customize it in ways that are incompatible with each other." The apocalyptic scenario feared by some would involve a large team of clever developers, many of whom write their own policies for fun and usefulness. Say, for example, that John Doe in the U.S. team defines a set of policies and uses the type:

typedef SmartPtr<Widget, uncounted, disallow_conversion, super_check>
    PWidgetUS;

At the same time, Fred Nurk in the Australian team uses:

typedef SmartPtr<Widget, discounted, allow_conversion, no_check_only_cash>
    PWidgetAus;

Then, ouch, they try to integrate their code, and make it possible for these types to coexist with each other, and even be convertible to each other when invoking functions from one team to the other!

Policy-based design allows and solves these cases by copying objects policy by policy, so it is up to the implementers to decide which policies convert to which, and in what ways. However, this approach might be more clumsy than you would find worthwhile.

The intended use of policy-based smart pointers is that smart pointer definitions such as the above are carefully chosen by a small team of designers and consistently used throughout. Which brings us to another inconvenience of policy-based smart pointers: the long definitions naturally suggest using typedefs, but typedefs don't work well with inheritance.

Say, for example, that John Doe convinces the whole team to use his PWidgetUS. Let's call it PWidget. Then, everybody merrily uses this symbolic type, until Fred Nurk defines a class Midget, derived from Widget, and wants to use a smart pointer with it having the same policies as PWidget, just replacing Widget with Midget. Then, ouch, he'd need to copy and paste PWidget and then facelift it into:

typedef SmartPtr<Midget, uncounted, disallow_conversion, super_check>
    PMidget;

Copy-and-paste is a capital sin, so this solution is definitely not satisfactory. The one true solution would be to use template typedefs, a feature that has been asked for a long time, and that now is being formally proposed for C++ standardization [10]. In that distant future Star Trek-ish world, Fred would write:

template <class WidgetAndDescendants>
typedef SmartPtr<WidgetAndDescendants, uncounted, disallow_conversion, super_check>
    PWidget;

Now you can say PWidget<Widget>, PWidget<Midget>, and PWidget<Gadget>—and they all nicely map to the same typedef by replacing WidgetAndDescendants with the passed-in type.

Absent that feature, there are a number of less-than-ideal solutions. (Did I hear macros?) One solution is to follow an idea promoted by the standard allocators, namely, to put a typedef inside the smart pointer template, as follows:

template
<
    typename T, policies 
>
class smart_ptr
{
    ...
public:
    template <class U> struct rebind
    {
        typedef smart_ptr<U, policies> other;
    };
};

And then you can define PMidgetUS by using the marvelously ingenious and highly expressive syntax:

typedef PWidgetUS::rebind<Midget>::other PMidget;

You either hate it, or just dislike it—but it does the trick. Other solutions involve traits, variations on the nested typedef theme, and so on. There seems to be none that is 100 percent satisfactory, so now you know why some just prefer the classic design that doesn't require that much typ(edef)ing.

As an interesting psychological/perception issue, people who prefer the classic design for this particular reason seem to forget that the default parameters of a policy-based smart pointer provide the exact functionality AND syntactic convenience of a classic design. Naturally, the default arguments would be the most frequently used and would engender a best-of-the-breed smart pointer, a situation in which all you have to do is to say smart_ptr<Widget> here, smart_ptr<Midget> there, and so on—exactly the same as with a classic design! But it seems like as soon the potential functionality is in there, the expectation bar rises automatically as well.

Another interesting aspect is that no gripes come from people who actually are using Loki's policy-based smart pointer. So now there are those who use it and like it, and those who don't and don't.

All in all, in the over two years of getting feedback from Loki users, it looks like the fundamental design of Loki's smart pointer turned out to be sound, modulo a number of mistakes and suboptimalities that Dave addressed, and that we're going to get into below.

Size Does Matter

Loki's original smart pointer publicly inherited from each of its policies. This heretical use of inheritance, typical for policy-based designs, allows policies considerable freedom in tweaking the smart pointer interface.

Except for the storage policy, which actually contains the raw pointer, any other policy likely contains no state at all. Actually, the known implementations of the Conversion and Checking policies never contain any data members at all.

In a perfect world, it would follow that the compiler takes advantage of the Empty Base Optimization [6] and smartly and nicely folds the space occupied by the empty base classes into non-existence. However, most of today's compilers don't apply EBO as full heartedly in the presence of multiple inheritance. Thinking that that's the compilers' limitation, I was staying cool: Why do what works now when you can do what'll work later and take six months off? That blissful state, however, lasted only until Vesa Karvonen opined that it might be the C++ Standard itself that limits applicability of EBO.

In particular, Vesa refers to Chapter 10.1, Paragraph 4, which says:

A base class specifier that does not contain the keyword virtual, specifies a nonvirtual base class. A base class specifier that contains the keyword virtual specifies a virtual base class. For each distinct occurrence of a nonvirtual base class in the class lattice of the most derived class, the most derived object (1.8) shall contain a corresponding distinct base class subobject of that type. [...]

Distinct would mean, different addresses—hence the need for each base to occupy space. Matters are not as clear, though, because other sections make it clear that you shouldn't be in the business of comparing addresses of objects of incompatible types, even after you converted them to void*. But when template templates come into play, it becomes increasingly hard for the compiler to keep a clear mind—so the compiler often chooses the conservative route and reserves a few unused bytes even for empty subobjects.

Dave decided to write something that works and not take the six months off, and he came up with a clever solution starting from an idea that I have posted online [8]. The basic idea is to inherit discriminately: if a class is "substantive" (that is, has some member variables), it will be inherited. Otherwise, it is not needed as part of the object and is discarded from the inheritance lattice.

To implement this idea, you need two things:

• A way to tell that an object is empty (that's not as trivial as it looks; don't forget that sizeof(T) is never zero, even when T has no members);
• A way to either inherit or not inherit a type, based on the Boolean condition above.

The first mechanism is implementable, assuming you have a compiler that applies EBO for the simplest case of single inheritance: you lure the poor compiler by giving it the opportunity to apply EBO for your tested type T, then you detect whether it did apply EBO or not.

The basic idea is simple, you just need to write something like:

template <class T>
class is_empty
{
    struct witness { int someData_[256]; };
    struct probe : public T { int someData_[256]; };
public:
    enum { result = sizeof(witness) == sizeof(probe) };
};

Sweet! Now, making is_empty general enough to cope with primitive data types (true, in this case we don't care about that), and most of all moody compilers, takes considerably more work. Fortunately, in this case we can do that thing with the shoulders of giants, because Boost already has a well-tuned and tested implementation of is_empty. If you put into equation four C++ experts fighting against a dozen compilers, the code above expands to about 209 lines.

But that was the easy part. When writing the second piece of code (the discriminating inheritance), things become, as the groom who changed his mind in the last minute would say, "a little tense."

Again, in principle things are pretty simple. Just devise a template class taking two types and two Booleans (that specify whether the two types are empty or not), and then specialize on the four possible combinations:

template <class T, class U, 
    bool TEmpty = is_empty<T>::result, bool UEmpty = is_empty<T>::result> 
class optimally_inherit;
// Case 0: none of T and U is empty: inherit both
template <class T, class U, false, false> 
class optimally_inherit : public T, public U
{
   ... forwarding constructors ...    
};
// Case 1: U is empty, T is not: inherit T only
template <class T, class U, false, true> 
class optimally_inherit : public T 
{
   ... forwarding constructors ...    
};
 ... two more cases ...

Generic programmers have learned to dread forwarding; in C++ it is surprisingly hard and unrewarding to write generic forwarding functions that preserve semantics. Take a look at optimally_inherit.hpp. What proper forwarding boils to in our case is writing some casts to properly guide the compiler on which type is intended for which recipient. Otherwise, the compiler has a zest for matching generic template constructors, even when the intent lies elsewhere. It took a lot of head scratching and some analysis from the Visual C++ team to figure out all the necessary casts.

You'll also notice that optimally_inherit implements swap, an important building block for efficient components. Whenever you define a type, consider providing a non-throwing swap operation for it.

So here's how smart_ptr looks with the size optimization in place:

template
<
    typename T,
    template <typename> class OwnershipPolicy = ref_counted,
    template <typename> class ConversionPolicy = disallow_conversion,
    template <typename> class CheckingPolicy = assert_check,
    template <typename> class StoragePolicy = scalar_storage
>
 class smart_ptr
    : public optimally_inherit<
        typename optimally_inherit<
            StoragePolicy<T>,
            OwnershipPolicy<T>
            >::type,
        typename optimally_inherit<
            CheckingPolicy<T>,
            ConversionPolicy<T>
            >::type
        >::type
    {
        ...
    };

As you see, the inheritance tree is formed by compounding optimally_inherit with itself, much as you would create a 4-tuple by having an std::pair store two std:pairs. (Speaking of pairs, regular Boost users might have noticed that optimally_inherit is in many ways the complement of compressed_pair.)

Member Functions versus Nonmember Functions

In an interesting article [9], Scott Meyers makes the argument that nonmember functions ought to be preferred because they increase encapsulation. The cost is that fun(obj) is not as cute as obj.fun(). The policy-based smart_ptr, and policy-based designs in general, prefer non-member functions for this and a couple of other reasons.

For one thing, visibility of names in base classes follows different rules than visibility of regular symbols. This can create problems for policy-based designs where the interest is to give each policy a fair chance at improving the interface of the final object of which the the policy is a part. If a policy just uses nonmember functions (sometimes friend functions), then normal overloading rules apply. Were the policy to define member functions, they will clash with synonymous names defined by another bona fide policy written by a fellow programmer! Or, if they have the same name as a member function defined by the final class, they become inaccessible.

The interesting conclusion here is: Prefer nonmembers to members. If you want dynamic behavior, you can call virtual member functions from inside the nonmembers no problem. There are various reasons for which this piece of advice applies; it does apply at its best in the case of smart pointers, which, in order to avoid confusion with their pointee objects, should stick with operator-> and operator* and define no named member function whatsoever.

Conclusion

This first article in a miniseries on policy-based smart pointers discusses the pros and cons of a policy-based approach as opposed to the well-known, less parameterized design. The unparalleled flexibility of policy-based smart pointers comes together with specific issues that need careful streamlining.

In the next installment of Generic<Programming> (which, by the way, will appear in dead tree edition) we'll continue discussing Dave's implementation of a policy-based smart pointer, in particular, ensuring exception safety.

[Editor's Note: The authors' charming note about "dead tree edition" refers to the fact that we are welcoming Generic <Programming> to the print version of CUJ starting in December 2003.]

Bibliography and Notes

[1] http://www.boost.org/
[2] Alexandrescu, Andrei. Modern C++ Design, Addison Wesley, 2001.
[3] http://groups.google.com/groups?selm=8eumi2%246uq%241%40news8.svr.pol.co.uk
[4] "How many men, so many thoughts". Publius Terentius Afer. Phormio, 454. Not a politically correct affirmation, but then this is not Oprah Magazine.
[5] http://std.dkuug.dk/JTC1/SC22/WG21/docs/papers/2003/n1431.htm
[6] Myers, Nathan. "The 'Empty Member' C++ Optimization," Dr. Dobb's Journal, August 1997. http://www.cantrip.org/emptyopt.html.
[7] Search the newsgroup comp.std.c++ for a thread entitled "Re: Obese compound objects??? >:o("
[8] http://article.gmane.org/gmane.comp.lib.boost.devel/1287/match=optionally+inherit
[9] Meyers, Scott. "How Non-Member Functions Improve Encapsulation," C/C++ Users Journal, February 2000.
[10] http://std.dkuug.dk/JTC1/SC22/WG21/docs/papers/2003/n1449.pdf