Pizer’s Weblog

programming, DSP, math

C++: Exploiting Copy Elisions

with 8 comments

This article is about writing efficient code and giving the compiler opportunities for optimizations with respect to copying / “moving” objects in good old C++98. I use a simple function as an example but it should extend to other cases as well. The technique that is described here (“swaptimization”) is not entirely new and I can’t take credit for it. But it is probably little-known which is a good reason to write about it. :-)

How would you write a function that accepts a string (with call-by-value semantics, source is not modified) and returns a reversed string by value? Perhaps something like this?

  // version 1, C++98
  std::string flip_str(std::string const& x)
  {
    std::string result = x;
    std::reverse(result.begin(),result.end());
    return x;
  }

You might have chosen to accept the parameter as reference-to-const to avoid unnecessary copying like I did above. But is this really the best thing we can do? To answer this, let’s check what and how a compiler is allowed to optimize (elide copies):

  • If a function returns a function-local object (including temporary) it is allowed to elide the copy construction of the function’s result (return value optimization).
  • If an object obj of type X is initialized with a temporary of type X, the compiler is allowed to elide this copy and make obj an alias for this temporary. This includes the initialization of pass-by-value function parameters.

Many C++ compiler actually perform these optimizations in many situations. So, in order to write efficient code we should try to exploit this.

If you check the implementation of flip_str version 1 again you’ll notice that I manually created a copy of the string, named result. In this case it’s easy for compilers to perform the named return value optimization. The return expression directly refers to the local object result. But we havn’t exploited temporaries as function arguments. What about this version?

  // version 2, C++98
  std::string flip_str(std::string x)
  {
    std::reverse(x.begin(), x.end());
    return x;
  }

In version 2 we let the compiler worry about how x should come to life. In case the function is invoked with an lvalue argument the compiler will make sure that x refers to a copy. In case it’s a temporary the compiler might be able to elide the copy (x might alias the temporary object). So far so good. What about RVO? You could argue that x is a local variable. But to implement the mentioned copy elision optimizations the compiler probably generated a function that actually takes two addresses behind the scenes — one for the pass-by-value parameter x and one for the to-be-constructed return value. In version 2 the line “return x;” will then copy-construct the return value from x, so no NRVO is done. In C++0x we could simply write

  // version 3, C++0x (relying on a fast move constructor)
  std::string flip_str(std::string x)
  {
    std::reverse(x.begin(), x.end());
    return std::move(x);
  }

Because std::string is a rather small object that only manages the character array through an internal pointer, move constructing strings can be expected to be much faster than copy constructions — unless your std::string implementation uses copy-on-write. Still, it should be at least a bit faster. C++98 doesn’t support move construction directly. But there is a trick to get a similar behaviour in this case. Instead of a move construction we can use swap and rely on NRVO:

  // version 4, C++98
  std::string flip_str(std::string x)
  {
    std::string result; // empty string, expected to be fast
    result.swap(x); // swapping, expected to be fast
    std::reverse(result.begin(), result.end());
    return result; // NRVO applicable
  }

Swapping is a kind of two-way moving. If your type supports fast swapping you should consider writing such a swap member function along with a free inline function and/or a specialization of the std::swap template so that algorithms can benefit from it.

Finally, let’s verify how many times the string‘s copy constructor is invoked in the following example code:

  // test code
  #include <iostream>
  #include <algorithm>
  #include <string>

  using std::string;

  string source() {return "Hello World!";}

  // insert flip_str version 1, 2, or 4

  int main() {
    string hw = flip_str(flip_str(source()));
    std::cout << hw << '\n';
  }

To verify how many times the copy c’tor of string is invoked we could replace the inclusion of the <string> header and the using std::string; declaration with the following dummy class:

  // string replacement for testing
  struct string {
    string()
      {std::cout<<"string::string()\n";}
    string(char const*)
      {std::cout<<"string::string(char const*)\n";}
    string(string const&)
      {std::cout<<"string::string(string const&)\n";}
    ~string()
      {std::cout<<"string::~string()\n";}
    void swap(string & with)
      {std::cout<<"string::swap(string &)\n";}
    char* begin() {return 0;}
    char* end() {return 0;}
  };

With this replacement and the g++ compiler I obtained the following results:

  Output for flip_str version 1 and 2:
  string::string(char const*)
  string::string(string const&)
  string::string(string const&)
  string::~string()
  string::~string()
  string::~string()


The output for version 1 and 2 is exactly the same in this case. Here it is for version 4:

  Output for flip_str version 4:
  string::string(char const*)
  string::string()
  string::swap(string &)
  string::string()
  string::swap(string &)
  string::~string()
  string::~string()
  string::~string()


The use of version 1 results in two copy constructions (total). The same is true for version 2. The use of version 4 didn’t involve any copy constructions. Just two default constructions and two swaps.

Conclusions:
For types that have a fast default constructor and a fast associated swap function we can exploit the compilers’ copy elision capabilities to increase performance. Other examples for these kinds of types include most STL containers (vector, deque, list, set, map, …).

- P

About these ads

Written by pizer

June 25, 2009 at 4:57 pm

8 Responses

Subscribe to comments with RSS.

  1. > In C++0x we could simply write
    > std::string flip_str(std::string x)
    > {
    > std::reverse(x.begin(), x.end());
    > return std::move(x);
    > }”

    Why “return std::move(x)” ?
    “return x;” do the job as well.

    Arzar

    June 29, 2009 at 4:05 pm

  2. I’m not so sure about that. From what I know the variable ‘x’ is currently not considered a function-local variable which would mean the return value is copy-constructed from x. I don’t think there’s any problem with letting the compiler treat ‘x’ like a function-local object so that it implicitly prefers a move construction of the return value. I’s just that I remember talking to someone trustworhty who explained to me that pass-by-value function parameters are not function-local with respect to copy elision and implicit move. But maybe this is wrong and/or the rules have changed. I’ll check this out later. In any case this explicit move should not degrade performance since current C++ implementations don’t even support NRVO in case the return expression names a pass-by-value parameter.

    pizer

    June 29, 2009 at 5:53 pm

  3. Arzar: It seems you’re right. std::move is not necessary for returning function parameters that have been accepted by value. At least this is the conclusion I draw from more recent examples by Dave Abrahams and a discussion in the comp.std.c++ newsgroup.

    pizer

    August 18, 2009 at 11:05 am

  4. In case of interest: Output with cl.exe, Version 16.00.21003.01 which ships with MS VisualStudio 2010 Professional Beta 2. All optimization stuff turned on.

    Impressive is the bad performance of Version 1. :-O. I mean, I expected it to be the worst option, but THAT bad?

    Interesting also, that cl do cleanup of temporaries inbetween (which is probably bad for reference counting? Or maybe its just irrelevant).

    flip_str Version 1:
    string::string(char const*)
    string::string(string const&)
    string::string(string const&)
    string::~string()
    string::string(string const&)
    string::string(string const&)
    string::~string()
    string::~string()
    string::~string()
    string::~string()

    flip_str Version 2 and 3:
    string::string(char const*)
    string::string(string const&)
    string::~string()
    string::string(string const&)
    string::~string()
    string::~string()

    flip_str Version 4:
    string::string(char const*)
    string::string()
    string::swap(string &)
    string::~string()
    string::string()
    string::swap(string &)
    string::~string()
    string::~string()

    Immanuel Scholz

    March 16, 2010 at 4:10 pm

  5. Thanks for your comments! Wow. version 1 performs really bad. What happened? Did you really turn on all the optimizations? From what I know, Microsoft’s compiler only does NRVO when optimizations are turned on. I only gave version 3 to show how move-enabled types can be used. Since the dummy string class has no move constructor you don’t see any difference between ver2 and ver3. But as soon as you add a move constructor the two copies should turn into move constructions which are really cheap (at least for std::string).

    pizer

    March 29, 2010 at 9:28 pm

  6. What version of g++ did you use?

    bmburstein

    July 3, 2012 at 1:19 pm

  7. Hello bmburstein! Well, it was 3 years ago and I can’t really say for sure. But it was probably something like 4.2.

    pizer

    July 4, 2012 at 11:11 am

  8. […] C++: Exploiting Copy Elisions […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: