Title: auto_value: Transfer Semantics for Value Types

Author:

Date: 04 June 2007 11:55:00 +01:00 or Mon, 04 June 2007 11:55:00 +01:00

Summary: std::auto_ptr has a reputation for causing problems due to its surprising copy/assignment semantics. Richard Harris tries to separate the good ideas from the bad.

Body:

The problem of eliminating unnecessary copies is one that many programmers have addressed at one time or another. This article proposes an alternative to one of the most common techniques, copy-on-write. We'll begin with a discussion on smart pointers, and why we need more than one type of them. We'll then look at the relationship between smart pointers and the performance characteristics of some simple string implementations, including one that supports copy-on-write. I'll suggest that a different choice of smart pointer better captures our intent, and show that what we were trying to do doesn't achieve half as much as we thought it would.

Finally, I hope to show that whilst the problem we set out to solve turns out to be a bit of a non-issue, this technique has a side effect that can be exploited to dramatically improve the performance of some complex operations.

     article::article()

I'd like to begin by recalling Jackson's Rules of Optimization.

Rule 1: Don't do it.
Rule 2 (for experts only): Don't do it yet.

This is probably a little presumptuous of me, but I'd like to add something:

Harris's Addendum: Nyah, nyah. I can't hear you.

I'll admit it's not very mature, but I think it accurately reflects how we all really feel. No matter how much a programmer preaches, like Knuth, that premature optimisation is the root of all evil, I firmly believe that deep down they cannot help but recoil at inefficient code.

Don't believe me? Well, ask yourself which of the following function signatures you'd favour:

  void f(std::vector<std::string> strings);
  void f(const std::vector<std::string> &strings);

Thought so.

But you mustn't feel bad about it, the desire to write optimal code is a good thing. And I can prove it.

In their seminal 2004 paper, 'Universal Limits on Computation', Krauss and Starkman demonstrated that the universe will only be able to process another 1.35x10¹²⁰ bits during its lifetime. Count them. Just 1.35x10¹²⁰. If Moore's Law continues to hold true, we'll run out of bits in 600 years.

So we can stop feeling guilty about our oft-criticised drive to optimise, because wasted CPU cycles are accelerating the heat death of the universe.

Will nobody think of the children?

Act responsibly.

Optimise.

OK, that's a little disingenuous. Knuth actually said that in 97% of cases we should forget about small efficiencies. I suspect that we'd all agree that using const references by default for value types generally falls into the 3% that we shouldn't ignore. There is, after all, a world of difference between choosing the more efficient of two comparably complex statements and significantly increasing the complexity of your code in the name of a relatively small efficiency gain.

There is a grey area though. Sometimes it really is worth increasing the complexity of your code for relatively small gains. Especially when the particular source of inefficiency occurs regularly within your code base and you can hide that complexity behind a nice tightly defined class interface.

This article is going to take a look at those most profligate of wastrels, temporaries.

But since the direct route rarely has the most interesting views, we're going to set off with a discussion on smart pointers.

auto_ptr

Let's start by taking a look at the definition of auto_ptr (see Listing 1).

 template<typename X>
 class auto_ptr
 {
 public:
 typedef X element_type;
   explicit auto_ptr(X *p = 0) throw();
   auto_ptr(auto_ptr &p) throw();
   template<class Y> auto_ptr(auto_ptr<Y> &p)
      throw();
   auto_ptr(auto_ptr_ref<X> p) throw();
   ~auto_ptr() throw();
   auto_ptr & operator=(auto_ptr &p) throw();
   template<class Y> auto_ptr &
      operator=(auto_ptr<Y> &p) throw();
   auto_ptr & operator=(auto_ptr_ref<X> p)
      throw();
   template<class Y> operator auto_ptr_ref<Y>()
      throw();
   template<class Y> operator auto_ptr<Y>()
      throw();
   X & operator*() const throw();
   X * operator->() const throw();
   X * get() const throw();
   X * release() throw();
   void reset(X *p = 0) throw();
 private:
   X *x_;
 };

Listing 1

It's a little bit more complicated than you'd expect isn't it?

This is because, like HAL from Clark's 2001: A Space Odyssey, it has been driven ever so slightly barking mad from being given two competing responsibilities. The first of these is to tie the lifetime of an object to the scope in which it's used.

For example:

void
f()
{
  const auto_ptr<T> t(new T);
  //...
} //object is destroyed here

The destructor of the auto_ptr deletes the object it references, ensuring that it is properly destroyed no matter how we leave the scope.

The second responsibility is to safely transfer objects from one location to another.

For example:

auto_ptr<T>
f()
{
  return auto_ptr<T>(new T);
}

void
g(auto_ptr<T> t)
{
  //...
} //object is destroyed here

void
h()
{
  auto_ptr<T> t;
  t = f(); //ownership is transferred from f here
  g(t);    //ownership is transferred to g here
}

The two roles are distinguished by the constness of the auto_ptr interface. The const member functions of auto_ptr manage lifetime control, whereas the non-const member functions manage ownership transfer.

For example, by making the variable t in the function h in the previous example const, we can ensure that the compiler will tell us if we accidentally try to transfer its ownership elsewhere:

void
h()
{
  const auto_ptr<T> t;         
  t = f(); //oops         
  g(t);    //oops       
}

And herein lies the problem. We want constauto_ptrs to jealously guard their contents, so we make the arguments to the transfer constructor and assignment operator non-const references. But, unnamed temporaries, such as function return values, can only be bound to const references, making it difficult to transfer ownership of an object out of one function and into another.

For example:

void
h()
{
  g(f()); //now I'm confused       
}

This is where the mysterious auto_ptr_ref class comes to our rescue. You'll note that auto_ptr has a non-const conversion to auto_ptr_ref and that there's a conversion constructor that takes an auto_ptr_ref. So a non-const unnamed temporary can be converted to an auto_ptr_ref, which will in turn transfer ownership to an auto_ptr via the conversion constructor.

Neat, huh?

Well, perhaps. But we could almost certainly do better by giving each of auto_ptr's personalities its own body. We'll do this by introducing a new type, scoped_ptr, to manage object lifetimes and stripping those responsibilities from auto_ptr.

The definition of scoped_ptr is as shown in Listing 2.

template<typename X>
class scoped_ptr
{
public:
  typedef X element_type;

  explicit scoped_ptr(X *p = 0) throw();
  explicit scoped_ptr(
     const auto_ptr<X> &p) throw();
  ~scoped_ptr() throw();

  X & operator*() const throw();
  X * operator->() const throw();
  X * get() const throw();

  auto_ptr<X> release() throw();
private:
  scoped_ptr(const scoped_ptr &); // not
                                  // implemented
  scoped_ptr & operator=(const scoped_ptr &);
                                //not implemented
  X * x_;
};

Listing 2

Those in the know will see the similarity with the boost scoped_ptr (www.boost.org). This is only natural since I pretty much just swiped it from there.

As with the original auto_ptr, the constructors take ownership of the objects passed to them and the destructor destroys them. The principal change is that it is no longer legal to copy or assign to scoped_ptrs (the unimplemented private copy constructor and assignment operator are there to suppress the automatically generated ones).

We can continue to use scoped_ptr to tie object lifetime to scope:

void
f()
{
  scoped_ptr<T> t(new T);
  //...
} //object is destroyed here

But we can no longer use it to transfer ownership:

scoped_ptr<T> //oops, no copy constructor
f()
{
  return scoped_ptr<T>(new T);
}
void
g(scoped_ptr<T> t) //oops, no copy constructor
{
  //...
}
void
h()
{
  scoped_ptr<T> t;
  t = scoped_ptr<T>(new T); // oops, no assignment
                            // operator
}

Now let's have a look at how giving up responsibility for lifetime control changes auto_ptr (Listing 3).

template<typename X>
class auto_ptr
{
public:
  typedef X element_type;
  explicit auto_ptr(X *p = 0) throw();
  auto_ptr(const auto_ptr &p) throw();
  template<class Y> auto_ptr(
     const auto_ptr<Y> &p) throw();
  ~auto_ptr() throw();
  const auto_ptr & operator=(
     const auto_ptr &p) const throw();
  template<class Y>
    const auto_ptr & operator=(
       const auto_ptr<Y> &p) const throw();
  X & operator*() const throw();
  X * operator->() const throw();
  X * release() const throw();
private:
  mutable X *x_;
};

Listing 3

OK, so I lied a little.

We haven't so much lost the ability to control object lifetimes with auto_ptr as made it a little less attractive. The constructors still take ownership of the objects passed to them and the destructor still destroys them, but holding on to them is difficult.

This is because the object pointer is now mutable, allowing it to be changed even through const member functions. Usually mutable is reserved for members that can change whilst the object maintains the appearance of constness (caches, for example), an idea typically described as logical constness. Here, to be honest, it's a bit of a hack. We need to tell the compiler to abandon all notions of constness for auto_ptrs and unfortunately we can't do that (unnamed temporaries rear their problematic heads again). So we lie to the compiler. We tell it that "no, really, this function is const" and use mutability to change the object pointer anyway.

We can still use auto_ptr to transfer object ownership from one place to another:

auto_ptr<T>
f()
{
  return auto_ptr<T>(new T);
}
void
g(auto_ptr<T> t)
{
  //...
} //object is destroyed here
void
h()
{
  auto_ptr<T> t;
  t = f(); //ownership is transferred from f here
  g(t);    //ownership is transferred to g here       
}

But we might run into problems if we try to use it to control object lifetime:

T
h()
{
  const auto_ptr<T> t;
  g(t);      //ownership is transferred to g here
  return *t; //oops
}

It's precisely because this new auto_ptr is so slippery, that I've added a release method to boost's scoped_ptr. This enables us to use the scoped_ptr to control the lifetime of the object within a function and auto_ptr to control its transfer during function return.

For example:

auto_ptr<T>
f()
{
  scoped_ptr<T> t;
  //...
  return t.release();
}

void
g()
{
  scoped_ptr<T> t(f());
}

I shall keep the name auto_ptr for this new ownership transfer pointer despite many reasonable arguments against doing so. Firstly, I believe that auto_ptr has strong associations with transfer semantice for most of us. Secondly, and far more importantly, it has led to a much snappier title for this article than the alternative.

Henceforth, therefore, when we refer to auto_ptr, we will mean this new version, having the sole responsibility of ownership transfer.

shared_ptr

Another approach to managing object lifetimes is to allow multiple references to share ownership of an object. This is achieved by keeping the object alive for as long as something is referring to it.

There are two common techniques used to do this, the correct approach and the easy approach. Guess which one we're going to look at.

That's right. Reference counting.

Reference counting works by keeping a count of the number of active references to an object and deleting it once this count drops to zero. Each time a new reference is taken, the count is incremented and each time a reference is dropped, the count is decremented. This is generally achieved by requiring the referencing entity to explicitly register its interest or disinterest in the object.

The chief advantage of using reference counting to implement shared ownership semantics is that it's relatively simple compared to the alternative.

The chief disadvantage occurs when an object directly or indirectly holds a reference to itself, such as when two objects hold references to each other. In this situation, the reference count will not fall to zero unless one of the objects explicitly drops the reference to the other. In practice, it can be extremely difficult to manually remove mutual references since the ownership relationships can be arbitrarily complex. If you would like to bring a little joy into someone's life, ask a Java programmer about garbage collection.

We can automate much of the book-keeping required for reference counting by creating a class to manage the process for us. In another shameless display of plagiarism I'm going to call this class shared_ptr (see Listing 4).

template<typename X>
class shared_ptr
{
public:
  typedef X element_type;
   shared_ptr() throw();
  template<class Y> explicit shared_ptr(Y * p);
  shared_ptr(const shared_ptr &p) throw();
  template<class Y> shared_ptr(
     const shared_ptr<Y> &p) throw();
  template<class Y> explicit shared_ptr(
     const auto_ptr<Y> &p);
  ~shared_ptr() throw();
  shared_ptr & operator=(
     const shared_ptr &p) throw(); 
  template<class Y>
    shared_ptr & operator=(
       const shared_ptr<Y> &p) throw();
  template<class Y>
    shared_ptr & operator=(
       const auto_ptr<Y> &p) throw();
  X & operator*() const throw();
  X * operator->() const throw();
  X * get() const throw();
  void reset(X *p = 0) throw();
  bool unique() const throw();
  long use_count() const throw();
private:
  X *x_;
  size_t *refs_;
};

Listing 4

The reference count is pointed to by the member variable refs_ and is incremented whenever a shared_ptr is copied (either through assignment or construction) and decremented whenever a shared_ptr is redirected (either through assignment or reset) or destroyed.

For example:

void
f()
{
  shared_ptr<T> t(new T); //*refs_==1          
  {
    shared_ptr<T> u(t); //*refs_==2          
    //...
  } //*refs_==1
  //...       
} //*refs_==0, object is destroyed here

Reference counting blurs the distinction between object lifetime control and transfer by allowing many entities to simultaneously "own" an object.

shared_ptr<T>
f()
{
  return shared_ptr<T>(new T);
}
 void
g(shared_ptr<T> t) //++*refs_       
{
  //...       
} //--*refs_        

void
h()
{
  shared_ptr<T> t;
  t = f(); //ownership is transferred from f here
  g(t);    //ownership is shared with g here       
}

The sequence of events in the above example runs as shown in Figure 1.

call h
shared_ptr()

call f
new T
shared_ptr(T *)                     //*refs_=1     
shared_ptr(const shared_ptr &)      //++*refs_    
~shared_ptr                         //--*refs_     
exit f

shared_ptr::operator=(const shared_ptr &)

                                  //++*refs_
~shared_ptr                        //--*refs_
call g
shared_ptr(const shared_ptr &)     //++*refs_     
~shared_ptr                        //--*refs_
exit g

exit h
~shared_ptr                        //--*refs_

Figure 1

As you can see, at the end of h, the reference count is zero and the object is consequently destroyed.

Since the object has more than one owner we must exercise caution when using it or, more specifically, when changing its state.

For example:

void
f(shared_ptr<T> t)
{
  //...       
}

void
g()
{
  shared_ptr<T> t(new T);
  shared_ptr<const T> u(t);
  f(t);    //ownership is shared with f here                  
            //state of u is uncertain here
}

Of course, this is just pointer aliasing in a spiffy new suit and as such shouldn't come as much of a surprise. I mean, nobody makes that mistake these days, do they?

Well, almost nobody.

Well, certainly not standard library vendors.

Well, probably not standard library vendors.

Well, probably not very often.

string

The last time I saw this problem was in a vendor supplied std::string. Well, not this problem exactly, but it was related to incorrect use of reference counted objects. I shan't name names, but it was a company you all know and many of you respect. When I finally tracked down what was causing my program to crash I was stunned.

Now you may be wondering how these sorts of problems could possibly relate to string, after all it's a value type not an object type. The reason is that this particular string used a common optimisation technique known as copy-on-write, or COW for short, and this technique relies upon reference counting.

Next time, we'll take a look at string and the implications of the COW optimisation.

#include

Krauss and Starkman. Universal Limits on Computation (arXiv:astro-ph/0404510 v2, 2004).

Clark, 2001: A Space Odyssey (Hutchinson, 1968).

Acknowledgements

With thanks to Kevlin Henney for his review of this article and Astrid Osborn, Keith Garbutt and Niclas Sandstrom for proof reading it.

Notes:

More fields may be available via dynamicdata ..

Journal Articles

Title: auto_value: Transfer Semantics for Value Types

auto_ptr

string

#include

Acknowledgements