Haskell や Go などの自動ガベージ コレクションを備えた言語では、ガベージ コレクタは、スタックに保存されている値がメモリへのポインターであり、単なる数値であるとどのように判断できるのでしょうか? ガベージ コレクターがスタックをスキャンするだけで、すべてのアドレスがオブジェクトへの参照であると想定すると、多くのオブジェクトが到達可能として誤ってマークされる可能性があります。
明らかに、次の値のうちいくつがポインターであるかを示す値を各スタック フレームの先頭に追加できますが、それではパフォーマンスが大幅に低下するのではないでしょうか?
実際にはどのように行われますか？
一部のコレクターは、スタック上のすべてが潜在的なポインターであると想定しています (Boehm GC など)。これは、予想されるほど悪くはありませんが、明らかに最適ではありません。多くの場合、マネージ言語では、追加のタグ付け情報がスタックに残され、コレクターがポインターの場所を把握するのに役立ちます。
ほとんどのコンパイル済み言語では、関数を入力するたびにスタック フレームのレイアウトが同じであるため、データに正しい方法でタグ付けすることはそれほど難しくありません。
「ビットマップ」アプローチは、これを行う 1 つの方法です。ビットマップの各ビットは、スタック上の 1 つのワードに対応します。ビットが 1 の場合、スタック上の位置はポインターであり、0 の場合、位置はコレクター (またはそれらの線に沿ったもの) の観点からの単なる数値です。非常によく書かれた GHC ランタイムと呼び出し規則は、ほとんどの関数に 1 ワードのレイアウトを使用します。たとえば、数ビットがスタック フレームのサイズを伝達し、残りがビットマップとして機能します。より大きなスタック フレームには複数ワード構造が必要ですが、考え方は同じです。
ポイントは、レイアウト情報がコンパイル時に計算され、関数が呼び出されるたびにスタックに含まれるため、オーバーヘッドが低いことです。
さらに単純なアプローチは、すべてのポインターがスタックの先頭に配置される「ポインター ファースト」です。ポインターの前に長さを含めるか、ポインターの後に特別な「終了」単語を含めるだけで、このレイアウトでどの単語がポインターであるかがわかります。
興味深いことに、この管理情報をスタックに取得しようとすると、C との相互運用性に関連する多くの問題が発生します。たとえば、C は移植可能ですが、持ち運びが難しいため、高水準言語を C にコンパイルすることは最適ではありません。この種の情報。C のような言語 (GCC、LLVM) 用に設計されたコンパイラを最適化すると、スタック フレームが再構築されて問題が発生する可能性があるため、GHC LLVM バックエンドは、LLVM スタックではなく独自の「スタック」を使用するため、最適化のコストがかかります。同様に、C コードと「マネージ」コードの間の境界は、GC を混乱させないように慎重に構築する必要があります。
このため、JVM で新しいスレッドを作成すると、実際には 2 つのスタック (Java 用と C 用) が作成されます。
Haskell スタックは、各スタック フレーム内の単一のメモリ ワードを使用して、そのスタック フレーム内のどの値がポインターであり、どれがポインターでないかを (ビットマップで) 記述します。詳細については、GHC Commentaryの「スタックのレイアウト」記事と「ビットマップ レイアウト」記事を参照してください。
公平を期すために言えば、すべてのことを考慮すると、記憶の 1 語のコストはそれほど高くありません。各メソッドに 1 つの変数を追加するだけと考えることができます。それは悪いことではありません。
GC が管理している何かのアドレスであるすべてのビット パターンが実際にはポインターであると仮定する GC が存在します (したがって、何かを解放しません)。通常、呼び出しポインタは小さな共通整数よりも大きく、通常は整列する必要があるため、これは実際にはかなりうまく機能します。ただし、これにより、一部のオブジェクトの収集が遅れる可能性があります。C の Boehm コレクターはこのように動作します。これは、ライブラリ ベースであり、コンパイラから特定のヘルプを得られないためです。
また、GC が使用されている言語とより緊密に結合されており、メモリ内のオブジェクトの構造を実際に認識している GC もあります。特にスタック フレームの処理について読んだことはありませんが、コンパイラと GC が連携して動作するように設計されている場合は、GC に役立つ情報を記録できます。トリックの 1 つは、すべてのポインター参照をまとめて、スタック フレームごとに 1 ワードを使用してその数を記録することですが、これはそれほど大きなオーバーヘッドではありません。言葉を追加せずに各スタック フレームに対応する関数を特定できる場合は、関数ごとの「スタック フレーム レイアウト マップ」をコンパイルすることができます。 1 へのポインターではない単語の順序ビット。これは (アドレス アラインメントのために) ポインターには必要ないため、それらを区別することができます。