Tuesday, January 15, 2013

Swaptimizations - exploiting copy elision and RVO

Performance critical code for years has relied on passing everything by pointers to heap allocated objects. Often this is not the best, or even the fastest way to do this. Passing by value and returning by value use stack based entities which are much faster to allocate, de-allocate, and don't cause fragmentation of memory.
"C++ is my favorite garbage collected language because it generates so little garbage" - Bjarne Stroustrup
This is true if you write in such a way as to make this true. Smart pointers made it pretty easy to eliminate memory leaks, but it can be even better. Using RVO and copy elision we can pass by value pretty much all the time without the overhead of temporaries. Consider this code:
Texture MakeBigTexture
{
  Texture bigTexture();
  Do stuff
  return bigTexture;
}

void Init()
{
  Texture temp = MakeBigTexture();
}
This code seems wrong. What about the giant temporary? It doesn't exist. Compilers have long taken advantage of Return Value Optimization or RVO. The way it works is that the compiler knows the return is temporary. It also knows where it will ultimately end up. Why not put the temporary where it will ultimately end up? And that's what it does. 
Copy elision is the opposite. Here's an example
string FlipString(string str)
{
  reverse(str.begin(), str.end());
  return str;
}

string Source()
{
  return "Flip This String";
}

void main
{
  cout << FlipString(Source()) << endl;
}
The output of Source is a temporary so again the compiler moves the temporary to its final destination. In this case str.
Now the tricky part. You do not get RVO here. The reason is kind of simple. The compiler can put a temporary in one place or the other, but not both. So we will get a copy. But what if that copy is too expensive? Do we have to revert to pointers and references? No. We can do Swaptimization. Here's how it works.
string FlipString(string str)
{
  string result;
  result.swap(str);
  reverse(result.begin(), result.end());
  return result;
}

string Source()
{
  return "Flip This String";
}

void main
{
  cout << FlipString(Source()) << endl;
}
Result uses RVO and str uses copy elision. C++ 11 gives us rvalues and so we don't need to do this, but that is for another time.

No comments:

Post a Comment