Counter: 0, today: 0, yesterday: 0

ゲームプログラミングにおけるC++の都市伝説

この記事は、C++ Advent Calendar 2012 22日目の記事です。

時間の関係で3つの都市伝説しかご紹介できませんでしたが、またの機会があれば他の都市伝説についてもお話したいと思います。

2012/12/22 written by h.godai @hgodai

 目次

初めに

かつて、8bit時代はゲームのプログラムはアセンブラが主流でした。やがて、ゲームのプラットフォームが16bitから32bitになるに従い、C言語でゲームが書かれるようになります。1980年代後半から最近まで、実に20年近くC言語がゲームプログラミングの主言語の座に居座っていました。

1990年代後半から、C++の開発環境が整備され、ゲームプログラミングにおいてC++が選択肢の一つに加わるようになりました。C言語と親和性の高いC++はすぐにゲームプログラム用の言語として使用されましたが、いっぽうでC++はゲームには向いていないと考えるエンジニアも多く、少なくとも2000年ごろまではゲームプログラミングの主流がC++に置き換わることはありませんでした。

C++はゲームプログラミングに向いていないのでしょうか? もちろん、そんなことはありません。そのような噂は、C++に対する多くの誤解の元にできたものです。

ここでは、C++にまつわる都市伝説を通して誤解を解いていきたいとおもいます。

都市伝説1 C++は遅いのでゲームには向いていない

1990年ごろ、私が初めてC++に触れたとき、C++は遅いと感じました。C++のコーディングに関する知識に乏しく、すべてのクラスはCObjectを継承し、メソッドはすべてvirtualにしていました。STL(Standard Template Library)といった便利なライブラリはなく、コンテナも自前でお粗末なものを作っていました。C++のコンパイラは、どんなにひどいコードも文句を言わず喜んでコンパイルしてくれました。最近のコンパイラのように気の利いた警告は出ませんでした。 私自身、テンプレートが使えるようになるまで、C++は遅いと思っていました。それでもオブジェクト指向で設計し、C++でプログラムするメリットのほうが大きいと感じていたので使っていました。(パフォーマンスに対してクリティカルな部分はアセンブラを使っていました。) 当時の「便利で良い言語だけど実行速度がCに比べて遅い」というイメージが、いつの間にか都市伝説となってしまたのではないでしょうか。

では、C言語とC++で書かれた等価なプログラムの実行速度を測定して、「C++はCより遅いのか?」を検証してみましょう。

速度の計測は、CPUのカウンタを使用したAPIを使っています。Windows版はVisualStudio2008、Linux版はUbuntu10.4 gcc4.4.2 の環境で測定を行いました。 コンパイルオプションは、それぞれ速度に対して最高レベルの最適化を設定してあります。 テストプログラムは、10万回~100万回ほどのループを10回繰り返し、最大と最小を排除した8回分の平均値を計算しています。

残念ながらC++11でのテスト環境がそろっていないため、C++03でのテストです。

検証1 世界で最も多くの人が実行するプログラム、「Hello World」を比べてみよう

#ref(): File not found: "CppAdvent_1-1.png" at page "ScopedAllocator"

C++標準ライブラリのstreamクラスは高機能で複雑な処理を行うので、さすがにシンプルなprintfより遅いだろうという予想していましたが、C++も意外と健闘してVisualStudioではprintfよりも速い結果になりました。Linuxではprintfの圧勝なので、"Hello World"対決は一勝一敗の五分というところでしょうか。いずれにしても、高機能なC++のstreamクラスを、パフォーマンスを理由に使用を避ける必要ななさそうです。

検証2 文字列の全文検索 (strstr vs std::string)

つぎは、もう少し複雑なプログラムということで、char*型の文字列から特定の文字列を検索する、全文検索の処理速度を比べてみましょう。

被検索対象は約45KBのテキスト文字で、boost/foreach.hpp のテキストを使用しました。検索する文字列は、"BOOST"という文字で、foreach.hpp内には260個の"BOOST"という文字が存在しています。

#ref(): File not found: "CppAdvent_1-2.png" at page "ScopedAllocator"

ポインタを直接操作するC言語のシンプルなstrstr関数にくらべて、C++はSTLのコンテナとアルゴリズムという高機能で複雑な処理です。ところが、結果はC++の圧勝。VisualStudioでは半分近い速度で実行してしまいました。gccでは1割程度の差にとどまったことから、gccのCライブラリに対する最適化がVisualStudioに比べて高性能なのではないかと思われます。

この2つのプログラムをよく見てください。普通に考えれば、どう見てもCのプログラムのほうがシンプルで速そうです。C++のプログラムは、stringというクラスに文字列のデータが隠ぺいされ、findというメソッドを介して動作しています。検索位置もポインタではなくインデックスで管理されており、メモリアドレスを直接示しているポインタを使ったCのプログラムのほうが速そうです。しかし、現実は確実にC++のほうが速いという結果が出ています。プログラムの処理速度というのは、見た目で判断するのは難しく、測定してみないと確かな事はわからないという良い例でしょう。

機能的にはC++のコンテナやアルゴリズムが圧倒しているので、もはや文字列操作にCの関数を使う必要性は殆ど無いと言えます。

検証3 ビットマップのピクセル処理 (C vs #define vs C++ template)

検証2でC++が良いスコアを出したのは、最適化によるインライン展開による効果が大きいことが考えられます。ならば、C言語には"#define"という非常に強力かつ無慈悲なマクロ機能がありますから、C言語もマクロで展開してしまえば、C++のテンプレートと同等の速度を出せるかもしれません。

検証3では、C言語の関数コールによる処理と、#defineマクロによる処理、C++テンプレートによる処理を比べてみます。

対象となるテストプログラムは、RGBが5:6:5bitの16bit/pixelのイメージデータのRとGとBを入れ替える処理を行います。ループの処理とビット演算が主な処理内容となります。

int get_r(short x) { return ((x >> 8) & 0xf8); }
int get_g(short x) { return ((x >> 3) & 0xfc); }
int get_b(short x) { return ((x << 3) & 0xff); }

short to_rgb(int r, int g, int b) {
  return (short)(((r << 8) & 0xf800) | ((g << 3) & 0x07e0) | (b >> 3));
}

void test_bitmap_color_transform_pure_c(short* buffer) {
  short* p = buffer;
  int n;
  for (n = 0; n < IMAGE_HEIGHT * IMAGE_WIDTH; ++n, ++p) {
    int r = get_r(*p);
    int g = get_g(*p);
    int b = get_b(*p);
    *p = to_rgb(g, b, r);
  }
}
#define GET_R(x) ((x >> 8) & 0xf8)
#define GET_G(x) ((x >> 3) & 0xfc)
#define GET_B(x) ((x << 3) & 0xff)
#define TO_RGB(r, g, b) (((r << 8) & 0xf800) | ((g << 3) & 0x07e0) | (b >> 3))

void test_bitmap_color_transform_macro_c(short* buffer) {
  short* p = buffer;
  int n;
  for (n = 0; n < IMAGE_HEIGHT * IMAGE_WIDTH; ++n, ++p) {
      int r = GET_R(*p);
      int g = GET_G(*p);
      int b = GET_B(*p);
      *p = (short)TO_RGB(g, b, r);
  }
}
 template <int PixelBits>
 struct pixel_t {};
 template <>
 struct pixel_t<16> {
   uint16_t value_;
   pixel_t() : value_(0) {}
   pixel_t(int r, int g, int b)
       : value_(static_cast<uint16_t>(((r << 8) & 0xf800) | ((g << 3) & 0x07e0) | (b >> 3)))
   {}
   int get_r() const { return (value_ >> 8) & 0xf8; }
   int get_g() const { return (value_ >> 3) & 0xfc; }
   int get_b() const { return (value_ << 3) & 0xff; }
 };
 struct transcolor {
     template <typename Pixel>
     void operator () (Pixel& px) {
         px = Pixel(px.get_g(), px.get_b(), px.get_r());
     }
 };
 
 void test_bitmap_color_transform_cpp(vector< pixel_t<16> >& buffer)
   for_each(buffer, transcolor());
 }

#ref(): File not found: "CppAdvent_1-3.png" at page "ScopedAllocator"

この結果から、#defineマクロによる展開がまったく無意味なことが伺えます。VisualStudioもgccも、最適化オプションを付ければ適度にインライン展開されるため、わざわざマクロを使ってコードを汚すことは無いと言えるでしょう。 そして、このような比較的単純な処理でもC++のほうが高速な結果となっています。VisualStudioでは10%程度の差ですが、gccでは2倍以上の差がありました。 古いコードをC++用に書きなおすだけで処理速度が半分以下になるとしたら、ゲームプログラミングにおいて効果が大きいと言えるでしょう。

検証4 ソートライブラリ (libc vs STL)

最後の検証は、わりとよくあるやつ。qsort vs sortです。結果はもう見るまでもないですね。とりあえず、今までの検証と同じ条件でテストしてみました。

double x,y,zという要素をもつ100万個のオブジェクトのソート時間を計測します。 100万個のオブジェクトは、あらかじめ乱数で埋めておきます。比較条件は、それぞれのエレメントのx+y+zの合計値です。

#ref(): File not found: "CppAdvent_1-4.png" at page "ScopedAllocator"

予想通りC++の圧勝です。VisualStudioでは2.5倍、gccでは4倍の差がつきました。 もう、議論の余地はありません。もし、qsort()を使っている個所があれば、すぐにsortに入れ替えるべきですね。

結論

ほとんどの処理で、C++はCよりも高速に動作します。しかも処理が複雑なほどC++とCの差は広がる傾向にあります。もちろん、Cのままg++でコンパイルしても効果はありません。ちゃんとC++の作法に則ってプログラムを書きなおすことができれば、ほぼロジックを変えずにプログラムを高速化することができます。

レガシーなCで書かれたプログラムを、C++で書きなおすにはそれなりのコストが掛ると思いますが、ゲームプログラミングにおいては実行速度の大幅な高速化が期待できるメリットは大きいでしょう。しかも、複雑な機能を簡単に実装でき、ソースコードのメンテナンス性も格段に良くなります。(上記の検証プログラムを比較して見れば明らかでしょう) C++はゲームプログラミングにおいて、少なくともC言語よりは最適なプログラミング言語と言えるでしょう。

都市伝説2 boost::poolはゲームには向いていない

ゲームプログラミングにおいて、メモリーの管理は重要です。とくに、スマートフォンやコンシューマーゲーム機などはリソースに限りがあるので、無尽蔵にメモリーを消費するようなプログラムは書けません。しかも、パフォーマンスも重要で、組み込み型のnew/deleteもしくはシステムライブラリのmalloc/freeは速度が遅い場合が多く、ゲーム内で多用するとゲーム全体のパフォーマンスを低下させてしまいます。さらに、確保と解放を繰り返すことによるメモリーの断片化も非常に重要な問題となります。

これらの問題を一気に解決してくれそうなライブラリがboostにあります。そう、boost poolライブラリです。boost poolは、同一サイズのオブジェクトが多数あるような場合、速度面でもメモリサイズ面でも非常に少ないオーバヘッドで動作してくれます。さらに、使用済みのメモリを一括して削除できるため、たとえばタイトル画面に戻った時などにすべてのメモリーをパージしてしまえば、フラグメントの問題も大幅に解消できます。

そんな便利なboost poolライブラリですが、「ゲームには向いていない」という話しを耳にする事があります。その理由は、mallocにかかる時間が安定しないという事です。具体的に言うと、「通常は非常に高速だが、時々致命的なほど遅くなる」ということです。これが本当ならば、たしかにゲームには不向きでしょう。

さっそく、「都市伝説1」で使用した速度計測ツールを使って、boost::poolのmallocに掛る時間を計測してみました。

     uint64_t* ptrs_[100000];
     boost::object_pool<uint64_t> intpool;
     for (int n = 0; n < 100000; ++n) {
       // 計測開始
       ptrs_[n] = intpool.malloc();
       // 計測終了
     }

#ref(): File not found: "CppAdvent_2-1.png" at page "ScopedAllocator"

ごらんのとおり。10万回のmallocのほとんどが300ナノ秒以下で処理が終わっていますが、8回ほど非常に時間がかかっています。最悪なのは65505回目の273μ秒で、平均的な時間の実に1000倍の時間を要しています。

STLやboostに精通されている皆さんならこのグラフを見ただけでピンときますね。そうです。これは、std::vectorの要素をpush_backで増やし続けた時の所要時間のグラフとピッタリ一致します。 boost poolはvectorと同じように、メモリーの動的な確保を倍々のサイズで行っていきます。初期値は32要素で、33番目の要素が必要になると64個に拡大していきます。そして、65505番目(2^16 - 31)の要素が必要となった時には、65536個の要素がアロケーターから確保されます。その時の所要時間が、mallocの時間となっているのです。

解決方法は簡単です。object_poolのコンストラクタに、あらかじめ確保すべき要素数を指定しておくだけです。ゲームの場合、消費されるリソースの最大値はほとんどの場合固定されるので、必要なサイズをあらかじめ確保しておく事は難しくないでしょう。intpoolのコンストラクタにサイズ指定を追加してテストしてみます。

     uint64_t* ptrs_[100000];
     boost::object_pool<uint64_t> intpool(100000);
     for (int n = 0; n < 100000; ++n) {
       // 計測開始
       ptrs_[n] = intpool.malloc();
       // 計測終了
     }

#ref(): File not found: "CppAdvent_2-2.png" at page "ScopedAllocator"

見事に平坦なグラフになりました。初回だけ、メモリー確保のために時間がかかっていますが、それ以降のmallocは完全に安定しています。 boost poolのコンストラクタにサイズを指定ができるとうことは、必要不可欠な機能だという事でしょう。とくにゲームの場合は、安定して動作させるためにサイズ指定は必須と言えます。

同様に、std::vectorにpush_backを行うようなプログラムの場合、かならずreserveしておくというのが、ゲームプログラミングでは常識となっています。 正しく使えば、boost poolはゲームプログラミングにおいて非常に有効なライブラリです。(実際に私も多用しております)

都市伝説3 boostライブラリは怪しいライブラリだ。使うと呪われる。

残念なことに、C++のプログラマ以外の人々にはboostライブラリの認知度は低く、理解されないケースがあります。さらに、以下のような噂に尾ヒレがついて、このような都市伝説を作ってしまったのではないでしょうか。

はい。これらは確かに事実かもしれませんが、boostは決して怪しいライブラリでななく、C++標準化委員会と密接に関わりをもつ公式なライブラリです。プログラマを虜にする魅力に満ちていますが、呪われてしまうような事はありませんので、安心して使ってください。

ただし、仕事でboostライブラリを使用する際は、用法用量をきちんと守り、適切に使用してください。使用方法を充分に理解せず、ネットからコピペして使っていると痛い目を見るかもしれません。ドキュメントは読みましょう。それでもわからない時はソースコードを読みましょう。「知恵袋」系の掲示板で質問してはいけません。怪しまれるだけです。しかるべき筋の人に質問しましょう。これらの事を守れれば、boostはあなたの強い味方になってくれるはずです。


トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS