3

If I have the following function declaration that returns a std::list<Triangle*> by value:

std::list<Triangle*> getAllAbove(Triangle* t);

when I return the std::list<Triangle*> (which is created on the stack in getAllAbove) at the end of getAllAbove, will GCC be able to optimize out the call to std::list<Triangle*>'s copy constructor (which presumably would iterate through all of the elements and copy them), or at least copy only the list metadata (e.g. not the elements themselves)? The list could potentially contain a few thousand pointers and I would like to avoid copying all of them needlessly.

Is the only way in which to bypass the copy constructor call to create the list on the heap and then return a pointer to it?

greatwolf
  • 20,287
  • 13
  • 71
  • 105
WirthLuce
  • 1,361
  • 13
  • 23
  • 1
    See also [http://stackoverflow.com/questions/1394229/understanding-return-value-optimization-and-returning-temporaries-c](http://stackoverflow.com/questions/1394229/understanding-return-value-optimization-and-returning-temporaries-c) – Bo Persson Jun 08 '11 at 05:20

5 Answers5

6

Well, the alternative way to bypass copying is to use the "return parameter" idiom instead of using the return value of the function

void getAllAbove(Triangle* t, std::list<Triangle*>& result);

Instead of forming the result "on the stack" as you do now, form it directly in result parameter (i.e. in the recipient list that you pass from the caller).

As for your original code, whether the copying will take place or not depends on the capabilities of your compiler.

From the most abstract point of view, your code actually has two copyings. (And yes, these are full-fledged copyings when the entire content of the list is meticulously duplicated in another list, element by element.) Firstly, the named list object you create on the stack inside your function is copied to a nameless temporary object that holds the return value of the function. Then the temporary object is copied to the final recipient object in the calling code. Most compilers will be able to eliminate one of these copyings (to eliminate the intermediate temporary, as allowed by C++98 specification).

To eliminate the second one the compiler has to be able to perform so called Named Return Value Optimization (as allowed by C++03 specification). A compiler that supports Named Return Value Optimization should be able to essentially implicitly convert your function's interface into the equivalent of the above "return parameter" idiom. I would expect GCC to be able to do it. Try it and see what happens.

AnT stands with Russia
  • 312,472
  • 42
  • 525
  • 765
  • 2
    "Most compilers will be able to eliminate one of these copyings" - if the result of `getAllAbove` is used in an initializer. If it's used in a copy-assignment, then it can't be eliminated. Hence `std::list foo = getAllAbove(bar);` is good. `foo = getAllAbove(bar);` is bad. `getAllAbove(bar).swap(foo)` is a workaround to avoid the bad without having to change the signature of the function. C++0x move semantics are a fix for the bad. – Steve Jessop Jun 08 '11 at 07:33
  • @Steve Jessop: I see what you mean, but I don't understand why you attached it to that specific statement of mine. That statement refers to C++98 elision, which allows eliminating the copying from named local object to intermediate temporary object. That copying can be eliminated regardless of whether the function is used in copy-assignment or in initialization. I.e. instead of copying, the lifetime of the named local object is extended so as to use it as a RHS in the assignment. It is the second elimination that becomes problematic in assignment context. The first one is always possible. – AnT stands with Russia Jun 08 '11 at 14:08
  • @AndreyT: I'm probably just confused which one you're referring to as the one that most compilers can eliminate, then. I'd actually expect that most compilers can eliminate both, anyway. As you say, the chronologically first copy, the NRVO, is always applicable. The copy from the temporary (or named object, if NRVO has happened) to the final destination can be elided if it's a copy ctor, not if it's copy assignment. That's the one I thought you meant by "eliminate the intermediate temporary, as in C++98". – Steve Jessop Jun 08 '11 at 15:05
  • @Steve Jessop: That's actually an interesting question. C++98 allows copy elision when a temporary is copied *from* in initialization context. However, on top of that C++98 allows copy elision when a temporary is copied *to* in `return` context. It is not clear to me whether C++98 allows applying both elisions at the same time (in "return value used as initializer" context). C++03 states explicitly that both can be applied, while, as I believed, C++98 expects the compiler to choose only one of the two (in initialization context). – AnT stands with Russia Jun 08 '11 at 15:29
  • In assignment context C++98 would be forced to choose the second one, because that's the only one available. That's what I meant by my "Most [C++98] compilers will be able to eliminate one of these copyings". – AnT stands with Russia Jun 08 '11 at 15:29
  • Ah, right. I guess if we looked far enough into the C++03 process, we could figure out whether the permission to do both was intended as a completely new (backward-incompatible) feature, or just that the C++98 text was judged not to explicitly say what they always intended it to say. – Steve Jessop Jun 08 '11 at 15:59
4

Generally you don't need to worry, unless you have reasons to: Want Speed? Pass by Value.

Gene Bushuyev
  • 5,512
  • 20
  • 19
2

Write the code in the way that seems the easiest to understand and maintain it. Then profile. If this is a problem spot, optimize it by eliminating the copy, otherwise leave it the way it is.

I'd expect my compiler to apply return value optimization to that, though, making manual intervention needless. And I expect the next version of my compiler to make all this irrelevant because it applies move semantics to the problem, turning the copying of a container (copying all of its values) into a simple copying of two pointers.

Community
  • 1
  • 1
sbi
  • 219,715
  • 46
  • 258
  • 445
0

To get rid of worrying about compiler optimization, you can pass list<> by reference to the function.

std::list<Triangle*>& getAllAbove(Triangle* t, std::list<Triangle*>& myList);

You can either return by reference or simply not return it.

iammilind
  • 68,093
  • 33
  • 169
  • 336
0

You can go with void getAllAbove(Triangle* t, std::list<Triangle*>& out). Fill out the list once and get the output in out

Mayank
  • 5,454
  • 9
  • 37
  • 60