Return value optimization

From Seo Wiki - Search Engine Optimization and Programming Languages

Jump to: navigation, search

Return value optimization, or simply RVO, is a C++-specific compiler optimization technique that involves eliminating the temporary object created to hold a function's return value.[1] It is particularly notable for being allowed to change the observable behaviour of the resulting program.[2]

Contents

Summary

In general, the C++ standard allows a compiler to perform any optimization, as long as the resulting executable exhibits the same observable behaviour as if all the requirements of the standard has been fulfilled. This is commonly referred to as the as-if rule.[3]The term return value optimization refers to a special clause in the C++ standard that allows an implementation to omit a copy operation resulting from a return statement, even if the copy constructor has side effects,[4] something that is not permitted by the as-if rule alone.[3]

The following example demonstrates a scenario where the implementation may eliminate one or both of the copies being made, even if the copy constructor has a visible side effect (printing text).[4] The first copy that may be eliminated is the one where first is copied into the function f's return value. The second copy that may be eliminated is the copy of the temporary object returned by f to second.

 
#include <iostream>
 
struct C 
{
  C() {}
  C(const C&) { std::cout << "Hello World!\n"; }   
};
 
C f() 
{
  C first;
  return first;  
}
 
int main() 
{
  C second = f();
}

Depending on the compiler, and the compiler's settings, the resulting program may display any of the following outputs:

Hello World!
Hello World!
Hello World!
<nothing>

Background

Returning an object of builtin type from a function usually carries little to no overhead, since the object typically fits in a CPU register. Returning a larger object of class type may require more expensive copying from one memory location to another. To achieve this, an implementation may create a hidden object in the caller's stack frame, and pass the address of this object to the function. The function's return value is then copied into the hidden object.[5] Thus, code such as this:

struct Data { char bytes[16]; };
Data f()
{
  Data result = {};
  // generate result
  return result;  
}
 
int main()
{
  Data d = f();  
}

May generate code equivalent to this:

struct Data { char bytes[16]; };
 
Data * f(Data * __hiddenAddress)
{
  Data result = {};
  // copy result into hidden object
  *__hiddenAddress = result;
  return __hiddenAddress;  
}
 
int main()
{
  Data __hidden; // create hidden object
  Data d = *f(&__hidden); // copy the result into d 
}

which causes the Data object to be copied twice.

In the early stages of the evolution of C++, the language's inability to efficiently return an object of class type from a function was considered a weakness.[6] Around 1991, Walter Bright invented a technique to minimize copying; effectively replacing the hidden object and the named object inside the function with the object used to hold the result:[7]

struct Data { char bytes[16]; };
 
void f(Data * p)
{
  // generate result directly in *p
}
 
int main()
{
  Data d;
  f(&d);
}

Bright implemented this optimization in his Zortech C++ compiler.[6] This particular technique was later coined "Named return value optimization", referring to the fact that the copying of a named object is elided.[7]

Compiler support

Return value optimization is supported on most compilers,[1] including Microsoft Visual C++,[8] g++,[9] and the Intel C++ Compiler.

However, there may be circumstances where the compiler is unable to perform the optimization. One common case is when a function may return different named objects depending on the path of execution: [8][10][5]

#include <string>
std::string f(bool cond = false)
{
  std::string first("first");
  std::string second("second");
  // the function may return one of two named objects
  // depending on its argument. RVO will probably not be applied
  if(cond) 
    return first;  
  else
    return second;
}
 
int main()
{
  std::string result = f();
}

Other forms of copy elision

Apart from the elision of the copy operation in a return statement, section 12.8, paragraph 15 of the C++ standard lists another case where copy elision is allowed, namely when a temporary object of class type is copied to an object of the same type.[4] This is also a very widely implemented optimization. As a result, copy-initialization is usually equivalent to direct-initialization in terms of performance, but not in semantics; copy-initialization still requires an accessible copy constructor.[11] The optimization can not be applied to a temporary object that has been bound to a reference. Example:

int n = 0;
struct C 
{
  C(int) {}
  C(const C&) { ++n; } // the copy constructor has a visible side effect
};                     // it modifies an object with static storage duration  
 
int main() 
{
  C c1(42); // direct-initialization, calls C::C(42)
  C c2 = 42; // copy-initialization, calls C::C(42) _or_ C::C( C(42) )
 
  return n; // returns either 0 or 1, depending on whether the copy was elided
}

The C++ standard also mentions that a similar optimization may be applied to objects being thrown and caught,[12][13] but it is unclear whether the optimization applies to both the copy from the thrown object to the exception object, and the copy from the exception object to the object declared in the exception-declaration of the catch clause. It is also unclear whether this optimization only applies to temporary objects, or named objects as well.[14] Given the following source code:

#include <iostream>
 
struct C 
{
  C() {}
  C(const C&) { std::cout << "Hello World!\n"; }   
};
 
void f() 
{
  C c;
  throw c; // copying the named object c into the exception object. 
}          // It is unclear whether this copy may be elided.
 
int main() 
{
  try 
  {
    f();
  }
  catch(C c) // copying the exception object into the temporary in the exception declaration.
  {          // It is also unclear whether this copy may be elided.
  }
}

A conforming compiler should therefore produce a program that prints "Hello World!" twice. In the upcoming C++ standard (C++0x), the issues have been addressed, essentially allowing the same set of outputs as the first program.[14]

References

  1. 1.0 1.1 Meyers, Scott (1996). More Effective C++. Addison Wesley. 
  2. Alexandrescu, Andrei (2003-02-01). "Move Constructors". Dr. Dobbs Journal. http://www.ddj.com/cpp/184403855. Retrieved 2009-03-25. 
  3. 3.0 3.1 ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages - C++ §1.9 Program execution [intro.execution] para. 1
  4. 4.0 4.1 4.2 ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages - C++ §12.8 Copying class objects [class.copy] para. 15
  5. 5.0 5.1 Bulka, Dov; David Mayhew (2000). Efficient C++. Addison-Wesley. ISBN 0-201-37950-3. 
  6. 6.0 6.1 Lippman, Stan. "The Name Return Value Optimization". Stan Lippman. http://blogs.msdn.com/slippman/archive/2004/02/03/66739.aspx. Retrieved 2009-03-23. 
  7. 7.0 7.1 "Glossary D Programming Language 2.0". Digital Mars. http://www.digitalmars.com/d/2.0/glossary.html. Retrieved 2009-03-23. 
  8. 8.0 8.1 Shoukry, Ayman B.. "Named Return Value Optimization in Visual C++ 2005". Microsoft. http://msdn.microsoft.com/en-us/library/ms364057(VS.80).aspx. Retrieved 2009-03-20. 
  9. "Options Controlling C++ Dialect". GCC. 2001-03-17. http://gcc.gnu.org/onlinedocs/gcc-2.95.3/gcc_2.html#SEC5. Retrieved 2009-03-20. 
  10. Hinnant, Howard; et al. (2002-09-10). "N1377: A Proposal to Add Move Semantics Support to the C++ Language". WG21. http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1377.htm. Retrieved 2009-03-25. 
  11. Sutter, Herb (2001). More Exceptional C++. Addison-Wesley. 
  12. ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages - C++ §15.1 Throwing an exception [except.throw] para. 5
  13. ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages - C++ §15.3 Handling an exception [except.handle] para. 17
  14. 14.0 14.1 "C++ Standard Core Language Defect Reports". WG21. http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#479. Retrieved 2009-03-27. 
Personal tools

Served in 0.492 secs.