2

I was thinking of developing some named parameter code, but it got me thinking of some code like the following:

#include <utility>

int main() 
{
  using std::make_pair;
  auto x = make_pair(1, make_pair(2, make_pair(3, make_pair(4,5))));
}

Now, a naive implementation of this would do "make_pair(4,5)" first, then copy the result into the second element of "make_pair(3, ...)", and then copy that into the second element of "make_pair(2, ...)" etc.

This would result in O(n^2) performance unfortunately, with a lot of unnecessary copies. I can't see how (named) return value optimization helps here either.

Ideally, make_pair(4,5) realizes it's going to be in the last spot of x, and constructs itself in that place.

Taking this further:

#include <utility>

int main() 
{
  using std::make_pair;
  auto&& x1 = make_pair(3, make_pair(4,5));
  auto x2 = make_pair(1, make_pair(2, std::move(x1)));
}

I'd like to avoid the copies in code like this also.

Is this optimization so obvious that I should assume compilers perform it or is there another way I should be coding this to avoid the copies?

Clinton
  • 22,361
  • 15
  • 67
  • 163
  • 3
    Even with current C++ and a decent compiler that code doesn't make any unnecessary copy (I wrote a little test with g++ and no copies are present in the assembly code generated). – 6502 May 02 '11 at 06:22
  • Statements like: I can't see how (named) return value optimization helps here either are going to get you hammered. Programmers are really bad at understanding what the compiler actually does. Just try it and see what actually happens. Then you can make statements like: *The compiler does not maage to spot the optimization X how do I make my code more friendly to the compiler* – Martin York May 02 '11 at 08:49

2 Answers2

5

[N]RVO does help in cases like this. Basically what happens is that one composite object gets allocated, and the "return value" from each of the functions ends up going directly into the object that will hold the result.

If you're going to do much of this (especially in C++11), it's almost certainly cleaner, simpler and more direct to use a tuple instead, so your:

auto x = make_pair(1, make_pair(2, make_pair(3, make_pair(4,5))));

would end up like:

auto x = make_tuple(1, 2, 3, 4, 5);

This probably won't affect the generated code much, but (at least IMO) it's a lot easier to read.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
1
make_pair(1, make_pair(2, make_pair(3, make_pair(4,5))));

All the make_pairs which are arguments into another make_pair will create a temporary which is treated as an rvalue reference and is thus not copied.

I think what you really want is make_tuple.

ronag
  • 49,529
  • 25
  • 126
  • 221