KholdCode

23 Nov 2013

Moves demystified

In this article, I will try to explain move semantics in C++11 using a more pragmatic approach, by answering specific questions developers may ask. We’ll start with why moves are needed in the first place, then see how to use them, and eventually move onto common misconceptions and pitfalls.

Index

The article is quite large, so I included a short summary with links for each of the sections below:

Why are moves needed?

Let’s consider a simple fixed-size vector of numbers:

/**
 * Runtime-sized vector, but
 * Size fixed at construction.
 */
class Vector {
    double* storage_;
    size_t  size_;

public:
    Vector(size_t numElements)
        : storage_(new double[numElements])
        , size_(numElements)
    { }

    ~Vector() { delete[] storage_; }

    // element access
    double& operator[] (size_t i)       { return storage_[i]; }
    double  operator[] (size_t i) const { return storage_[i]; }

    size_t size() const { return size_; }

    // standard iterator fare (begin(), end(), etc...)
    // ...
};

Even though these vectors have a fixed size throughout their lifetime, they may be quite large, so copying them would be prohibitively expensive. The whole underlying array must be replicated.

Visualizing a Copy Constructor. Both the members and anything they refer to must be copied.

We’d like to perform value operations without unnecessary copies:

Vector c = a + b;

Of course that leaves us with the problem of defining operator +. What do we return? Clearly we want to return a value if we want operations to compose, but that could mean copying a massive vector!

??? operator + (Vector const& a, Vector const& b);

Our instincts say:

  • Returning by value is bad! We make a copy!

  • If we allocate on the heap and return a pointer, who deletes it?

    • It doesn’t compose! Can’t chain several additions since we’re not working with values.

We need some way to move a value out of a scope directly, without copying

Copying the value out of a function and then deleting the local seems absurd. Let’s see what already exists in C++03 to tackle this problem.

Can I “move” in C++03?

Ideally, given the problem of implementing operator + for two vectors, we’d want to write this:

Vector operator + (Vector const& a, Vector const& b)
{
    // create result of same size
    assert(a.size() == b.size());
    Vector result(a.size());

    // compute addition
    std::transform(
        a.begin(), a.end(), // input 1
        b.begin(),          // input 2
        result.begin(),     // result
        std::plus<double>() // binary operation
    );

    return result; // ... but can we avoid the copy?
}

And that’s exactly what you should write, because the compiler will get rid of the copy for you! This happens because of copy elision (specified in the C++ standard in clause 12.8.31), and more specifically because of NRVO (Named Return Value Optimization). Returning a local variable by value is detected by the compiler, and the needless copy is elided. This optimization was first developed in 1991, so you can rest assured your compiler supports it.

Even in C++03, returning by value usually results in no copies because of copy elision.

Now, I say usually, because there are corner cases where this optimization will not trigger. See the Wikipedia Article for an overview, and consult your favourite compiler manual for more details.

In the next section we’ll consider another problem where move semantics are needed.

Why do I really need moves and C++11?

We saw that our previous problem of transferring values out of a terminating scope is still solvable in C++03, through clever compiler optimization. We need to cover the converse situation of transferring values into a scope, in situations like:

  • Passing subcomponents to a constructor of an aggregate
  • Handing off a value to another task or thread.
  • Transferring ownership of a unique resource (e.g. a file handle, thread, std::unique_ptr)

In all of the cases above, there is a need to transfer without copying. Yet again, pointers are not the answer here. Using pointers for this transfer requires managing the storage (either the heap, or some shared memory), which should be unnecessary, and might even defeat the purpose entirely.

Simply put, transferring values in and out of a scope allows efficient passing of values.

Moves allow value semantics, without extraneous copies.

To keep a concrete problem in mind, let’s look at initializing an aggregate object from two Vector objects. We’ll define Ray concretely soon.

// Example of extraneous copies
// (A more concrete definition follows in a subsequent example)
Ray computeRay()
{
    Vector origin;
    Vector direction;

    // ...
    // compute vectors
    // ...

    // want to avoid copying
    // the Vectors !
    return Ray(
        origin,   // COPY!
        direction // COPY!
    );
}

Now that we have defined the problem, how do we solve it?

What are rvalues and how do they relate to move semantics?

The key feature that we need, is to tell apart regular values, and “temporary” ones. Once we know that, we can decide whether to copy or move. By looking at a typical assignment we can see where the terms lvalue and rvalue come from:

Vector a, b, c;
// c is an lvalue. It is on the "left"
// |
   c = a + b;
//     ^^^^^
// the result of the "a + b" expression is an rvalue
// It is on the "right"
  • Lvalues are values that you can freely refer to in their scope because they are bound to a name- such as variables. As such, lvalues can be assigned to, and used several times in a single scope.
  • Rvalues, cannot be directly referred to because they are temporaries and are not bound to a name- such as values returned by a function, or the direct result of an inline construction:
// some kind of factory function
Vector createVector(std::string param);

Vector myVec = createVector("hello world");
//            ^             ^^^^^^^^^^^^^
//            |         temporary std::string
//            |
//  temporary Vector
//
// There are two rvalues in the expression above.

Given that by definition we cannot refer directly to rvalues, we need rvalue references (&&) to be able to bind to them. This allows overloading functions/methods/constructors for rvalue arguments which we know will expire.

Rvalues are values that are either temporary or on the verge of expiry. They cannot be used directly, except through rvalue references &&. Rvalue references make it possible to specify a function overload for an expiring value, such as a move constructor.

How is a move performed?

To do a move, we need a cheap way of transferring data from an expiring value. By providing an overloaded constructor that takes an rvalue reference (&&), we can do that. Here is a Move Constructor for our Vector that is cheaper than a copy:

// Move constructor.
// "other" will soon expire!
Vector::Vector(Vector&& other)
    // shallow copy
    : storage_(other.storage_)
    , size_(other.size_)
{
    // nullify source
    other.storage_ = nullptr;
    other.size_ = 0;
}

Visualizing a Move Constructor in two steps. The resources are ‘stolen’ from the source.

A Move Constructor involves:

  • A shallow copy

    • We take pointers/resources directly from the other object

  • Nullify the source

    • Having stolen the pointers/resources, we nullify these fields in the source so the destructor doesn’t release them.

How is std::move used? Does it perform the move?

This article is about moves, but we have yet to use std::move. What gives?

Unfortunately, std::move is in some sense a misnomer. Think of std::move as a new type of cast that casts any expression to an rvalue. This cast makes the compiler select the rvalue reference overload (for example a move constructor), where the actual move is performed.

To be more concrete, and work towards a problem established earlier, let’s define the Ray class that has overloaded constructors:

class Ray
{
    Vector origin_;
    Vector direction_;

public:
    // Construct by copying subcomponents
    Ray(Vector const& origin, Vector const& direction);
    
    // Construct by moving subcomponents
    Ray(Vector&& origin, Vector&& direction);

    // etc...
};

Using std::move we can tell the compiler that the value is no longer needed in this scope. Solving the problem is now within reach. Given local lvalues that we need to move, we can cast them to rvalues using std::move:

// Example of moving
Ray computeRay()
{
    Vector origin;
    Vector direction;

    // ...
    // compute vectors
    // ...

    // Move vectors into Ray
    // triggering the right constructor
    return Ray(
        std::move(origin),
        std::move(direction)
    );
}

It bears reiterating:

std::move does not perform the move. It is nothing more than a cast from an lvalue to an rvalue, to allow an actual move to happen (e.g. by causing an appropriate move constructor to be called).

Why do I need to use std::move on rvalue references?

We tackled moving lvalues down a layer, using std::move. What happens when we already have an rvalue reference that we need to move down another layer?

Let’s look at a concrete example using our Ray class, and its constructor that takes two Vectors by rvalue reference. When composing a larger aggregate out of smaller movable objects, we can delegate the process of moving to the sub-components using std::move:

// Construct by moving subcomponents.
Ray::Ray(Vector&& origin, Vector&& direction)
    // move construct inner objects
    : origin_(std::move(origin))
    , direction_(std::move(direction))
{ }

To move down an rvalue through successive layers, std::move has to be applied each time, even to rvalue references.

Why is that? A mind-bending realization is that because rvalue references are bound to a name, they are themselves lvalues. We need to tell the compiler that this value is no longer needed in this scope. Stop here, and take a breath.

Let’s look at that code again, now with more annotations:

// Construct by moving subcomponents.
// "origin" and "direction" refer to rvalues,
// but are themselves lvalues in this scope.
Ray::Ray(Vector&& origin, Vector&& direction)
    // move construct inner objects,
    // by casting inputs to rvalues
    : origin_(std::move(origin))
    , direction_(std::move(direction))
{ }

There are several important things to notice here:

  • The constructor overload is chosen when both inputs are rvalues.

  • Once the rvalue references are bound, we can refer to them in the scope.

    • This means that these rvalue references are lvalues!
  • We have to use std::move to cast these references back to rvalues to pass them to the move constructors of the Vector objects.

Phew!

rvalue references bound to a name, can be referred to in their scope and are therefore lvalues.

If this last quote makes your head spin, just remember that to move a value down through successive layers, std::move has to be applied each time.

Is there a difference between an rvalue and an rvalue reference?

Yes! The two notions are very different. This misconception comes up time and time again, but not in the form of this direct question. I noticed that while learning the new concept of rvalues, the ideas of rvalues and rvalue references can become conflated together. Many refer to one or the other interchangeably. This is a stage I experienced, and was surprised that this is rarely disambiguated directly.

Rvalues and rvalue references are very different notions. Rvalues are the actual expiring values that cannot be used directly. To access rvalues, we use rvalue references.

The misconception often manifests itself in code like this (which doesn’t work):

// How NOT to do it
std::string&& func()
    std::string hello("Hello World!");
    return std::move( hello );
}

To give some perspective, here’s the same function but with lvalues:

//  Also, how not to do it.
std::string& func()
    std::string hello("Hello World!");
    return hello;
}

We all know that returning a reference to a local value is bad, since it goes out of scope- and that’s exactly what happens in both cases. Both references returned would be referring to already-destroyed objects.

A value returned from a function is already an rvalue. Returning an rvalue reference to a local is as bad as returning an lvalue reference to it.

Just so there is no confusion, here’s the simplest and correct way to do it:

//  Optimal thanks to Copy Elision
std::string func()
    return "Hello World";
}

Any temporaries and copies disappear due to copy elision.

Are moves free? Are moves faster than copies?

Are moves free? No. As we have seen:

  • Moves are shallow copies
  • That also nullify the source of the copy

Both operations have to be performed to move an object. It will never be as fast as not doing anything.

Are moves faster than copies? This depends. Moves are much faster for structures with indirection, (like vectors), since copying all of the data is not required (just pointers). However, moves are copies for structures without pointers or indirection, since we still need to transfer all the member variables. If there is no “depth” to the structure, then there are no performance benefits to moves.

For simple structures with no indirection, moves are copies.

Clever solutions in C++03

There are other clever ways of getting rid of unnecessary copies and operations from C++03 code. Both go beyond the scope of this article, but you can read up on these techniques at the links below:

  • Expression Templates

    • Expression templates allow encoding a tree of expressions (e.g. mathematical expressions) and performing simplifications and optimizations on them, all at compile time.
    • The implementations are very complex, but the user API ends up being extremely intuitive, while performing extremely efficiently.
    • A great library that uses this concept heavily is Eigen.

  • Faking Rvalues

    • Boost Move emulates rvalues and move semantics through very clever C++ tricks, allowing the creation of movable objects in C++03.

Conclusion and other resources

I hope this has helped some of you understand the basics of move semantics. Please comment below with corrections/suggestions, and if I have missed any other common questions about moves in C++11/14.

To dive deeper into move semantics and various pitfalls, here are a few more resources to look at:

This article has been featured on isocpp.org and reddit.

  • c++11
  • intermediate