新卒研修アプリのデータ構造の最適化に挑んでみた！

こんにちは、トイロジックを2023年に新卒で入社しました羊師匠です！

本記事では、トイロジックの新人研修のメインであるiPhone研修で作ったゲーム、『バクバクバック』に対して行った最適化をご紹介します！

『バクバクバック』はどういうゲーム？

敵から逃げつつ、タイミングを計って一気食いする爽快感のある見下ろし型ローグライクアクションゲームです！

『バクバクバック』は大量のエネミーを取り扱うため、一番負荷の重い処理は敵の生成・破棄処理ですが、オブジェクトプールを活用すればすぐに対策できます！

しかしエネミー1体に描画機能やAI、コライダーなどなど、たくさんのコンポーネントがついており、如何にアップデート処理の時間を抑えるかのも結構大事です。今回はあえて普段あんまり気づかないところに着目し、最適化の方法をご紹介します！

データ構造における最適化

「配列」と「連結リスト」は皆さんご存じかと思いますが、簡潔に言いますと、配列は連続したメモリ上に要素を格納し、一方連結リストは非連続なメモリブロックに要素を分散して格納し、各要素がポインタで互いにリンクされています。

そのため、配列ではインデックスを使用して任意の要素に直接アクセスできますが、連結リストでは要素にアクセスするためにリストを順にたどる必要があります。一方、配列は固定サイズで挿入や削除が遅いのですが、連結リストは動的サイズで挿入や削除が速いと言われています。

動的にオブジェクトを挿入・削除したい場合はとりあえず連結リストを使えばよいという印象です。さらにゲームオブジェクトの場合ですと、任意の要素に直接アクセスすることがなく、毎フレームリストを走査するから、一見連結リストにしか適任はないと思いますよね。しかし、それは意外と落とし穴です！

配列と連結リスト、どちらが向いているのか、実験してみましょう！ここで『バクバクバック』のコードを使用すると少し冗長でわかりずらいかと思いますので、別の実験用コードをご用意しました！

// コードを一部抜粋
// フールバージョンはこちら：https://github.com/simurayousuke/cpu-prefetch-exp/

// 配列と連結リストのルートオブジェクトを作成
GameObject<vector> arrayRoot;
GameObject<list> llistRoot;

// ツリー状の構造でデータを初期化
InitData(0, DEPTH, SUB_COUNT, arrayRoot);
InitData(0, DEPTH, SUB_COUNT, llistRoot);

// 10回実験をす
for (auto i = 0; i < 10; ++i)
{
	// 連結リストでワールドマトリックスを計算しなおす
	llistRoot.UpdateMatrix();
	// 使用時間の出力
	printf("llist: %2.3f ms ( %2.1f FPS)\r\n", time, 1000.0 / time);
										
	// 配列でワールドマトリックスを計算しなおす
	arrayRoot.UpdateMatrix();
	// 使用時間の出力
	printf("array: %2.3f ms ( %2.1f FPS)\r\n", time, 1000.0 / time);
}

これはツリー状の複数のゲームオブジェクトを走査し、ワールドマトリックスを全部計算しなおすに必要な時間を比較する実験です。ツリーの深さは10で、すべてのノードは100の子を持っています。つまり、ルートを含めて合計51201個のゲームオブジェクト(コンポーネント)があります。実験の結果は以下になります。

連結リストより配列の方の性能が明らかに良いのがわかりました。

なぜコンテナー変えただけでこんなにも違うの？

実は現代のCPUにはキャッシュがあり、さらにプリフェッチという機能があります。連結リストが遅いのではなく、このプリフェッチ機能が配列の走査を速めたということです。それでは、キャッシュとプリフェッチを一つずつ少しご説明しようと思います。

「キャッシュ」は、高速なメモリの一種で、CPUとメインメモリ（RAM）との速度差を埋めるために使用されます。キャッシュの読み書き速度はメモリの10～100倍だと言われています。CPUが必要とするデータや命令を高速に提供することで、全体的な処理速度を向上させます。キャッシュは通常、いくつかのレベル（L1、L2、L3など）に分かれており、L1が最も高速だが容量が小さく、L3は比較的遅いが容量が大きいといった特性があります。

「プリフェッチ」は、CPUが将来的に必要とする可能性のあるデータを、事前にメモリからキャッシュに読み込むことを指します。このプロセスは、データのアクセスパターンやアルゴリズムに基づいて自動的に行われます。目的は、CPUがデータを要求した時に、そのデータがすでにキャッシュに存在している状態を作り出すことです。

配列はメモリ上で連続しているため、プリフェッチが効率的に行え、キャッシュの恩恵を受けやすくなります。一方、連結リストの要素はメモリ上で非連続な位置に存在するため、プリフェッチが効果的に機能しにくく、キャッシュの効果も限定的になります。この結果、配列を使用した場合の方が連結リストを使用した場合よりも桁違いで性能が向上することがあります。

まとめ

いかがでしたでしょうか。今回は実験を通じて、配列と連結リストを使用したケースでの性能を比較し、ゲームオブジェクトのアップデート処理においては配列の方が優れていることを示しました。

配列とオブジェクトプールを同時に使用することで、ローディングの時間が少し長くなるかと思いますが、フレーム落ちの減少はとても期待できるでしょう。

最後までお読みいただきありがとうございました。皆様とゲームの奥深い世界で再び出会えることを心から願っています。未開の地を探検し、既成の枠を越え、ゲーム業界の新たな波を起こしましょう！

※本記事はトイロジックのゲーム開発技術ブログ「トイログ」からの転載です。他にも記事を読みたい方はぜひトイログをチェックしてみてください！

---

トイロジックでは現在、一緒に働くプログラマーを募集しています。
不明点などもお気軽にお問い合わせください。ご応募お待ちしております！

#プログラマー #ゲーム #ゲーム制作 #ゲーム開発 #ゲーム会社 #アクション #Cplusplus #オブジェクトプール #新卒研修