Thursday, December 24, 2015

Redundant std::move

C++11! R-value references! std::move! As people start switching to using C++11, they naturally start using std::move and rvalue references to increase the performance of the programs. Nonetheless, one of the common misuses of std::move is to apply it to a return value when it isn’t required:

Foo GetFoo() {
 Foo foo;
 …
 return std::move(foo); // std::move is not needed here.
}

The reason std::move is not required is that the C++ standard provides special rules for this situation. Specifically,

§12.8/32
When the criteria for elision of a copy operation are met or would be met save for the fact that the source object is a function parameter, and the object to be copied is designated by an lvalue, overload resolution to select the constructor for the copy is first performed as if the object were designated by an rvalue. If overload resolution fails, or if the type of the first parameter of the selected constructor is not an rvalue reference to the object’s type (possibly cv-qualified), overload resolution is performed again, considering the object as an lvalue. [ Note: This two-stage overload resolution must be performed regardless of whether copy elision will occur. It determines the constructor to be called if elision is not performed, and the selected constructor must be accessible even if the call is elided. — end note ]

This is a lot of standard-ese, but let’s break it down in order to understand what this rule means.

When does the rule apply?

When the criteria for elision of a copy operation are met ...

First, it says that this rule applies if we run into a situation when copy elision (or return value optimization) would typically take place. This situation is covered by §12.8/31 of the standard, which is also a lot of standard-ese (this is a subject for another post). In laymen’s terms, it says that, among other things, copy elision can take place if we are returning a local variable that has the same type as the function return type:

Foo GetFoo() { // The return type of GetFoo is “Foo”
 Foo foo;
 …
 return foo;  // |foo|’s type is “Foo”
}

In the above situation, we are in a situation when copy elision can be applied, since the return type of the function matches the type of the variable we’re returning.

… or would be met save for the fact that the source object is a function parameter …

The next part allows this rule to be applied even if the variable we’re returning is a function parameter. That is, copy elision cannot happen if the variable is a function parameter, but this rule can be applied nevertheless:

Foo ModifyFoo(Foo foo) { // copy elision cannot happen here.
 …
 return foo;
}

The above example looks very similar to the GetFoo example, except that the variable is a function parameter. This means that although copy elision cannot occur, the rule discussed here (§12.8/32) does apply.

… and the object to be copied is designated by an lvalue …

The last part describing when this rule can be applied says that the variable we’re operating on must be an lvalue. We’ve explored lvalues and rvalues in a previous post, but it basically says that this rule is not applied to rvalues. The reason for this is that if the object being returned is an rvalue, a move constructor would already be selected without the need for special rules.

What does the compiler have to do?

… overload resolution to select the constructor for the copy is first performed as if the object were designated by an rvalue …

This says that although the variable we’re returning is, in fact, an lvalue (this is true, since this rule only applies when we’re returning lvalues), we have to select a constructor for copying this variable as if it was an rvalue. This is the key piece of the rule: if we’re in a return statement, we don’t need to move things since it will already be treated as an rvalue.

Foo GetFoo() {
 Foo foo;
 …
 return foo; // Select a ctor for this copy as if
}             // foo was an rvalue.

However, we’re not done yet.

If overload resolution fails, or if the type of the first parameter of the selected constructor is not an rvalue reference to the object’s type …

The rule continues. In fact, it is now putting restrictions on what must happen if Foo does not have a move constructor. That is, if we do perform this resolution as if our variable was an rvalue, but for whatever reason we don’t end up using a move constructor for our variable, then we apply the following:

… overload resolution is performed again, considering the object as an lvalue …

That is, we have to go back and select a copy constructor, but this time considering our variable for what it is: an lvalue. Consider the following:

struct Foo {
Foo();
Foo(const Foo&);
};

Foo GetFoo() {
 Foo foo;
 …
 return foo;
}

At the return statement, |foo| is first treated as an rvalue. However, the overload resolution selects the constructor taking a reference to const Foo. This is not a move constructor. Thus, the compiler goes back and this time treats |foo| as an lvalue. It again, selects the reference to const Foo.

This seems like a minor distinction, but it can make a difference in certain situations. Consider what happens if Foo also has a constructor taking a reference to non-const Foo.

struct Foo {
Foo();
Foo(const Foo&);
Foo(Foo&);
};

Foo GetFoo() {
 Foo foo;
 …
 return foo;
}

Now, this is completely legal, but let’s see what happens at the return statement now. First, we treat |foo| as an rvalue as before. We select a constructor taking a reference to const Foo, since references to const can bind to rvalues. However, since this is not a move constructor, we start again and treat |foo| as an lvalue. This time, however, we select a constructor that takes a reference to non-const Foo, since it’s a better match for this copy (|foo| is a non-const lvalue).

The note

Note: This two-stage overload resolution must be performed regardless of whether copy elision will occur. It determines the constructor to be called if elision is not performed, and the selected constructor must be accessible even if the call is elided.

This part notes that although the rule is referencing copy elision, it is just relying on it since the rules for when it can happen are similar. However, this rule to treat the variable as an rvalue applies whether or not copy elision would actually occur.

As an aside …

A version of clang that I use on my machine provides some helpful warning flags to identify situations where moves are used but not required. The first one is pessimizing move:

$ cat test.cpp
#include

struct Foo {};

Foo GetFoo() {
 Foo foo;
 return std::move(foo);
}

$ clang -std=c++11 -c -Wpessimizing-move test.cpp
test.cpp:7:10: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
 return std::move(foo);
        ^
test.cpp:7:10: note: remove std::move call here
 return std::move(foo);
        ^~~~~~~~~~   ~
1 warning generated.

In summary, this says that the compiler could have performed a copy elision here, but since we wrapped the return call in an std::move, this can no longer happen. The use of std::move here is preventing a good optimization. This makes this a pessimizing move.

The second distinct warning level is redundant move:

$ cat test.cpp
#include

struct Foo {};

Foo ModifyFoo(Foo foo) {
 return std::move(foo);
}

$ clang -std=c++11 -c -Wredundant-move test.cpp
test.cpp:6:10: warning: redundant move in return statement [-Wredundant-move]
 return std::move(foo);
        ^
test.cpp:6:10: note: remove std::move call here
 return std::move(foo);
        ^~~~~~~~~~   ~
1 warning generated.

Note that this is a separate warning, because copy elision cannot happen in this case. That is, this use of std::move is not preventing optimizations. However, it says that it isn’t required because the object would be treated as an rvalue anyway.

But, we also learned before that the variable would only be treated as an rvalue if the class has a move constructor. So, that means that in theory we can force different behavior to happen with or without the move. Consider the following:

$ cat test.cpp
#include
#include

struct Foo {
 Foo() { fprintf(stderr, "default ctor\n"); }
 Foo(const Foo&) { fprintf(stderr, "const copy ctor\n"); }
 Foo(Foo&) { fprintf(stderr, "non-const copy ctor\n"); }
};

Foo ModifyFoo(Foo foo) {
 return std::move(foo); // This line issues the warning
}

int main() {
 Foo foo = ModifyFoo(Foo());
}

$ clang -std=c++11 -Wredundant-move test.cpp
test.cpp:11:10: warning: redundant move in return statement [-Wredundant-move]
 return std::move(foo);
        ^
test.cpp:11:10: note: remove std::move call here
 return std::move(foo);
        ^~~~~~~~~~   ~
1 warning generated.

$ ./a.out
default ctor
const copy ctor

Although we get a warning that we have a redundant std::move, the move is still applied. As a result, the value in the return statement is an rvalue. This means that it can bind to a const copy constructor, which is what happens. Yet, removing the “redundant move” and compiling without warnings yields the following:

$ ./a.out
default ctor
non-const copy ctor

That is, the compiler first attempts to treat |foo| as an rvalue. However, since it doesn’t have a move constructor, it goes back and finds a constructor as if |foo| was a (non-const) lvalue. It binds to the non-const copy ctor since it’s a better match.

I guess it’s open to interpretation what “redundant” means in this case, but it is possible to get a different behavior with and without a std::move in a return statement. Note that this shouldn’t be a common situation at all, since it’s rare to encounter both a const- and a non-const- copy constructors.

Tuesday, December 22, 2015

r-value references and move semantics

This post discusses different types of expressions and references that can exist in C++11. In particular, it explains rvalue references that are new in C++11. It then touches on uses of std::move and std::forward, outlining appropriate and inappropriate usages.


Expressions: lvalues vs rvalues.


In C++, an expression is a sequence of operators and operands. An expression has a value, which can be classified into one of several value categories. For simplicity, we’ll talk about the most relevant of the value categories: lvalues and rvalues.


An lvalue expression is named so because most of the time it can appear on the left hand side of an assignment operation. This provides a good intuition when trying to decide whether an expression at hand is an lvalue expression. More formally, an lvalue expression is an expression that refers to a memory address. Specifically, if you can take an address of an expression, then it is an lvalue expression. You can think of lvalues as expressions that have a name. Most of the time they are just regular variables. Some examples of lvalue expressions are the following:


int n;
n = 3;          // n is an lvalue expression


int a[2];
a[0] = n;       // a[0] is an lvalue expression


int* p = &a[0];
*p = 5;         // *p is an lvalue expression
*++p = 7;       // *++p is an lvalue expression


An rvalue expression, on the other hand, is simply not an lvalue. These are expressions that can only appear on the right-hand side of an assignment operator. They are not assignable and do not refer to a specific memory location. Some examples of rvalue expressions are the following:


int n = 3;       // 3 is an rvalue expression
n = Function();  // Function() is an rvalue expression


int a, b;
n = a + b;       // a + b is an rvalue expression.


c[0] = n;        // n is _not_ an rvalue expression.
                // It’s still an lvalue, even though it’s on
                // the right hand side of the assignment.


The last example is an important concept. Just because an expression is on the right hand side of an assignment, does not make it an rvalue. That is, lvalues can appear on either left- or right- hand sides of an assignment operation. However, rvalues can only appear on the right hand side.


These are just two types of expressions that exist. There are more of them (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3055.pdf), but for the purpose of this document the important distinction we need to make is between lvalue and rvalue expressions.


Variable types: lvalue references vs rvalue references


When referring to lvalues and rvalues, we talk about expressions. Now let’s talk about variables. Variables have types. Some of these types may refer to expressions. These variables are, of course, references. There are a couple of familiar types of references:


  • lvalue references to non-const. These are references that can refer only to lvalue expressions. They, in fact, refer to objects, which is exactly what an lvalue expression represents. For example,


int a = 5;        // a has a type int
int& ref = a;     // ref has a type lvalue reference to int.
                 // It refers to an lvalue, |a|.


int& bad_ref = 5; // This line will not compile. Since 5 is an
// rvalue expression, an lvalue reference to
// non-const cannot bind to it.


  • lvalue references to const. Similar to lvalue references to non const, lvalue references to const can also refer to lvalues. However, additionally they can refer to rvalues as well (since they aren’t modifiable, this is OK). In fact, lvalue references to const extend the lifetime of temporaries until they, themselves, are destroyed. For example,


int a = 5;               // a has a type int
const int& ref = a;      // ref has a type lvalue reference to
                        // const int

struct Foo {};
const Foo& good_ref = Foo(); // good_ref has a type lvalue
// reference to const int.
// This is OK, since it’s a
// const ref. The lifetime of
// the temporary object Foo()
// is extended until good_ref
// goes out of scope.


As an aside, it is an important feature of C++ that lvalue references to const extend the lifetime of temporaries to which they are bound. We use these types of tricks all the time. Consider the following example:


std::string GenerateString() {
 …
}


const std::string& s = GenerateString();
// Work with s.


The call to GenerateString produces a temporary std::string. It would normally be destroyed at the end of the expression, unless it is copied. However, since it’s bound to an lvalue reference to const, the lifetime of this temporary is extended, which allows us to work with it after the GenerateString line is executed.


C++11 and even more reference types


Now, without C++11,
  • we have types that can refer to lvalue expressions only (lvalue references to non-const)
  • we have types that can refer to either lvalue or rvalue expressions (lvalue references to const)


C++11 introduces a natural extension to this: a type that can refer to rvalue expressions only, an rvalue reference. This is written as a double ampersand after a type:


MyType&& ref = …;  // ref has a type rvalue reference
// (to non-const).


This type of reference can only refer to rvalue expressions and will simply refuse to bind to lvalue expressions. Consider a previous example, with lvalue references changed to rvalue references:


int a = 5;              // a has a type int
int&& ref = a;          // This won’t compile! rvalue
// references cannot bind to lvalues
// (and a, in this case, is an lvalue).


int&& another_ref = 5;  // This is now fine! another_ref
// refers to an rvalue expression 5.
++another_ref;          // It’s also a reference to non-const,
// so it’s modifiable! It now refers
// to “6”


In the previous example, lvalue reference to non-const could bind to the variable |a|, but could not bind to the expression 5. Now the positions are reversed. Since rvalue references can only refer to rvalues, ref refuses to bind to the variable |a| (it’s an lvalue), but binds to 5 without issues. Rvalue references, like lvalue references to const, extend the lifetimes of the expressions to which they refer. Additionally, since this is a reference to non-const, you can modify the value of the expression that it is referring to.


As a side note, you can also have a rvalue reference to const, but it loses much of its power. In fact, I would say that if you must have an rvalue reference to const, you might as well use an lvalue reference to const. It saves you one character stroke, and it is understood by far more programmers.


So what?


It turns out the fact that rvalue references refer to rvalues and the fact that they are modifiable allows us to write pretty efficient code in some situations.


Consider the following code with a new rvalue reference constructor (also known as a move constructor):


struct MyClass {
MyClass(MyClass&& other) {
  …
}
};


There are two pieces of information we have within this constructor. First, we know that the value passed to it was an rvalue. For all intents and purposes, we can pretend that the value was a temporary (or at least the calling code wants us to believe it was a temporary). Second, we know that we can modify the argument. This allows this constructor to be more efficient in some situations. Consider the following,


struct MyClass {
MyClass(MyClass&& other) {
  large_vector_.swap(other.large_vector_);
}


private:
 std::vector<int> large_vector_;
};


With a typical copy constructor, we would have to copy a potentially large vector. However, with a move constructor, no copies are required for this vector. We know |other| is going away, and we can change it any way we want. So, we can afford to simply swap the vector with our own (empty) vector. This operation is typically much cheaper than a full copy. That’s the power of move constructors: efficient moving of containers and pointers.


However, before writing a move constructor for every type that you have ever written, also consider the following example:


struct MyClass {
MyClass(MyClass&& other) {
  …
}


private:
 int large_array_[500];
};


It’s a similar class, but it has an array instead of a vector. What can a move constructor do here that is more efficient than a copy constructor? Not much. In fact, the move constructor in this case would have to do exactly the same thing as a copy constructor. The reason is that the memory for the large array can’t be “moved”. There are no pointers to copy, no vector to swap. We have to do an element by element copy (or more likely a memcpy). However, this is exactly what a copy constructor would do as well. Considering this, a move constructor is actually unnecessary in this case; a copy constructor will work in more situations and do the same operations.


Coercing the type system (std::move)


So far, everything we talked about only involved the core C++11 language. The basic summary is that whenever you have an rvalue, it can be bound to an rvalue reference. This includes variables and functions parameters alike, including constructor and assignment operator parameters. However, we can also get into situations where we would really like to get an rvalue, but we simply don’t have one:


void function() {
 MyClass my_class;
 // Construct and initialize a non-trivial type.
 // …
 set_new_class(my_class);
}


After we make a call to set_new_class, the enclosing block also ends, which means |my_class| is not going to be used. In fact, we would really like to say that it might as well be a temporary. However, as the code stands right now, during the call to set_new_class, |my_class| is an lvalue. This means it cannot bind to rvalue references. Hence, an overload would be selected that prefers lvalues (most likely an lvalue reference to const). We can cheat and simply cast the type to an rvalue reference:


 set_new_class(static_cast<MyClass&&>(my_class));


This works. This really says that we want the type system to pretend that what we’re passing it is an rvalue so it can bind to rvalue references. Enter the C++11 standard library. It’s not much of a help, but it does provide a standard function std::move which would do this cast for you:


 set_new_class(std::move(my_class));


Note that the last two lines of examples will do exactly the same thing. They simply inform the compiler that at the line of set_new_class, it can treat |my_class| as if it was an rvalue. Obviously, the code can still access |my_class| after the call, but (at least with most standard types), applying a move and passing it somewhere usually leaves it in an unspecified state. That is to say, you can either destroy the object or assign a new value to it; using an object in an unspecified state can lead to undefined behavior.


Note that it’s worth reiterating, std::move will not actually move anything or do anything tricks with memory. It will simply cast its parameter to be an rvalue reference, unconditionally. You can also use it with rvalues, of course


 set_new_class(std::move(MyClass()));  // silly, but works.


The reason this is silly, is because MyClass() is already an rvalue. In the best case, adding a move only adds noise. In the worst case, this can inhibit some compiler optimizations such as return value optimizations, which can result in slower code.


As an important aside, note that we have to still distinguish the value category of an expression from the variable type. That is, a variable can have a type of rvalue reference, but the variable itself remains an lvalue:


void function(MyClass&& my_class) {
 set_new_class(
std::move(my_class)); // std::move is required to make
}                         // |my_class| an rvalue. That is
                         // because |my_class| as an
                         // expression is an lvalue.


Here, std::move is not adding noise, it is taking |my_class|, an lvalue expression, and converting it to an rvalue expression. This is needed, because regardless of the variable’s type, it refers to an object, thus making it an lvalue.


Special case for return statements


There is one special case where normally you would be inclined to write std::move, but it’s not required: a return statement returning a local variable (or function parameter) of the same type as the function signature’s return type:


Foo function() {
 Foo foo;
 …
 return foo;
}


In this case, foo is still an lvalue at the return statement. However, the C++ standard provides a special exception in this case. It says that if Foo has a move constructor, then |foo| has to be treated as an rvalue in this case. However, if Foo doesn’t have a move constructor then it will be treated as an lvalue.


In short, you typically do not need to say std::move(foo) when returning a local foo.


Templates (std::forward)


Templates present a small complexity. Specifically, when you have a templated typename T, then reading T&& does not necessarily imply an rvalue reference:


template <typename T>
void function(T&& value);  // value might either be an lvalue
                          // reference or an rvalue
// reference!


The reason for this is simple: when passing an rvalue into this function, say 5, the type system determines that T could be int, which makes the function accept an int&& (an rvalue reference):


template <typename T>
void function(T&& value);


function(5);  // T = int, |value| type is int&&.


However, when passed an lvalue, the type system tries its best to bind the passed argument to value. It succeeds due to reference collapsing. Reference collapsing is a rule that protects us against references to references. In a nutshell, it says that an rvalue reference to an lvalue reference (ie Type& &&) collapses to be an lvalue reference (Type&). So, when presented with an lvalue int, the type system figures out that it could make T, the deduced template type, be an int&, thus making value have the type int& && which collapses to int&.


template <typename T>
void function(T&& value);


int five = 5;
function(five);  // T = int&, |value| type is int&.


This is important, because when encountering T&& in a template, it is crucial to understand that this could mean an rvalue reference or it could mean an lvalue reference. Consider the following example:


template <typename T>
void function(T&& value) {
  …
  set_new_value(std::move(value)); // Wrong.
}


This example is similar to above, except that it contains a template. Now, using move here is wrong, because the function could have been invoked with an lvalue and the caller expects the object to still be the same when the function returns:


Type type;
function(type);
// Do work with |type|, since it shouldn’t have been modified.


It would be very unexpected for function to move from the type when it is still needed. For our second attempt, we can rewrite function as follows:


template <typename T>
void function(T&& value) {
  …
  set_new_value(value); // OK, but can be inefficient.
// (also fails with move only types)
}


This variant is ok, since it works just fine with both lvalues and rvalues. However, when an rvalue is passed in and |value| has the type rvalue reference, it can be inefficient to pass |value| directly, since |value| itself is an lvalue expression and can cause a copy.


What is needed here is a conditional cast to an rvalue. The condition is based on whether the type of value is an rvalue reference or not. This is what the C++11 standard library std::forward does:


template <typename T>
void function(T&& value) {
  …
  set_new_value(std::forward<T>(value)); // Good.
}


What this will do is make |value| an rvalue if its type is an rvalue reference. Otherwise, it will leave |value| as an lvalue. This looks magical, but it works simply by inspecting the deduced type T. Note that for forward, you have to specify which specialization you would like, by explicitly saying std::forward<T>. Earlier we learned that if T is a non-reference type (int for example), then value is an rvalue reference. However, if T is an lvalue reference type (int& for example), then value is an lvalue reference:


Example code
T
|value| type
Explanation
function(5)
int
int&&
rvalue reference
function(five);
int&
int&
lvalue reference


This is exactly the same mechanism that allows forward to figure out whether to cast value to be an rvalue. In other words, when we see std::forward<T>, T is the part that causes us to do the right thing:


std::forward<int>(five);   // equivalent to “std::move(five)”
std::forward<int&>(five);  // equivalent to “five”


This is exactly what we want for a template. Given an unknown reference type (lvalue or rvalue reference), move it only if it was an rvalue reference. This process is known as perfect forwarding. In other words, forward only really applies to templated code, and it will act as move when the non-templated version would have used a move.


Given this, it is almost always wrong to see a call to std::forward in non-templated code. If the code isn’t templated, then it should be clear whether we want an lvalue or an rvalue. That is, we either leave the expression as is, or we apply std::move to it.


Pitfalls


It is clear that rvalue references are a powerful tool for writing efficient C++. However, there are also common pitfalls that one should watch out for:


  • Returning references to locals
  • Rvalue references to const
  • Pessimizing moves (applying std::move to expressions that are already rvalues)