タグ付きポインター

コンピュータサイエンスにおいて、タグ付きポインタとは、間接参照ビットや参照カウントなどの追加データが関連付けられたポインタ（具体的にはメモリ アドレス）のことです。この追加データは、メモリ アドレス指定の特定の特性を利用して、アドレスを表すデータの中にインラインで格納される、つまりポインタに「折り込まれる」ことがよくあります。この名前は、各ワードの重要性を示すためにハードウェア レベルでビットを予約する「タグ アーキテクチャ」システムに由来しています。追加データは「タグ」または「タグ群」と呼ばれますが、厳密に言えば「タグ」は型を指定するデータを指し、他のデータを指すものではありません。しかし、「タグ付きポインタ」という用法は広く使われています。

タグをポインタに折り畳むためのさまざまな手法があります。^{[ 1 ]}

ほとんどのアーキテクチャはバイト単位でアドレス指定可能ですが（アドレス指定可能な最小単位はバイト）、特定の種類のデータはデータのサイズ（多くの場合、ワードまたはその倍数）に合わせてアラインされることがよくあります。この不一致により、ポインタの最下位ビットの一部が未使用のまま残ります。これらのビットは、ポインタを使用するコードがメモリにアクセスする前にこれらのビットをマスクする限り、タグとして使用できます（多くの場合、ビットフィールド（各ビットが個別のタグ）として）。たとえば、 32ビットアーキテクチャ（アドレスとワードサイズの両方）では、ワードは32ビット＝4バイトなので、ワードアラインされたアドレスは常に4の倍数となり、末尾は00で終わり、最後の2ビットが使用可能になります。一方、64ビットアーキテクチャでは、ワードは64ビット＝8バイトなので、ワードアラインされたアドレスは末尾が000で終わり、最後の3ビットが使用可能になります。データがワードサイズの倍数でアラインされている場合は、さらに多くのビットが使用可能になります。ワードアドレス指定可能なアーキテクチャの場合、ワードアラインされたデータはアラインメントとアドレッシングの間に不一致がないため、使用可能なビットは残らないが、ワードサイズの倍数でアラインされたデータは残らない。

逆に、一部のオペレーティングシステムでは、仮想アドレスがアーキテクチャ全体の幅よりも狭いため、最上位ビットがタグに使用できます。これは、アラインメントされたアドレスの場合に、前述の手法と組み合わせることができます。これは特に 64 ビット アーキテクチャの場合に当てはまります。64 ビットのアドレス空間は、最大規模のアプリケーションを除くすべてのアプリケーションのデータ要件をはるかに超えているため、多くの実用的な 64 ビット プロセッサは、より狭いアドレスを持っています。仮想アドレスの幅は物理アドレスの幅よりも狭くなる可能性があり、物理アドレスの幅はアーキテクチャの幅よりも狭くなる可能性があることに注意してください。ユーザー空間でのポインタのタグ付けの場合、オペレーティングシステムによって提供される仮想アドレス空間 (さらにメモリ管理ユニットによって提供される) が関連する幅になります。実際、一部のプロセッサでは、プロセッサ レベルでこのようなタグ付きポインタの使用を明示的に禁止しています。特にx86-64では、オペレーティングシステムが最上位ビットがすべて 0 またはすべて 1 の正規形式のアドレスを使用することが求められます。

最後に、最新のオペレーティングシステムのほとんどでは、仮想メモリシステムがアドレス0周辺の論理メモリ領域を使用不可領域として確保しています。つまり、例えば0へのポインタは決して有効なポインタではなく、特殊なヌルポインタ値として使用できます。前述の手法とは異なり、この方法では単一の特殊なポインタ値のみが許可され、ポインタ全般に追加のデータを持たせることはできません。

商用プラットフォームにおけるタグ付きポインタのハードウェアサポートの初期の例の 1 つはIBM System/38でした。^{[ 2 ]} IBM は後にPowerPCアーキテクチャにタグ付きポインタのサポートを追加し、System/38 プラットフォームの進化形であるIBM iオペレーティングシステムをサポートしました。 ^{[ 3 ]}

タグ付きポインタの使用例として重要なのが、iOS 7 on ARM64のObjective-Cランタイムで、特にiPhone 5Sで使用されています。iOS 7 では、仮想アドレスには 33 ビットのアドレス情報しか含まれていませんが、64 ビット長なので、タグ用に 31 ビットが残ります。Objective-C クラスポインタは 8 バイト境界にアラインされているため、さらに 3 ビットのアドレス空間が解放され、タグ フィールドは参照カウントの格納やオブジェクトにデストラクタがあるかどうかなど、さまざまな目的で使用されます。^{[ 4 ] [ 5 ]}

macOSの初期バージョンでは、データオブジェクトへの参照を格納するためにハンドルと呼ばれるタグ付きアドレスが使用されていました。アドレスの上位ビットは、データオブジェクトがロックされているか、削除可能であるか、リソースファイルから生成されたかを示していました。これは、macOSのアドレス指定がSystem 7で24ビットから32ビットに進んだときに互換性の問題を引き起こしました。^{[ 6 ]}

ヌルポインタを表すのにゼロを使用することは非常に一般的で、多くのプログラミング言語（ Adaなど）はこの動作を明示的に採用しています。理論的には、オペレーティングシステムが予約した論理メモリブロック内の他の値をヌルポインタ以外の条件を示すために使用することもできますが、これらの使用例はまれです。おそらく、移植性が低いことが理由でしょう。ソフトウェア設計においては、ヌルとは異なる特別なポインタ値（特定のデータ構造における番兵など）が必要な場合は、プログラマが明示的に指定するのが一般的です。

ポインタのアライメントを利用することで、ヌルポインタやヌル番兵よりも柔軟性が高まります。なぜなら、ポインタに、指し示すデータの型、アクセス可能な条件、またはポインタの使用に関するその他の同様の情報をタグ付けできるからです。この情報は、有効なポインタすべてに付加できます。一方、ヌルポインタやヌル番兵は、有効なポインタとは異なる、限られた数のタグ付き値しか提供しません。

タグ付きアーキテクチャでは、メモリの各ワードにタグとして機能するためのビットが一定数予約されています。Lispマシンなどのタグ付きアーキテクチャは、タグ付きポインタの解釈と処理のためのハードウェアサポートを備えていることがよくあります。

GNU libc はmalloc()、32 ビット プラットフォームでは 8 バイト整列メモリ アドレスを、64 ビット プラットフォームでは 16 バイト整列を提供します。^{[ 7 ]}より大きな整列値は、で取得できますposix_memalign()。^{[ 8 ]}

タグ付きポインタの最大の利点は、タグフィールドを別途持つポインタよりも占有スペースが少ないことです。これは、ポインタが関数の戻り値である場合に特に重要です。また、大規模なポインタテーブルにおいても重要となります。

より微妙な利点としては、ポインタと同じ場所にタグを格納することで、外部同期メカニズムを使用せずに、ポインタとそのタグの両方を更新する操作の原子性を保証できる場合が多いことが挙げられます。 これは、特にオペレーティングシステムにおいて、非常に大きなパフォーマンス向上につながります。

タグ付きポインタは、XOR連結リストと同様の難点をいくつか抱えていますが、その程度はより軽微です。例えば、すべてのデバッガがタグ付きポインタを正しく追跡できるとは限りません。しかし、タグ付きポインタを念頭に置いて設計されたデバッガであれば、これは問題になりません。

ヌルポインタを表すのにゼロを使用する方法は、以下のような欠点はありません。ゼロは広く普及しており、ほとんどのプログラミング言語で特別なヌル値として扱われ、その堅牢性は十分に実証されています。例外は、 C++におけるオーバーロード解決におけるゼロの扱い方です。C++ではゼロはポインタではなく整数として扱われるため、整数ゼロよりも特殊値nullptrが好まれます。ただし、タグ付きポインタの場合、ヌルポインタを表すのにゼロは通常使用されません。