In the previous post I covered the motivation and basics of rvalue-references, one of the language additions in the next C++ standard. Today I will examine the changes that rvalue-references will bring to the way we write C++ code.

We will start with the following example:

typedef string Word;
typedef vector<Word> Words;
typedef map<Word, Words> SynonymMap;
 
Words words = ...
SynonymMap map;
 
for (Words::const_iterator i = words.begin ();
     i != words.end ();
     ++i)
{
  Words& syn = map[*i];
  // Load synonyms into syn.
}

Seeing that the code that loads all the synonyms for a particular word is quite long, we would like to move it into a separate function. The straightforward change would look like this:

Words load (const Word& w)
{
  Words r;
  // Load synonyms into r.
  return r;
}
 
Words words = ...
SynonymMap map;
 
for (Words::const_iterator i = words.begin ();
     i != words.end ();
     ++i)
{
  map[*i] = load (*i);
}

With the current state of C++ this code has a potential efficiency problem. As was discussed in the previous post, depending on the complexity of the load() function and C++ compiler used, the addition of the function call can result in the synonym list being copied twice. The first time in the load() function from r into a temporary and the second time from the temporary into the object stored in the map.

There are two common ways in which this inefficiency is addressed right now. The first involves passing a reference to the result object instead of returning it by value:

void load (const Word& w, Words& r)
{
  // Load synonyms into r.
}
 
Words words = ...
SynonymMap map;
 
for (Words::const_iterator i = words.begin ();
     i != words.end ();
     ++i)
{
  load (*i, map[*i]);
}

This approach has a number of drawbacks. For one, the code is unnatural. We wouldn’t have written it like this if we weren’t optimizing. More importantly, this approach is limited to cases where the type has the default constructor or we have enough information to create an empty instance before passing it to the load() function. Consider, for example, the following simple change to the above code:

typedef string Word;
typedef vector<Word> Words;
 
class Synonyms: Words
{
public:
  Synonyms (const string& source);
  ...
};
 
typedef map<Word, Synonyms> SynonymMap;

Now only the load() function knows how to construct the Synonyms object.

Both the return by value and pass by reference approaches have another drawback that may not be apparent at first. As we insert new entries, the synonym map may need to grow the underlying storage from time to time. When this happens, all the existing Words object are copied from the old storage to the new one.

The second way to deal with the inefficiency of returning the Words object by value is to allocate it on the heap and return a pointer instead:

typedef string Word;
typedef vector<Word> Words;
typedef map<Word, shared_ptr<Words> > SynonymMap;
 
shared_ptr<Words> load (const Word& w)
{
  shared_ptr<Words> r = new Words;
  // Load synonyms into r.
  return r;
}
 
Words words = ...
SynonymMap map;
 
for (Words::const_iterator i = words.begin ();
     i != words.end ();
     ++i)
{
  map[*i] = load (*i);
}

This approach forced us to change the way we store the synonym list in the map. It also requires an extra heap allocation for each Words object.

As we can see, with the current state of C++ there is no perfect solution to the problem of returning complex objects. If we return the object by value, we pay with two copies per call plus copying during the map growth. The pass by reference approach cannot always be used and also suffers from the map growth overhead. Finally, the return by pointer method gets rid of the function return and map growth overheads but has the penalty of allocating each Words object on the heap. Normally, the return by pointer approach is chosen as the least inefficient.

With the introduction of rvalue-references this situation changes dramatically. Provided the types we use are rvalue-optimized by including a constructor and an assignment operator for rvalue-references (std::vector and std::map are), the return by value approach becomes the most efficient. The deep copies during the function return are eliminated and when the map grows, the rvalue constructor is used to “move” the existing objects to the new storage.

Another advantage of the return by value approach is that it allows the user to choose where to place the object, on the stack or on the heap. The stack rvalue can be cheaply moved to the heap using the rvalue constructor:

Words load (const Word& w)
{
  Words r;
  // Load synonyms into r.
  return r;
}
 
shared_ptr<Words> syn (load ("value"));

One, however, needs to understand how rvalue-references work to be able to write efficient code using return by value and rvalue-optimized types. Otherwise it is fairly easy to shoot oneself in the foot, as shown in the following example:

Words load (const Word& w)
{
  Words r;
  // Load synonyms into r.
  return r;
}
 
Words words = ...
SynonymMap map;
 
for (Words::const_iterator i = words.begin ();
     i != words.end ();
     ++i)
{
  Words syn (load (*i));
  map[*i] = syn;
}

Here we introduced a variable that temporarily holds the result of the load() function. With it we also introduced an unnecessary copy since now the non-rvalue assignment operator has to be used. It does not mean, however, that we cannot do something with the list of synonyms before we insert it into the map. We just need to use std::move() to “move” the object instead of copying it.

for (Words::const_iterator i = words.begin ();
     i != words.end ();
     ++i)
{
  Words syn (load (*i));
 
  if (syn.size () > 0)
    map[*i] = std::move (syn);
}

I suspect that as with many other parts of C++, people who make the effort to understand rvalue-references will write even more elegant and efficient code while those who don’t will continue complaining that C++ is too difficult.

While it may seem that the only two places where rvalue-references will be used are constructors and assignment operators, on a more conceptual level, rvalue-references provide a mechanism to distinguish between objects whose state needs to be copied and objects whose state can be reused (with rvalue objects automatically treated as the latter). As such, rvalue-references can be used in other places where such a distinction can be helpful. For example, std::vector defines an overloaded version of the push_back() function that takes an rvalue-reference:

template <typename T, ...>
class vector
{
public:
  void push_back (const T&);  // copy
  void push_back (T&&);       // reuse
  ...
};

To summarize, the introduction of rvalue-references in C++ solves the problem of efficiently returning complex objects by value. They will allow writing simpler, faster, and more natural code. I also believe that, at least in well-designed programs, the use of heap-allocated objects will decrease which should make these programs even more efficient.

This entry was posted on Monday, December 1st, 2008 at 4:07 am and is filed under C++. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.