KMC活動ブログ

京大マイコンクラブの活動の様子を紹介します！！

Return Value Optimization (RVO)の話 【KMCアドベントカレンダー20日目】

KMCアドベントカレンダー2014

Return Value Optimization (RVO) の話

この記事は、今年もやります！KMCアドベントカレンダー！！ - KMC活動ブログの20日目の記事です。 昨日の19日目の記事はRustは開発中だけど面白い!【KMCアドベントカレンダー19日目】 - KMC活動ブログでした。

KMC3回生のhatsusatoです。 当初はC++のrvalue周りの話をしようと考えていたのですが、rvalueの解説記事は他にたくさんあるしなあ……、と渋っていたら天啓が来たのでRVOの話をします。

RVOとは

Return Value Optimization (RVO)とは、C++におけるコンパイラ最適化技術の名前です。 その名の通り、関数の戻り値に対して余分なコピーや一時オブジェクトを削減する最適化を施します。 コピーコンストラクタには副作用のある処理を書くこともできるので、コピーを削減するRVOがあるのとないのとでは、最終的な実行コードが異なることがあります。 しかし、C++の規格においてRVOは例外的に、たとえ実行コードが変わってしまうとしても行ってよい最適化として認められています。 実際には、コピーやムーブなどにおいてよほど変な処理を書かないかぎり、問題になることはありません。 この機能はよくあるC++コンパイラ(GCCとかClangとかMSVCとか)にはだいたい備わっていて、普段誰もが何気なくお世話になっています。

RVOのしくみ

最適化が適用される主な状況は、関数の戻り値などの一時オブジェクトをreturn文で戻すときです。

#include <iostream>
struct A {
  A(int i = 0) : x(i) {}
  A(const A&) { std::cout << "copy"; }
  int x;
};
A rvo() {
  return A();
}
int main() {
  A a = rvo();  // copy が呼ばれない
  A b = a;  // copy が呼ばれる
  return 0;
}
  • RVOの例

考えてみれば関数(rvo)の戻り値(A())は、その関数の呼び出し元の受け取り先の変数(a)に値を伝えたあとは破棄するだけの一時オブジェクトなので、戻り値を返す(return A())際に直接受け取り先(a)に書き込んでも問題ないはずです。 このような状況において、RVOが実装されているコンパイラでは余分なコピーや一時オブジェクトを削減してくれます。

void rvo(A* _result) {
  new (_result) A();
  return;
}
int main() {
  char a[sizeof(A)];
  rvo(reinterpret_cast<A*>(a));
  reinterpret_cast<A*>(a)->~A();
  return 0;
}

まるでメンバ関数における暗黙のthisポインタのように、関数の引数に戻り値を格納する先の変数へのアドレスを渡します。 そしてそのアドレスの先の上にオブジェクトを構築することで、関数内部での一時オブジェクト生成を呼び出し元のオブジェクト生成とみなすことができます。 このようにしてRVOは実現されています。

さらにNRVO

RVOをさらに推し進めたNamed Return Value Optimization (NRVO)というものがあります。 これはRVOよりも強力な最適化を施しますが、実装されているコンパイラは限られています。 先のRVOではreturn文で戻していたのは一時オブジェクトでしたが、NRVOは名前のついたローカル変数を戻すときに働く最適化です。

A nrvo(int y) {
  A a;
  a.x += y;
  return a;
}
  • NRVOの例

最終的に戻す変数(a)のすべてを、暗黙に受け取った戻り値の格納先(_result)で置き換えることでNRVOを実現しています。

void nrvo(A* _result, int y) {
  new (_result) A();
  _result->x += y;
  return;
}

戻り値として返したいオブジェクトはすべて_resultで表せないと行けないので、すべてのreturn文で戻すオブジェクトが同じオブジェクトでないと最適化が働きません。 同様のことはRVOにも言えます。 同じオブジェクトを返したからと言って最適化が適用されるかどうかはコンパイラによりますが。

A not_nrvo() {
  A a, b;
  return true ? a : b;
}
  • NRVO最適化が適用できない例

まとめ

RVO(およびNRVO)はC++コンパイラにおいて人知れず働き、コードを壊さない範囲でラジカルな最適化を行い、C++のコードを高速化しているのです。

次回予告

明日12月21日(日)のKMCアドベントカレンダーは、 wackyさんによる「イケてると思うdotfilesの管理方法」です。

参考文献