Friday, March 09, 2012

Rvalue references in constructor: when less is more

I've seen a recurring mistake made by well-versed C++03 programmers when they set out to use rvalue references for the first time. In fact, as it turns out, better you are at C++03, easier it is to fall in the trap of rvalue reference anti-pattern I'm gonna talk about.

Consider the following C++03 class:

class Book {
public:
  Book(const std::string & title,
       const std::vector<std::string> & authors,
       const std::string & pub,
       size_t pub_day
       const std::string & pub_month,
       size_t pub_year)
    : _title(title),
      _authors(authors),
      _publisher(pub),
      _pub_day(pub_day),
      _pub_month(pub_month),
      _pub_year(pub_year)
     {}

     // ....
     // ....

private:
  std::string _title;
  std::vector<std::string> _authors;
  std::string _publisher;
  size_t      _pub_day;
  std::string _pub_month;
  size_t      _pub_year;
};


The Book class above is as dull as it can be. Now lets C++11'fy it! C++11 gives us shiny new rvalue references and std::move. So lets add them.

class Book {
public:
  Book(const std::string & title,
       const std::vector<std::string> & authors,
       size_t pub_day
       const std::string & pub_month,
       size_t pub_year)
    : _title    (title),
      _author   (author),
      _pub_day  (pub_day),
      _pub_month(pub_month),
      _pub_year (pub_year)
     {}

  Book(std::string && title,
       std::vector<std::string> && authors,
       size_t      && pub_day
       std::string && pub_month,
       size_t      && pub_year)
    : _title    (std::move(title)),
      _authors  (std::move(authors)),
      _pub_day  (pub_day),
      _pub_month(std::move(pub_month)),
      _pub_year (pub_year)
     {}

     // ....
     // ....

private:
  std::string _title;
  std::vector<std::string> _authors;
  size_t      _pub_day;
  std::string _pub_month;
  size_t      _pub_year;
};


Is our constructor optimally move-enabled? It's far from it! More often that not, programmers' legit code will end up calling the old constructor instead of the the new one, which probably means lost opportunities for optimization. It could be hard to see what's wrong in the new class to an untrained eye. We've test it to see what's really wrong with it.

std::string & toUpper(std::string & s)
{
  std::transform(s.begin(), s.end(), s.begin(), toupper);
  return s;
}
const std::string & January()
{
  static std::string jan("January");
  return jan;
}
int main(void)
{
  std::vector<std::string> authors { "A", "B", "C" };
  Book b1("Book1", authors, 1, "Jan", 2012);   // old c-tor

  size_t year = 2012
  Book b2("Book2", { "A", "B", "C" }, 1, "Jan", year); // old c-tor

  std::string month = "Mar";
  Book b3("Book3", { "Author" }, 1, toUpper(month), 2012); // old c-tor

  Book b4("Book4", { "Author" }, 1, January(), 2012); // old c-tor

  std::string book = "Book";
  Book b5(std::move(book), std::move(authors), 1, std::move(month), year); // old-ctor

  Book b6("Book", { "Author" }, 1, "Jan", 2012); // new c-tor!
}


It may come as a surprise that in all but one case above, the old constructor is called. Only in the last case, the new-ctor is called, which makes the minimum number of copies. So what's the gotcha?

As it turns out, the Book constructors are stopping the compiler from doing a better job. The first constructor takes all the parameters as const reference and the second one takes all the parameters as rvalue reference. Unless and until all the the parameters passed to the constructor are temporary objects (rvalues) or literals, the second constructor does not kick in. This implies lost optimization opportunities for parameters that are temporary (so can be moved) but won't be moved because some other parameter botched the soup. These two constructors give you very limited options: all-or-nothing.

In case of b1, authors is an lvalue and it does not bind to an rvalue ref.
In case of b2, year is an lvalue and does not bind to an rvalue ref.
In case of b3, toUpper returns a string reference; Does no good.
In case of b4, January returns a const string reference; same story!
In case of b5, year is an lvalue that prevents calling the second constructor although programmer tries to explicitly move all the string and vector parameters. In reality, the actual moves do not happen and if the remaining program depends on the moves being successful may not be very happy.

Only in case of b6, all actual parameters are rvalues or literals. Therefore, the "all-rvalue-ref" constructor is called. Note that temporary string objects will be implicitly created where string literals are used.

So lets fix it. What we really need is just one constructor that accepts all the parameters by value. As a side-effect, the overall code is much simpler.

class Book {
public:
  Book(std::string title,
       std::vector<std::string> authors,
       size_t      pub_day
       std::string pub_month,
       size_t      pub_year)
    : _title    (std::move(title)),
      _authors  (std::move(authors)),
      _pub_day  (pub_day),
      _pub_month(std::move(pub_month)),
      _pub_year (pub_year)
     {}

  // ....
  // ....
};


That's it! This is our the constructor that works optimally. All strings, vectors, integral types are passed by value. Within the constructor, the pass-by-value parameters that are on the stack-frame must be moved to the respective data members. The reason is that the lifetime of pass-by-value parameters is anyways limited to the lifetime of the constructor call itself. We want to tie their lifetime to the object and not the constructor.

This constructor does no more deep copies of than necessary. And that number really depends on how it is called. Due to pass-by-value semantics, each object individually is an opportunity for the compiler to perform a move when a temporary is involved. Lets revisit our b1 to b4 objects.

In case of b1, except for authors all other parameters are copied and moved once.
In case of b2, all strings and vectors are copied and moved once. That's what matters.
In case of b3, toUpper returns an string reference; everything else copied and moved only once.
In case of b4, January returns a const string reference; everything else copied and moved once.
In case of b5, strings are vector are moved as expected and in fact the b5 object the local parameters are created using move-constructor and moved again into the data member. Hence the object is created without any deep copies (like zero-copy).

Using pass-by-value also opens other opportunities to eliminate temporaries when functions return by value and are used as actual parameters. However, I won't discuss that in detail here.

Finally, I want to conclude saying that this whole thing assumes that a move is much cheaper than a deep-copy. This is generally true for std::vector and std::string where memory is allocated dynamically. For small strings however small-string-optimization may make copy and move practically equivalent.

24 comments:

gwiazdorrr said...

Is this compiler behaviour defined somewhere in the standard?

Steve said...

Do you actually need the std::move()'s in the preferred constructor definition?

abigagli said...

Mmmm… Maybe I'm wrong, but I don't think that's really _the_optimal solution. If I understand correctly, in your proposed approach, you pay at least one copy, when "bringing" parameters into the stack frame of the constructor, and only then they'll be moved. The real zero-copy approach is to wrap in std::move the lvalues at the point where the constructor is called.
Am I missing something?

iatsbg said...

Perhaps it is a kind of copy elision similar to Return Value Optimization.
Here is a section of Dave Abrahams’s article: Want Speed? Pass by Value.

Although the compiler is normally required to make a copy when a function parameter is passed by value (so modifications to the parameter inside the function can’t affect the caller), it is allowed to elide the copy, and simply use the source object itself, when the source is an rvalue.

Sumant said...

@abigagli: Zero-copy is just not possible with all-const-ref constructor at all. With all-pass-by-value constructor, "necessary" copies will be made, which could be as low as zero. Say you have named variables (lvalues) for all the parameter the constructor is expecting. If you explicitly std::move all the those lvalues at the call-site of the constructor, there will be twice as many moves in total. And you get your logical zero-copy, which is really implemented as multiple moves.

dvide said...

@abigagli: In this example, the lvalues are never used again so you could have wrapped them in an std::move() call, yes. But imagine that the lvalues are used again at some point, so that making a copy is always going to be necessary. That's the point of this article. With the preferred implementation outlined here, you will only pay for the copies that are needed, not all or nothing. And importantly, the code is cleaner too. Remember that passing things by value does not necessarily imply a copy any more (although it never did because of copy elision, but ignoring that for now), because std::vector will have its own move constructor.

That's the cool thing about move semantics, it kinda cleans up the code in some contexts as well as providing the performance benefits.

dvide said...

Another cool thing is if you're implementing the copy-and-swap idiom. If you implement the assignment operator by taking the rhs parameter by value (which you already should do, to exploit any potential copy elision), you can get a move assignment operator for free simply by defining a move constructor. Then the one assignment operator will work for both move and copy assignment purposes, rather than needing two different assignment operators.

So it's super easy to implement full move semantics for your types if you're already using idiomatic code. And move elision is possible too, so sometimes even the move constructor won't be called if you do it that way.

AlfC said...

@steve, good question! can someone answer steve? if std::string and std::vector are implemented correctly std::move(...) is not necessary for the same reason, is it?

Sumant said...

@Steve: std::move in the preferred constructor are necessary. Within the constructor, the pass-by-value parameters that are on the stack-frame must be moved to the respective data members. The reason is that the lifetime of pass-by-value parameters is anyways limited to the lifetime of the constructor call itself. We want to tie their lifetime to the object and not the constructor.

@AlfC: As far as I know, std::string and std:vector are implemented "correctly" because they are "standard".

AlfC said...

I see. Needing so many std::moves looks a bit unelegant still. Thanks.

Xazax said...

Isn't using references implies the same amount of copy, moves? If I understand it well, by value method is copies the object to the stack of the constructor, then moves the object to the member of newly created object. So a copy + a move.

However if we pass by a reference, only a reference is copied to the constructor, and than, the member object is copied from the referenced object. So reference pass + deep copy.

Is really the first method more effective? Or am I wrong about what is happening?

Josh said...

@Xazax

I think an important piece missing from the description given is that most popular compilers will do copy elision on rvalues passed into functions. This means that for rvalues passed to the constructor, only a single move occurs vs 1 copy and 1 move. It is possible the compiler doesn't elide the copy when an rvalue is passed, and assuming the rvalue is movable, you'd get 2 moves instead of 1, which should still typically be cheaper than a copy operation.

As for passing lvalues by reference to the constructor. It's going to need to make a copy anyway, so you're paying for the cost of 1 move and 1 copy vs a single copy if passed by reference. Assuming move is cheap the cost of the extra move when passing lvalues shouldn't be a of much concern.

If you really want to have the most efficient code, you could override your constructor to take every permutation of rvalue refs and const lvalues, but that can quickly become terribly impractical and a maintenance nightmare.

mmocny said...

This is an excellent post and I totally agree, however, I wanted to add that this relies on the arguments to be move enabled.

If you are using a third party library which is not move enabled, yet there is some more efficient move-like operation you can do with it, you have to turn to other solutions (such as overloading on rvalue ref, or using a wrapper class that adds move operation).

Funny gifs said...

Written in a very professional, learning

GreenFox said...

I'm starting a code-centric blog I was wondering what you use to format your code.

Sumant said...

@GreenFox: I'm using http://alexgorbatchev.com/SyntaxHighlighter version 3.0 and https://sites.google.com to store the javascript and css files.

Balakrishnan.B said...

Do we need move here?
_authors (std::move(authors)),
Isn't it obvious here for the compiler that this is a temporary and move constructor should automatically kick in without having to specify manually?

Sumant said...

@Balakrishnan.B: Any named variable is an lvalue. So unless you use std:::move, compiler does not attempt a move.

Nordlöw said...

Does this mean that I unconditionally should convert all my template function/constructor arguments from const-reference to pass-by-value? If not could you give a list of cases of when to do what? What role does function inlining play in this case?

Sumant said...

I wish it was that simple. Even the best design guidelines cannot replace in-depth analysis of your specific problem. So a quick answer is use your judgement. The longer answer is, well, long!

In non-template code, if all the parameter types provide an efficient move constructor, the proposed technique in the post is a safe bet. You see at least two exceptions. First, non-template code: So what's different in template code? Templates open up more possibilities, such as perfect forwarding, which depends on using pass-by-rvalue-reference as opposed to pass-by-value. Compiler will figure out the best way passing the parameter. However, there is a gotcha and its solution rather requires pretty deep knowledge of language mechanics. So much wizardry is packed in it that it is counter productive IMHO. Please see this for more detail: http://codesynthesis.com/~boris/blog/2012/03/14/rvalue-reference-pitfalls-update

Second, efficient move ctor: Not all types have efficient move c-tor. for example, std::array, std::complex, etc. In such cases pass by const reference is probably the best idea.

Jon Kalb said...

dvide said...
Another cool thing is if you're implementing the copy-and-swap idiom. If you implement the assignment operator by taking the rhs parameter by value (which you already should do, to exploit any potential copy elision), you can get a move assignment operator for free simply by defining a move constructor. Then the one assignment operator will work for both move and copy assignment purposes, rather than needing two different assignment operators.


I'm not certain that it is so simple. You want your move assignment to be declared "noexcept" (so that std::swap() will be "noexcept") and you can do that if you create your own move assignment, but your copy assignment probably can't be noexcept (for example if have a std::string data member).

Anonymous said...

You might want to take a look on my post about virtual constructors in C++ here:

http://blog.panqnik.pl/dev/co-variant-and-virtual-constructor-in-c/

Erik Corry said...

Why would you ever want to pass a size_t by reference? This made no sense even before C++11

A size_t fits in a register and can be copied for free, whereas passing it by reference will force it onto the stack and put an extra level of indirection into the access.

Sumant Tambe said...

@Erik. Good point. the code was written to emphasize the use (or not using) references. I've changed it now.