![[SSA]](https://www.techarts.co.jp/ssabanner.png "[SSA]")
この記事は、C++ Advent Calendar 2012 のため作成しました。 時間の関係で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++にまつわる都市伝説を通して誤解を解いていきたいとおもいます。
1990年ごろ、私が初めてC++に触れたとき、C++は遅いと感じました。C++のコーディングに関する知識に乏しく、すべてのクラスは"CObject"を継承し、メソッドはすべてvirtualにしていました。STLのような便利なものはなく、コンテナも自前でお粗末なものを作っていました。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でのテストです。
printf(“Hello world\n”);
cout << “Hello world!” << endl;
C++標準ライブラリのstreamクラスは高機能で複雑な処理を行うので、さすがにシンプルなprintfより遅いだろうという予想していましたが、C++も意外と健闘してVisualStudioではprintfよりも速い結果になりました。Linuxではprintfの圧勝なので、"Hello World"対決は一勝一敗の五分というところでしょうか。いずれにしても、高機能なC++のstreamクラスは、使うのをためらうほどは遅いということはなさそうです。
つぎは、もう少し複雑なプログラムということで、char*型の文字列から特定の文字列を検索する、全文検索の処理速度を比べてみましょう。
被検索対象は約45KBのテキスト文字で、boost/foreach.hpp のテキストを使用しました。検索する文字列は、"BOOST"という文字で、foreach.hpp内には260個の"BOOST"という文字が存在しています。
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'
}
} 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の関数を使う必要性は少ないと言えるでしょう。
検証2でC++が良いスコアを出したのは、最適化によるインライン展開による効果が大きいことが考えられます。ならば、C言語には"#define"という非常に強力かつ無慈悲なマクロ機能がありますから、C言語もマクロで展開してしまえば、C++のテンプレートと同等の速度を出せるかもしれません。
検証３では、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) {
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);
}
}
}#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);
}
}
} 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++用に書きなおすだけで処理速度が半分以下になるとしたら、ゲームプログラミングにおいては効果が大きいでしょう。
最後の検証は、わりとよくあるやつ。qsort vs sortです。結果はもう見るまでもないですね。とりあえず、今までの検証と同じ条件でテストしてみました。
double x,y,zという要素をもつ100万個のオブジェクトのソート時間を計測します。 100万個のオブジェクトは、あらかじめ乱数で埋めておきます。比較条件は、それぞれのエレメントのx+y+zの合計値です。
typedef struct Element {
double x,y,z;
} Element;
int compare(const void* va, const void* vb) {
const Element* a = (const Element*)va;
const Element* b = (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); 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言語よりは最適なプログラミング言語と言えるでしょう。
ゲームプログラミングにおいて、メモリーの管理は重要です。とくに、スマートフォンやコンシューマーゲーム機などはリソースに限りがあるので、無尽蔵にメモリーを消費するようなプログラムは書けません。しかも、パフォーマンスも重要で、組み込み型のnew/deleteもしくはシステムライブラリのmalloc/freeは速度が遅い場合が多く、ゲーム内で多用するとゲーム全体のパフォーマンスを低下させてしまいます。さらに、確保と解放を繰り返すことによるメモリーの断片化も非常に重要な問題となります。
これらの問題を一気に解決してくれそうなライブラリがboostにあります。そう、boost poolライブラリです。boost poolは、同一サイズのオブジェクトが多数あるような場合、速度面でもメモリサイズ面でも非常に少ないオーバヘッドで動作してくれます。さらに、使用済みのメモリを一括して削除できるため、たとえばタイトル画面に戻った時などにすべてのメモリーをパージしてしまえば、フラグメントの問題も大幅に解消できます。
そんな便利なboost poolライブラリですが、「ゲームには向いていない」という話しを耳にする事があります。その理由は、mallocにかかる時間が安定しないという事です。具体的に言うと、「通常は非常に高速だが、時々致命的なほど遅くなる」ということです。これが本当ならば、たしかにゲームには不向きでしょう。
さっそく、「都市伝説１」で使用した速度計測ツールを使って、boost::poolのmallocに掛る時間を計測してみました。
uint64_t* ptrs_[100000];
boost::object_pool<uint64_t> intpool;
for (int n = 0; n < 100000; ++n) {
// 計測開始
ptrs_[n] = intpool.malloc();
// 計測終了
}
ごらんのとおり。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のコンストラクタに、あらかじめ確保すべき要素数を指定しておくだけです。ゲームの場合、消費されるリソースの最大値はほとんどの場合固定されるので、必要なサイズをあらかじめ確保しておく事は簡単でしょう。プログラムを修正してテストしてみます。
uint64_t* ptrs_[100000];
boost::object_pool<uint64_t> intpool(100000);
for (int n = 0; n < 100000; ++n) {
// 計測開始
ptrs_[n] = intpool.malloc();
// 計測終了
}
見事に平坦なグラフになりました。初回だけ、メモリー確保のために時間がかかっていますが、それ以降のmallocは完全に安定しています。 boost poolのコンストラクタに指定ができるとうことは、良く使う機能だからでしょう。とくにゲームの場合は、安定して動作させるためにサイズ指定は必須と言えます。
同様に、std::vectorにpush_backを行うようなプログラムの場合、かならずreserveしておくというのが、ゲームプログラミングでは常識となっています。 正しく使えば、boost poolはゲームプログラミングにおいて非常に有効なライブラリです。（実際に私も多用しております）
残念なことに、C++のプログラマ以外の人々にはboostライブラリの認知度は低く、理解されないケースがあります。さらに、以下のような事実が尾ヒレのついた都市伝説を作ってしまったのではないでしょうか。
はい。これらは確かに事実かもしれませんが、boostは決して怪しいライブラリでななく、C++標準化委員会と密接に関わりをもつ公式なライブラリです。プログラマを虜にする魅力に満ちていますが、呪われてしまうような事はありませんので、安心して使ってください。
