#counter
* ゲームプログラミングにおけるC++の都市伝説 [#x9f442ee]
この記事は、[[''C++ Advent Calendar 2012''>http://partake.in/events/a02d7049-1473-4b69-b5ad-25ed416c5557]] 22日目の記事です。
-Prev 21日目の記事 [[CEANによる配列操作>http://d.hatena.ne.jp/ignisan/20121221]]
-Next 23日目の記事 構造化並列プログラミング
時間の関係で3つの都市伝説しかご紹介できませんでしたが、またの機会があれば他の都市伝説についてもお話したいと思います。
2012/12/22 written by h.godai @hgodai
目次
-[[初めに>#k5a59394]]
-[[都市伝説１ C++は遅いのでゲームには向いていない>#o889d800]]
-[[都市伝説２ boost::poolはゲームには向いていない>#s3ca296b]]
-[[都市伝説３ boostライブラリは怪しいライブラリだ。使うと呪われる。>#h09bcf62]]
*初めに [#k5a59394]
かつて、8bit時代はゲームのプログラムはアセンブラが主流でした。やがて、ゲームのプラットフォームが16bitから32bitになるに従い、C言語でゲームが書かれるようになります。1980年代後半から最近まで、実に20年近くC言語がゲームプログラミングの主言語の座に居座っていました。
1990年代後半から、C++の開発環境が整備され、ゲームプログラミングにおいてC++が選択肢の一つに加わるようになりました。C言語と親和性の高いC++はすぐにゲームプログラム用の言語として使用されましたが、いっぽうでC++はゲームには向いていないと考えるエンジニアも多く、少なくとも2000年ごろまではゲームプログラミングの主流がC++に置き換わることはありませんでした。
C++はゲームプログラミングに向いていないのでしょうか？ もちろん、そんなことはありません。そのような噂は、C++に対する多くの誤解の元にできたものです。
ここでは、C++にまつわる都市伝説を通して誤解を解いていきたいとおもいます。
* 都市伝説１ C++は遅いのでゲームには向いていない [#o889d800]
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でのテストです。
**検証１ 世界で最も多くの人が実行するプログラム、「Hello World」を比べてみよう [#mca26be9]
-プログラムリスト
--C言語
printf(“Hello world\n”);
--C++言語
cout << “Hello world!” << endl;
-結果
#ref(CppAdvent_1-1.png)
C++標準ライブラリのstreamクラスは高機能で複雑な処理を行うので、さすがにシンプルなprintfより遅いだろうという予想していましたが、C++も意外と健闘してVisualStudioではprintfよりも速い結果になりました。Linuxではprintfの圧勝なので、"Hello World"対決は一勝一敗の五分というところでしょうか。いずれにしても、高機能なC++のstreamクラスを、パフォーマンスを理由に使用を避ける必要ななさそうです。
** 検証2 文字列の全文検索 (strstr vs std::string) [#nf51e35f]
つぎは、もう少し複雑なプログラムということで、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'
}
}
- 結果
#ref(CppAdvent_1-2.png)
ポインタを直接操作する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) [#m2d771fc]
検証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) {
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);
}
}
--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) {
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);
}
}
--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());
}
- 結果
#ref(CppAdvent_1-3.png)
この結果から、#defineマクロによる展開がまったく無意味なことが伺えます。VisualStudioもgccも、最適化オプションを付ければ適度にインライン展開されるため、わざわざマクロを使ってコードを汚すことは無いと言えるでしょう。
そして、このような比較的単純な処理でもC++のほうが高速な結果となっています。VisualStudioでは10%程度の差ですが、gccでは2倍以上の差がありました。
古いコードをC++用に書きなおすだけで処理速度が半分以下になるとしたら、ゲームプログラミングにおいて効果が大きいと言えるでしょう。
** 検証4 ソートライブラリ (libc vs STL) [#hefa1303]
最後の検証は、わりとよくあるやつ。qsort vs sortです。結果はもう見るまでもないですね。とりあえず、今までの検証と同じ条件でテストしてみました。
double x,y,zという要素をもつ100万個のオブジェクトのソート時間を計測します。
100万個のオブジェクトは、あらかじめ乱数で埋めておきます。比較条件は、それぞれのエレメントのx+y+zの合計値です。
-プログラム
--C言語
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);
--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());
- 結果
#ref(CppAdvent_1-4.png)
予想通り''C++の圧勝''です。VisualStudioでは''2.5倍''、gccでは''4倍''の差がつきました。
もう、議論の余地はありません。もし、qsort()を使っている個所があれば、すぐにsortに入れ替えるべきですね。
** 結論 [#mcdd6e06]
ほとんどの処理で、''C++はCよりも高速に動作します''。しかも処理が複雑なほどC++とCの差は広がる傾向にあります。もちろん、Cのままg++でコンパイルしても効果はありません。ちゃんとC++の作法に則ってプログラムを書きなおすことができれば、ほぼロジックを変えずにプログラムを高速化することができます。
レガシーなCで書かれたプログラムを、C++で書きなおすにはそれなりのコストが掛ると思いますが、ゲームプログラミングにおいては実行速度の大幅な高速化が期待できるメリットは大きいでしょう。しかも、複雑な機能を簡単に実装でき、ソースコードのメンテナンス性も格段に良くなります。（上記の検証プログラムを比較して見れば明らかでしょう）
C++はゲームプログラミングにおいて、少なくともC言語よりは最適なプログラミング言語と言えるでしょう。
* 都市伝説２ boost::poolはゲームには向いていない [#s3ca296b]
ゲームプログラミングにおいて、メモリーの管理は重要です。とくに、スマートフォンやコンシューマーゲーム機などはリソースに限りがあるので、無尽蔵にメモリーを消費するようなプログラムは書けません。しかも、パフォーマンスも重要で、組み込み型の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();
// 計測終了
}
-結果
#ref(CppAdvent_2-1.png)
ごらんのとおり。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(CppAdvent_2-2.png)
見事に平坦なグラフになりました。初回だけ、メモリー確保のために時間がかかっていますが、それ以降のmallocは完全に安定しています。
boost poolのコンストラクタにサイズを指定ができるとうことは、必要不可欠な機能だという事でしょう。とくにゲームの場合は、安定して動作させるためにサイズ指定は必須と言えます。
同様に、std::vectorにpush_backを行うようなプログラムの場合、かならずreserveしておくというのが、ゲームプログラミングでは常識となっています。
正しく使えば、boost poolはゲームプログラミングにおいて非常に有効なライブラリです。（実際に私も多用しております）
* 都市伝説３ boostライブラリは怪しいライブラリだ。使うと呪われる。 [#h09bcf62]
残念なことに、C++のプログラマ以外の人々には''boostライブラリの認知度は低く''、理解されないケースがあります。さらに、以下のような噂に尾ヒレがついて、このような都市伝説を作ってしまったのではないでしょうか。
-証言1 boost愛好者は、秘密の組織を作って''定期的に集会を開いている''らしい
-証言2 boostは''「魔道書」''を愛好者に配布し、''黒魔術的なプログラミングを布教している''らしい
-証言3 一度でもboostを使った者は、''二度とboostなしでは生きていけなくなる''らしい
-証言4 boostの深い所まで踏み込んでしまった者は、''魔術的なプログラミングの虜''になり、やがて役に立たないプログラムばかり作る''廃人''と化していくらしい
はい。これらは確かに事実かもしれませんが、boostは決して怪しいライブラリでななく、C++標準化委員会と密接に関わりをもつ公式なライブラリです。プログラマを虜にする魅力に満ちていますが、呪われてしまうような事はありませんので、安心して使ってください。
ただし、仕事でboostライブラリを使用する際は、''用法用量をきちんと守り、適切に使用してください''。使用方法を充分に理解せず、ネットからコピペして使っていると痛い目を見るかもしれません。ドキュメントは読みましょう。それでもわからない時はソースコードを読みましょう。「知恵袋」系の掲示板で質問してはいけません。怪しまれるだけです。[[''しかるべき筋の人''>http://d.hatena.ne.jp/faith_and_brave/]]に質問しましょう。これらの事を守れれば、boostはあなたの強い味方になってくれるはずです。
![[SSA]](https://www.techarts.co.jp/ssabanner.png "[SSA]")
