ダブルヘッドスタックアロケータ

高性能アプリケーション、例えばビデオゲームをプログラミングしていると、限られたリソースを最大限に活用する高速なコードを書くための巧妙なテクニックを学びます。メモリ割り当ては、可変量のメモリを必要とするパフォーマンスクリティカルなコードにとって非常に大きなトピックです。「スタックアロケータ」と聞くと、「alloca」を思い浮かべるかもしれませんが、これは実際のプログラムスタックからメモリを割り当てることができます。これは緊急時には非常に便利ですが、今日の記事のトピックではありません。今日私たちが話しているスタックアロケータのもう一つの呼び名は「バンプアロケータ」です。 スタックアロケータ 2010年頃、私はSurreal Software（Midway Seattle）で、残念ながらMidwayが倒産したためにキャンセルされたオープンワールドゲーム「This is Vegas」に取り組んでいました。そのプロジェクトで、私の職務の一つはアニメーションプログラミングでした。アニメーションは、ボーンのセットに対するステートマシンを使用して動作し、各ステートはアニメーションブレンドのツリーでした。ステートが変更されると、連続性を維持するために古いステートから新しいステートへとブレンドアウトしていました。多くのブレンドが行われており、これらのアニメーションをCPU上で評価およびブレンドするために、多数の動的メモリ割り当てが使用されていました。しかし、これらの割り当てはすべて一時的なもので、フレームの一部期間しか存在する必要がありませんでした。さらに、これらの割り当てはフレームごとに発生する必要がありました。なぜなら、例えばカメラのフラスタムに基づいて、そのフレームでアニメートされているキャラクターが何であるかによって、状況は1フレームから次のフレームへと劇的に変化する可能性があるからです。アロケータは、このコードセクションのプロファイリングでホットスポットとして現れました。この問題を解決するために、私たちは「スタックアロケータ」を実装しました。このアロケータでは、割り当ては単なる整数加算であり、解放はさらに安価です。これを行うには、必要な最大量、例えば1MBのメモリを確保し、それをスタックとして使用します。また、スタックのトップを知るための整数変数「tos」も保持します。メモリを割り当てたい場合、メモリはスタックのトップにあるメモリであり、次の割り当てがあなたの割り当ての後になるように、tos変数に割り当てたいバイト数を加算します。 uint8_t* StackAllocate(uint8_t* mem, size_t& tos, size_t size){ uint8_t* ret = &mem[tos]; tos += size; return ret; } 実際の実装では、メモリのサイズも知っておく必要があります。これにより、tosがメモリの終端に達した場合の処理（nullを返す、アサートするなど）を行うことができます。メモリの使用が終わったら、tos変数を0に設定するだけです。 tos = 0; // スタック割り当てをすべて解放 私たちのケースでは、アニメーションブレンドが完了し、結果を頂点シェーダーへのスキニングのためにバッファにコピーした後、tosを0に設定しました。ゲームフレーム中に一時的なメモリ割り当てすべてにスタックアロケータをより一般的に使用していた場合、フレームが開始されるときに0に戻すかもしれません。結果は劇的なものでした。割り当てはもはやプロファイラで測定可能な時間を取らなくなりました。なぜなら、割り当ては整数加算であり、すべてのメモリを解放するのは単一の整数代入だったからです。それより速くなることはありません。 注意点として、この実装ではデストラクタは呼び出されません。コンストラクタにプレースメントnewを使用するのは簡単です。デストラクタを呼び出すのはより難しく、手動プロセスになり、エラーが発生しやすいです。RAIIパターンを使用できるかもしれませんが、スタックアロケータは単純な型に最適です。 スタックアロケータのもう一つの素晴らしい点は、マルチスレッド環境でも動作することです。tos変数がアトミック加算を使用する場合、複数のスレッドが同じスタックアロケータから割り当てを行うことができます。これは、CPUでのフォーク/ジョイン状況や、GPUで実行される複雑なアルゴリズムに役立ちます。スタックアロケータで「部分解放」を行うこともできます。例えば、各レベルが動的割り当てを必要とする再帰的なプロセスがあった場合、そのレベルが開始されたときのtosの値を覚えておき、そのレベルの処理が終了したときにその値に戻すことができます。 ダブルヘッドスタックアロケータ 数年後、私はBlizzardのStarCraft 2チームにいました。私のボスであるJames Anhaltは（そして今も）非常に賢い人物で、私にシェーダーおもちゃを紹介し、以前のブログ投稿で紹介されたクールなテクニックをたくさん共有してくれました。彼は、過去に遭遇したメモリ断片化の問題の解決策として、ダブルヘッドスタックアロケータについて教えてくれました。ストリーミングワールドゲームを想像してみてください。プレイヤーが世界を駆け巡るにつれて、古いレベルジオメトリが解放され、新しいレベルジオメトリがディスクから割り当てられストリーミングされてきます。同時に、プレイヤーキャラクターが異なる形態に変身でき、形態が変わるたびに古い形態が解放され、新しい形態がディスクから割り当てられストリーミングされてくると想像してください。課題は、これら2つのシステムがランダムな量のメモリを、それぞれ独自のタイムラインで割り当て、解放していると、メモリが断片化してしまうことです。簡単な例を見てみましょう。レベル（赤）とキャラクター（緑）のために合計100MBのメモリがあるとします。レベルが20MBを割り当て、次にキャラクターが30MBを割り当て、次にレベルが20MBを割り当て、キャラクターが最後の30MBを割り当てます。レベルデータ（赤）の割り当てがキャラクターの割り当て（緑）とインターリーブされています。 次に、プレイヤーが新しいセクションに移動したため、古いレベルデータのメモリが解放されたとします。新しいレベルデータは単一の30MBの割り当てを必要とするだけです。40MBの空きメモリがありますが、それは一つの塊ではありません！20MBのブロックが2つだけです。そのため、新しいレベルデータはそれより小さいにもかかわらず、そのためのスペースを割り当てることができません。これがメモリ断片化であり、メモリが制約された環境では大きな問題です。レベルデータが解放され、キャラクターの割り当てのみが残ります。40MBの空きがあるにもかかわらず、30MB（3ブロック）の新しいレベルデータの割り当てスペースがありません！ そこで、Jamesは、このような状況で彼らが何をしたかというと、通常のスタックアロケータのようなメモリチャンクを持っていましたが、レベルデータは0から上向きに成長するtosを持ち、キャラクターデータはメモリの末尾から下向きに成長するtosを持っていました。彼らが互いに交差して、レベルのtosがキャラクターのtosより大きくなったときに、メモリがなくなったことがわかります。それがどのように機能するか見てみましょう。 レベルデータ（赤）の割り当てとキャラクターデータ（緑）の割り当て。レベルデータが解放され、キャラクターの割り当てのみが残ります。レベルデータは、同じメモリブロック内に別のスタックアロケータを保持することで、必要な30MBを割り当てることができます。メモリ断片化はありません。これにより、レベルデータが変更する必要があるときに、レベルのtosを0に戻し、必要なメモリを再割り当てすることができ、断片化は一切発生しませんでした。同様に、キャラクターがメモリを解放したとき、そのtosをメモリの末尾に戻し、必要なメモリを再割り当てすることができ、これも断片化はありませんでした。再び、これらのアロケータはマルチスレッド環境でもうまく機能します。各スレッドがどちらかの側から割り当てを行う可能性がある場合でもです。tosインデックスへのアトミック加算だけで十分です。 「なぜダブルヘッドではなく、2つのスタックアロケータを持たないのか？」と疑問に思うかもしれません。主な利点は、メモリが制約されており、一方のスタックアロケータのサイズが2つのシステムにサービスを提供するのに十分であるとわかっているが、一方に割り当てられるメモリの割合が柔軟である場合です。前述のようなゲームの状況では、一部のレベルがより多くのメモリを使用できることを意味しますが、そのような状況では、キャラクターはメモリ使用量を削減する必要があります。少しこじつけの例ですが、意図は伝わったかと思います。 有限領域での可変サイズオブジェクトの格納 固定量のメモリに多数の可変サイズオブジェクトを格納しようとする場合、インデックスによるランダムアクセスを望む場合に、これのバリエーションがあります。例えば、効率のために特定のサイズのネットワークパケットを送信したい場合、そのメモリに可変個の可変サイズのネットワークコマンドをエンコードしたいとします。簡単にアクセスできるようにしたいのです。