ソフトウエア研究会in秋葉原

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
ゲームプログラミングの都市伝説へ行く。
- 1 (2012-12-22 (土) 16:01:20)
- 2 (2012-12-22 (土) 19:16:23)
- 3 (2012-12-22 (土) 22:03:29)
- 4 (2012-12-23 (日) 00:00:59)
- 5 (2012-12-23 (日) 02:55:43)
- 6 (2012-12-24 (月) 04:06:10)

現在作成中です。 †

この記事は、C++ Advent Calendar 2012 のため作成しました。

初めに
都市伝説１　C++は遅いのでゲームには向いていない
都市伝説２ boost::poolはゲームには向いていない
都市伝説３　boostライブラリは怪しいライブラリだ。使うと呪われる。

初めに †

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

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

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

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

↑

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

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

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

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

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

↑

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

プログラムリスト

C言語
```
	printf(“Hello world\n”);
```
C++言語
```
	cout << “Hello world!”  << endl;
```

結果

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

↑

検証2 文字列の全文検索 (strstr() vs STL) †

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

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

プログラム

C言語

       const char* p = source_text; // boost/foreach.hppの内容
       const char* search_text = "BOOST";
       size_t tlen = ::strlen(search_text);
       uint32_t found = 0;
       while (p && *p) {
         p = ::strstr(p, search_text);
         if (p) {
           ++found;
           p += tlen; // size of 'BOOST'
         }
       }

C++言語

     string text(source_text);  // boost/foreach.hppの内容
     string search_text("BOOST");
     uint32_t found = 0;
     string::size_type p = 0;
     while (p != string::npos) {
	p = text.find(search_text, p);
	if (p != string::npos) {
	  ++found;
	  p += search_text.length(); // size of 'BOOST'
	}
     }

結果

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

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

↑

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

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

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

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

プログラム

C言語(関数コール)

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) {
    int x,y;
    for (y = 0; y < IMAGE_HEIGHT; ++y) {
        short* row = &buffer[y * IMAGE_WIDTH];
        for (x = 0; x < IMAGE_WIDTH; ++x) {
            short* p = &row[x]; 
            int r = get_r(*p);
            int g = get_g(*p);
            int b = get_b(*p);
            *p = to_rgb(g, b, r);
        }
    }
}

C言語(マクロ)

#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) {
    int x,y;
    for (y = 0; y < IMAGE_HEIGHT; ++y) {
        short* row = &buffer[y * IMAGE_WIDTH];
        for (x = 0; x < IMAGE_WIDTH; ++x) {
            short* p = &row[x]; 
            int r = GET_R(*p);
            int g = GET_G(*p);
            int b = GET_B(*p);
            *p = (short)TO_RGB(g, b, r);
        }
    }
}

C++言語(テンプレート)

 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());
 }

結果

この結果から、#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の合計値です。

プログラム

C言語

 struct Element {
   double x,y,z;
 }
 int compare(const void* va, const void* vb) {
   const Element& a = *static_cast<const Element*>(va);
   const Element& b = *static_cast<const Element*>(vb);
   if (a.x+a.y+a.z < b.x+b.y+b.z) return 1;
   if (a.x+a.y+a.z > b.x+b.y+b.z) return -1;
   return 0;
 }
 ...
 const size_t ELEMENT_SIZE = 1000000;
 Element* element = (Element*)malloc(ELEMENT_SIZE * sizeof(Element));
 // setup random value to element
 qsort(element, ELEMENT_SIZE, sizeof(Element), compare);

C++言語

 struct Element {
   double x,y,z;
   bool operator () (const Element& a, const Element& b) const {
     return a.x+a.y+a.z < b.x+b.y+b.z;
   }
 };
 ...
 const size_t ELEMENT_SIZE = 1000000;
 vector<Element> element(ELEMENT_SIZE);
 // setup random value to element
 sort(element.begin(), element.end(), Element());

結果

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

↑

結論 †

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

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

↑

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

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

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

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

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

ゲームプログラミングの都市伝説 のバックアップ(No.2)

現在作成中です。 †

初めに †

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

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

検証2 文字列の全文検索 (strstr() vs STL) †

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

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

結論 †

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

ゲームプログラミングの都市伝説のバックアップ(No.2)

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

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