ハンドルはポインタよりも優れている (2018)

ハンドルはポインタよりも優れている

2018年11月28日: スロットごとの世代カウンタを使用して「ハンドル衝突」を防ぐ方法について、簡単なアップデートを追加しました。

元の投稿:

…ここでは、最近CおよびC++で動的メモリ管理をどのように行っているかについて少し説明します。これは基本的に、生のポインタやスマートポインタを「インデックスハンドル」に置き換えるものです。

私の前回のブログ記事では、ポインタフリーおよびアロケーションフリーのプログラミングについて言及しましたが、詳細は省略していました。以下は、そのブログ記事の内容です。

これはすべて、スマートポインタを通じてメモリが管理されることがよくある、かなり大きなC++コードベース（0.5から約1Mloc）で15年以上格闘した（時には苦痛な）経験に基づいています。最悪のケースでは、数万から数十万の小さなC++オブジェクトがそれぞれ独自のヒープアロケーションにあり、スマートポインタを通じて互いに指し合っています。このようなコードはメモリ破損（セグメンタルトラブルや破損は、スマートポインタの逆参照時にほとんどのアサーションで検出されるため、めったに発生しません）という点では非常に堅牢ですが、この種の「オブジェクトスパイダーウェブコード」は、最適化の明確な開始点がないため、コード全体がキャッシュミスだらけで非常に遅いです。その他の典型的な問題は、メモリの断片化と「偽のメモリリーク」です。これは、忘れられたスマートポインタが基になるメモリの解放を妨げるためです（メモリデバッグツールでは検出できないため、これを「偽のリーク」と呼びます）。

ここで提示するものは、特に新しいものでも巧妙なものでもありません。これらは、より大きなコードベースで、CおよびC++における一般的なメモリ関連の問題を回避（または少なくとも早期に検出）するために、一緒にうまく機能するいくつかの単純なアイデアの集まりであり、ガベージコレクタへの圧力を減らすために、高レベルのガベージコレクション言語でも役立つ可能性があります。

しかし、根本的な設計哲学は、互いにやり取りする小さな自律的なオブジェクトからアプリケーションが構築される古典的なOOPの世界にはあまり適合しません。そのため、オブジェクトの作成と破棄がコードのいたるところで「分散」して行われる、大規模な既存のOOPコードベースにこれらのアイデアを実装するのは非常に難しいです。

ここで説明するアプローチは、中央システムがメモリ内に密に詰め込まれたデータアイテムの配列で作業するデータ指向アーキテクチャでは非常にうまく機能します。

以下のブログ記事のほとんどは、ゲーム開発者の視点から書かれていますが、プログラムがメモリ内で数百から数百万のオブジェクト（または一般的に「データアイテム」）を処理する必要があり、そのようなアイテムが頻繁に作成および破棄される他の分野にも適用できるはずです。

要点は次のとおりです。

• すべてのメモリ管理を、レンダリング、物理、アニメーションなどの集中型システムに移行する。システムがメモリ割り当ての唯一の所有者となる。
• 同じタイプのアイテムを配列にグループ化し、配列のベースポインタをシステムプライベートとして扱う。
• アイテムを作成するときは、ポインタではなく「インデックスハンドル」のみを外部に返す。
• インデックスハンドルでは、配列インデックスに必要なビット数のみを使用し、残りのビットを追加のメモリ安全性チェックに使用する。
• ハンドルをポインタに変換するのは、絶対に必要になったときだけで、ポインタをどこにも保存しない。

これらの各点を以下で詳しく説明します。しかし、基本的な考え方は、一般的な「ユーザーレベル」コードが直接メモリ割り当て関数（malloc、new、make_shared/make_uniqueなど）を呼び出さず、ポインタの使用を最小限（アイテムへの直接メモリアクセスが絶対に必要で、一時的な参照としてのみ）に減らすということです。最も重要なのは、ポインタがアイテムの基になるメモリの「所有者」になることは決してないということです。

代わりに、メモリ関連の問題のデバッグと最適化が容易な少数の集中型システム内で、可能な限り直接的なメモリ操作が行われます。

メモリ管理を中央システムに移行する

このブログ記事では、「システム」とは、コードベースの（通常はかなり大きな）部分であり、「レンダリング」、「物理」、「AI」、「キャラクターアニメーション」などの一連の関連タスクを処理するものを指します。そのようなシステムは、明確に定義された関数APIを通じて他のシステムや「ユーザーコード」から分離されており、システムのデータに対して行われる作業は、コードベース全体に広がるのではなく、タイトな中央ループで実行されます。

システムは、ユーザーコードの制御下で作成および破棄されるアイテムを扱うことがよくあります（ただし、アイテムの作成と破棄は、それらのアイテムが使用するメモリの割り当てと解放とは異なることに注意してください！）。たとえば、レンダリングシステムは、頂点バッファ、テクスチャ、シェーダー、パイプラインステートオブジェクトなどを扱う場合があります。物理システムは、剛体、ジョイント、衝突プリミティブなどを扱います。アニメーションシステムは、アニメーションキーとカーブなどを扱います。

一般的なメモリマネージャは、データアイテムの処理方法やデータアイテム間の関係について、システム固有の「ドメイン知識」を持っていないため、そのようなアイテムのメモリ管理をシステム自体に移行するのは理にかなっています。これにより、システムはメモリ割り当てを最適化し、アイテムの作成および破棄時に追加の検証チェックを実行し、CPUのデータキャッシュを最大限に活用するためにメモリ内のアイテムを配置できます。

「システムドメイン知識」の良い例は、最新の3D APIでのレンダリングリソースオブジェクトの破棄です。リソースオブジェクトは、ユーザーコードが破棄を指示してもすぐに破棄することはできません。なぜなら、リソースがGPUによって消費されるのを待っているコマンドリストでまだ参照されている可能性があるからです。代わりに、レンダリングシステムは、ユーザーコードが破棄を要求したときにリソースオブジェクトを破棄のためにマークするだけで、実際の破棄はGPUがリソースを使用しなくなった後、後で発生します。

同じタイプのアイテムを配列にグループ化する

すべてのメモリ管理がシステムに移行されたら、システムはその追加の知識を使用してメモリ割り当てとメモリレイアウトを最適化できます。1つの明らかな最適化は、同じタイプのアイテムを配列にグループ化し、システム起動時にそれらの配列を割り当てることによって、一般的なメモリ割り当ての数を減らすことです。

新しいアイテムが作成されるたびにメモリ割り当てを実行する代わりに、システムは空き配列スロットを追跡し、次��空きスロットを選択します。ユーザーコードがアイテムを必要としなくなると、システムは解放を実行する代わりに、スロットを再度空きとしてマークするだけです（典型的なプールアロケータと違いはありません）。

このプール割り当ては、アイテムごとのメモリ割り当てを実行するよりもわずかに高速である可能性が高いですが、これがアイテムを配列に保持する主な理由ではありません（最新の一般的なアロケータも小さな割り当てには非常に高速です）。

いくつかの追加の利点があります。

• アイテムはメモリ内に密に詰め込まれることが保証されます。一般的なアロケータは、実際のアイテムメモリの隣にハウスキーピングデータを保持する必要がある場合があります。
• 「ホットアイテム」を連続したメモリ範囲に保持しやすく、CPUがデータキャッシュを最大限に活用できます。
• さらにタイトなパッキングとより良いデータキャッシュ使用のために、単一アイテムのデータを異なる配列の複数のサブアイテムに分割することも可能です（AoS対SoAおよびその間のすべて）。そして、それらのデータレイアウトの詳細はすべてシステムプライベートのままであり、外部コードに影響を与えることなく簡単に変更できます。
• システムが配列を再割り当てする必要がない限り、メモリ断片化が発生しないことが保証されます（ただし、64ビットアドレス空間ではこれはそれほど問題ではありません）。
• メモリリークを早期に検出するのが容易になり、より有用なエラーメッセージを提供できます。新しいアイテムが作成されると、システムは現在のアイテム数を期待される上限と比較して簡単にチェックできます（たとえば、ゲームではテクスチャが同時に1024個を超えることはないはずだとわかっており、すべてのテクスチャはレンダリングシステムを通じて作成されるため、この数が上限を超えた場合にシステムはより有用な警告メッセージを出力できます）。

ポインタの代わりに公開インデックスハンドル

システムアイテムをユニークな割り当てではなく配列に保持することには、アイテムをポインタではなく配列インデックスで識別できるという利点があります。これはメモリ安全性に非常に役立ちます。システムは、メモリポインタを外部に渡す代わりに、配列ベースポインタを「プライベート知識」として扱い、公開するには配列インデックスのみを渡すことができます。ベースポインタなしでアイテムのメモリ位置を計算すると、外部コードは、たとえ悪意があっても、アイテムのメモリにアクセスできません。

これにはさらにいくつかの利点があります。

• 多くの場合、システム外のコードはアイテムのメモリに直接アクセスする必要はなく、システムのみがアクセスします。そのような「理想的な」状況では、ユーザーコードはポインタを介してメモリにアクセスすることはなく、メモリ破損を引き起こすこともありません。
• システムのみが配列ベースポインタを知っているため、アイテム配列を自由に移動または再割り当てして、既存のインデックスハンドルを無効にすることなく処理できます。
• 配列インデックスはフルポインタよりも少ないビットを必要とし、それらのために小さいデータ型を選択できます。これにより、データ構造のタイトなパッキングとデータキャッシュ使用の向上が可能になります（ただし、追加のハンドルビットをメモリ安全性向上に使用できるという注意点があります。これについては後述します）。

ユーザーコードがアイテムのメモリに直接アクセスする必要がある場合、「ハンドルを入力として受け取り、ポインタを返す」ルックアップ関数`を介してポインタを取得する必要があります。このようなルックアップ関数が存在するとすぐに、上記のような非常に堅牢なメモリ安全性シナリオは保証されなくなり、ユーザーコードはいくつかのルールに従う必要があります。

• ポインタはどこにも保存してはいけません。次にポインタを使用するとき、それは同じアイテムを指していないか、有効なメモリを指していない可能性があります。
• ポインタは、単純なコードブロックでのみ使用し、関数呼び出しを「またいで」使用してはいけません。

ハンドルがポインタに変換されるたびに、システムは返されたポインタがハンドルが最初に作成されたのと同じアイテムを指していることを保証できます（これについては後述します）。しかし、この保証は時間の経過とともに「減衰」します。ポインタの下にあるアイテムが破棄されたり、基になるメモリが別の場所に再割り当てされたりする可能性があるためです（これはC++のイテレータ無効化と同じ問題です）。

上記の2つの単純なルールは記憶しやすく、ユーザーコードにポインタをまったく公開しないことと、すべてのメモリアクセスに対して（いくらかコストのかかる）ハンドルからポインタへの変換を行うこととの間で良い妥協点となります。

メモリ安全性に関する考慮事項

まず、各タイプのハンドルには独自のC/C++型を取得する必要があります。これにより、間違ったハンドルタイプを関数に渡そうとすると、コンパイル時に検出されます（単純なtypedefではコンパイラ警告は生成されません。ハンドルは独自の構造体またはクラスにラップする必要があります。ただし、これはデバッグコンパイルモードに限定される場合があります）。

すべての実行時メモリ安全性チェックは、ハンドルをポインタに変換する関数で行われます。ハンドルが単なる配列インデックスの場合、次のようになります。

• インデックスと現在のアイテム配列サイズとの間で範囲チェックが行われます。これにより、セグメンタルトラブルや、割り当て済みだが無関係なメモリ領域の読み書きを防ぎます。
• インデックスされた配列アイテムスロットにアクティブなアイテムが含まれているか（現在「空きスロット」ではないか）を確認する必要があります。これにより、「解放後使用」の単純なバリアントを防ぎます。
• 最後に、アイテムポインタがプライベート配列ベースポインタと公開アイテムインデックスから計算されます。

結果のポインタは、次の限り安全に使用できます。

• アイテム配列が再割り当てされない。
• インデックスされたアイテムが破棄されていない。

これらはどちらもシステム内の関数内でのみ発生するため、2つの「ポインタ使用ルール」が存在します（ポインタを保存しない、関数呼び出しをまたいでポインタを保持しない）。

上記の解放後使用チェックには、かなり大きな穴があります。配列スロットがハンドルインデックスの後ろにあるかどうかだけをチェックした場合、ハンドルが最初に作成されたのと同じアイテムであるとは限りません。元のアイテムが破棄され、同じ配列スロットが新しいアイテムのために再利用される可能性があります。

ここでハンドルの「空きビット」が登場します。たとえば、ハンドルが16ビットだとしましょう。しかし、同時に1024個のアイテムしか必要ない場合。1024個のアイテムをアドレス指定するには10ビットのインデックスしか必要なく、残りの6ビットは何かに使用できます。

これらの6ビットに何らかの「ユニークなパターン」が含まれている場合、ダングリングアクセスを検出できます。

• アイテムが作成されると、空き配列アイテムが選択され、そのインデックスが下位10ビットのハンドルに配置されます。上位6ビットは「ユニークビットパターン」に設定されます。
• 結果の16ビットハンドル（10ビットインデックス+6ビット「ユニークパターン」）が外部に返され、同時に配列スロットに保存されます。
• アイテムが破棄されると、配列スロットに保存されているアイテムハンドルは「無効なハンドル」値に設定されます（ゼロが外部に有効なハンドルとして返されない限り、ゼロでも構いません）。
• ハンドルがポインタに変換されるとき、下位10ビットが配列インデックスとして使用され、配列スロットをルックアップし、ハンドル全体が現在配列スロットに保存されているハンドルと比較されます。
  • 両方のハンドルが等しい場合、ポインタは有効であり、ハンドルが作成されたのと同じアイテムを指しています。
  • それ以外の場合はダングリングアクセスです。スロットアイテムは破棄された（その場合、保存されているハンドルは「無効なハンドル」値になります）、または破棄されて新しいアイテムのために再利用された（その場合、上位6ビットの「ユニークパターン」が一致しません）かのいずれかです。

ポインタにハンドルを変換する際のこのハンドル比較チェックは、ダングリングアクセスを検出するのに非常にうまく機能しますが、配列インデックスと「ユニークパターン」の同じ組み合わせが遅かれ早かれ作成される可能性があるため、完全ではありません。しかし、それでも保護がない（生のポインタのような）場合や、スマートポインタの場合に同様の状況で発生する「偽のメモリリーク」よりも優れています。

ユニークなハンドルを衝突が可能な限り少なく作成するための良い戦略を見つけることが、もちろん最も重要な部分であり、読者の演習として残されています ;P

明らかに、ユニークパターンにできるだけ多くのビットを使用することが良いことです。また、空き配列スロットの再利用方法も重要です（例: LIFO対FIFO）。作成/破棄のストレステストを少し書いて、ハンドルの衝突をチェックし、特定のユースケースに合わせてユニークパターンの作成を調整できるようにするのも良いでしょう。アイテムの作成と破棄が非常に頻繁に行われるシステムは、アイテムの作成と破棄がまれなシステムよりも多くの労力（または単に多くのハンドルビット）を必要とします。

ハンドルのその他の有用なプロパティ

メモリ安全性という側面全体 apart from、ハンドルはポインタが問題となる他の状況でも役立ちます。

ハンドルは、プロセス間で共有オブジェクト識別子として使用できます（必要なのは「create_item_with_handle()」のような関数で、新しいハンドルを作成するのではなく、既存のハンドルを入力引数として受け取ります）。これは、オンラインゲームでハンドルがサーバーとゲームセッション内のすべてのクライアント間で共有できる場合や、セーブゲームシステムで他のオブジェクトへの参照を保存する場合に特に役立ちます。

場合によっては、関連するアイテムのグループ全体（たとえば、アニメーションキーとカーブ）を作成し、単一のハンドルでアイテムグループ全体を参照するのが便利です。その場合、「範囲ハンドル」のようなものを使用できます。これは、インデックス（最初のアイテムの）だけでなく、範囲内のアイテム数も含まれます。

状況によっては、静的型チェックがコンパイル時に十分でない場合に、アイテムタイプのためにいくつかのハンドルビットを予約するのが役立つこともあります。

結論として、ハンドルが従来の「ヒープ上のオブジェクトへのポインタ」モデルで過去に遭遇した多くの問題を、どれほど自然かつエレガントに解決するか、そしてこのモデル（およびそれに基づいて構築されたC++の部分）を今どれほどほとんど恋しく思わないかに驚いています。

いくつかの実例

sokol-gfx APIは、レンダリングリソースオブジェクト（バッファ、画像、シェーダーなど）のポインタの代わりにハンドルを使用するC APIの例です。

sokol_gfx.h

Oryol Gfxモジュールは同様の3D APIラッパーですが、C++で書かれています。

Oryol Gfx Module

Oryol Animation拡張モジュールは、すべてのデータを配列に保持するキャラクターアニメーションシステムです。

Oryol Anim Module

更新 2018年11月28日

…上記の投稿では、同じスロットに対して同じユニークタグを2回作成するという問題を手際よく回避していましたが、Twitterで親切な人が、非常にシンプルでエレガントで、当惑するほど「明白」な解決策を教えてくれました。

各配列スロットには独自の世代カウンタがあり、ハンドルが解放されるときにインクリメントされます（ハンドルが作成されるときにインクリメントすることもできますが、解放時にインクリメントすると、無効なハンドルを検出するために「空きスロット」の予約値が不要になります）。

ハンドルが有効かどうかを確認するには、そのユニークタグをスロットの現在の世代カウンタと比較するだけです。

世代カウンタが「オーバーフロー」したら、その配列スロットを無効にし、そのスロットに対して新しいハンドルが返されないようにします。

これはハンドルの衝突を回避するための完璧な解決策ですが、すべての配列スロットがいずれ無効になるため、ハンドルはいずれ枯渇します。しかし、各スロットには独自のカウンタがあるため、これはすべてのハンドルビットが枯渇した後でのみ発生し、ユニークタグビットの一部だけではありません。

したがって、32ビットハンドルを使用すると、常に40億個のアイテムを作成でき、同時に最大2^(32 - num_counter_bits)個のアイテムがアクティブになります。これは、ハンドルの安全性を損なうことなく、ユニークタグに使用できるビット数を減らすことができることも意味します。

無効になったスロットからハンドルがもうワイルドに存在しないことが保証されたときに、それらを再アクティブ化することも可能かもしれません（おそらく、レベルの出入りなど、コードの特別な場所で）。