19

私は「なぜそれがそのように機能するのですか？」ガベージ コレクションに関する質問 (任意/すべての実装: Java、Python、CLR など)。ガベージ コレクターは、オブジェクトがスコープ内に存在しなくなったときにそのオブジェクトの割り当てを解除します。それを指している参照の数はゼロです。フレームワークは、参照の数がゼロになるとすぐに割り当てを解除できるように思えますが、私が遭遇したすべての実装は、しばらく待ってから、一度に多くのオブジェクトの割り当てを解除します。私の質問は、なぜですか？

私は、フレームワークが各オブジェクトの整数を保持していると仮定しています (Python はそうしていると思います。C で拡張モジュールを呼び出す必要があるためです。おそらく、これらの関数は実際のカウンターをどこかで変更します) PyINCREF。PyDECREFもしそうなら、オブジェクトが範囲外になった瞬間にオブジェクトを削除するのにこれ以上 CPU 時間がかかるべきではありません。オブジェクトごとに x ナノ秒かかる場合、後でオブジェクトごとに x ナノ秒かかりますよね?

私の仮定が間違っていて、各オブジェクトに整数が関連付けられていない場合、ガベージ コレクションが待機する理由が理解できます。各オブジェクトの状態を判断するには、参照のグラフをたどる必要があり、その計算には時間がかかります。このような方法は、明示的な参照カウント方法よりも消費するメモリが少なくなりますが、それがより高速であるか、他の理由で推奨される方法であることに驚いています。大変な作業のように聞こえます。

プログラミングの観点からは、オブジェクトがスコープ外になった直後に割り当てが解除されると便利です。デストラクタが必要なときに実行されることに依存できるだけでなく (Python の落とし穴の 1 つは__del__、予測可能な時間に呼び出されないことです)、プログラムのメモリ プロファイリングがはるかに簡単になります。 これがどれだけの混乱を引き起こすかの例を次に示します。私の考えでは、割り当てをすぐに解除するフレームワークでプログラミングする利点は非常に大きいので、私が聞いたすべての実装が割り当てを解除する前に待機するのには、何らかの正当な理由があるに違いありません。そのメリットとは？

注: 循環参照を識別するためだけに参照のグラフをたどる必要がある場合 (純粋な参照カウントはできない)、ハイブリッド アプローチではないのはなぜですか? 参照カウントがゼロになるとすぐにオブジェクトの割り当てを解除し、定期的にスイープを行って循環参照を探します。このようなフレームワークで作業するプログラマーは、可能な限り非循環参照に固執するパフォーマンス/決定論の理由があります。多くの場合、実現可能です (たとえば、すべてのデータが、親へのポインターを持たない JSON オブジェクトの形式になっている場合)。これは、一般的なガベージコレクターの仕組みですか?

4

7 に答える 7

34

まず、用語のポイント: 「ガベージ コレクション」は人によって意味が異なり、GC スキームの中には他のものよりも洗練されたものもあります。参照カウントを GC の一種と考える人もいますが、個人的には「真の GC」は参照カウントとは別物だと考えています。

refcounts を使用すると、参照数を追跡する整数があり、refcount がゼロになるとすぐに割り当て解除をトリガーできます。これは、CPython 実装がどのように機能するか、およびほとんどの種類の C++ スマート ポインターがどのように機能するかを示しています。CPython の実装では、バックアップとしてマーク/スイープ GC が追加されるため、説明したハイブリッド設計に非常によく似ています。

しかし、参照が渡されるたびに (比較的) 高価なメモリ書き込み (さらに、スレッドの安全性を確保するためのメモリ バリアやロック) が発生するため、参照カウントは実際には非常にひどいソリューションです。C++ のような命令型言語では、マクロとコーディング規則を使用してメモリの所有権を管理することは可能ですが (難しいだけです)、Lisp のような関数型言語では、通常、クロージャでのローカル変数のキャプチャにより暗黙的にメモリ割り当てが行われるため、ほぼ不可能になります。

したがって、最新の GC への第一歩が Lisp のために発明されたとしても、驚くべきことではありません。これは「twospace アロケーター」または「twospace コレクター」と呼ばれ、その名の通り正確に機能しました。つまり、割り当て可能なメモリ (「ヒープ」) を 2 つのスペースに分割しました。すべての新しいオブジェクトは最初のスペースから割り当てられ、いっぱいになると割り当てが停止し、ランタイムは参照グラフをたどり、ライブ (まだ参照されている) オブジェクトのみを 2 番目のスペースにコピーします。ライブ オブジェクトがコピーされた後、最初のスペースは空としてマークされ、割り当てが再開され、2 番目のスペースから新しいオブジェクトが割り当てられます。満杯になった時点で、ライブ オブジェクトは最初のスペースにコピーされ、プロセスは最初からやり直します。

twospace コレクターの利点は、O(N)作業を行う代わりに ( Nはガベージ オブジェクトの総数)、O(M)作業のみを行うことです ( Mはガベージオブジェクトの数) 。実際には、ほとんどのオブジェクトは短時間で割り当てられてから割り当て解除されるため、これによりパフォーマンスが大幅に向上する可能性があります。

さらに、twospace コレクターにより、アロケーター側も単純化できました。ほとんどのmalloc()実装では、「空きリスト」と呼ばれるものを保持しています。これは、まだ割り当て可能なブロックのリストです。新しいオブジェクトを割り当てるにはmalloc()、フリー リストをスキャンして、十分な大きさの空き領域を探す必要があります。しかし、twospace アロケータはそれを気にしませんでした。必要なバイト数だけポインタを押し上げるだけで、スタックのように各スペースにオブジェクトを割り当てただけです。

したがって、twospace コレクターは よりもはるかに高速でした。Lispmalloc()プログラムは C プログラムよりも多くの割り当てを行うため、これは素晴らしいことでした。別の言い方をすれば、Lisp プログラムはスタックのようにメモリを割り当てる方法を必要としていましたが、有効期間は実行スタックに制限されていませんでした。つまり、プログラムがメモリを使い果たすことなく無限に成長できるスタックです。 . 実際、Raymond Chen は、GC について人々はまさにそのように考えるべきだと主張しています。ガベージ コレクションについて誰もが間違った方法で考えているという彼の一連のブログ投稿を強くお勧めします。

しかし、twospace コレクターには重大な欠陥がありました。つまり、使用可能な RAM の半分以上を使用できるプログラムはなく、残りの半分は常に無駄になっていたということです。したがって、GC 手法の歴史は、通常、プログラム動作のヒューリスティックを使用して、twospace コレクターを改善しようとする試みの歴史です。ただし、GC アルゴリズムには必然的にトレードオフが伴います。通常は、オブジェクトを個別にではなくバッチで割り当て解除することを好みます。これにより、オブジェクトがすぐに割り当て解除されない場合に必然的に遅延が発生します。

編集:フォローアップの質問に答えるために、最新の GC は一般に世代別ガベージ コレクションのアイデアを取り入れています。オブジェクトは、有効期間に基づいて異なる「世代」にグループ化され、ある世代のオブジェクトは、存続すると別の世代に「昇格」されます。十分な長さ。場合によっては、オブジェクトの有効期間のわずかな違い (たとえば、リクエスト駆動型のサーバーで、1 つのリクエストより長くオブジェクトを格納する場合) が、オブジェクトの割り当てが解除されるまでにかかる時間に大きな違いが生じることがあります。より「終身」。

malloc()真の GC はとのレベルの「下」で動作する必要があることを正しく観察しますfree()。malloc()(ちなみに、とがどのように実装されているかを学ぶ価値free()はあります。それらも魔法ではありません!) さらに、効果的な GC を実現するには、(Boehm GC のように) 保守的であり、オブジェクトを決して移動しないでください。ポインターである可能性があるもの、または何らかの種類の「不透明なポインター」タイプが必要です-JavaおよびC＃は「参照」と呼びます。不透明なポインターは、オブジェクトへのポインターを更新することでいつでもオブジェクトを移動できることを意味するため、実際には割り当てシステムに最適です。生のメモリ アドレスと直接対話する C のような言語では、オブジェクトを移動することは決して安全ではありません。

また、GC アルゴリズムには複数のオプションがあります。標準の Java ランタイムには 5 つ以上のコレクター (Young、Serial、古い CMS、新しい CMS、および G1。1 つ忘れていると思いますが) が含まれており、それぞれにすべて構成可能な一連のオプションがあります。

ただし、GC は魔法ではありません。ほとんどの GC は、バッチ処理の時間と空間のトレードオフを利用しているだけです。つまり、速度の向上は通常、メモリ使用量の増加によって支払われます (手動のメモリ管理や参照カウントと比較して)。しかし、最近の RAM の低コストと比較して、プログラムのパフォーマンスとプログラマーのパフォーマンスの向上の組み合わせは、通常、トレードオフの価値があります。

うまくいけば、それが物事をより明確にするのに役立ちます！

于 2013-07-15T05:03:18.287 に答える
9

ガベージ コレクションを理解するには、ボウリング場に行き、ピンセッターが最初のボールが転がった後に落ちたピンをどのように取り除くかを見てください。ピンセッター メカニズムは、倒れたピンを個々に特定して除去するのではなく、まだ立っているすべてのピンを拾い上げ、安全な場所まで持ち上げてから、そこにあるピンの数や場所に関係なく、レーンを横切ってスイーパー バーを走らせます。 . それが完了すると、立っていたピンがレーンに戻されます。多くのガベージ コレクション システムは、ほぼ同じ原則で動作します。ライブ オブジェクトごとに、それが破棄されないようにするために、かなりの量の作業を行う必要があります。

補遺

ライブ アイテムが多数ある場合、その保存が遅くなる傾向があることを確認するために、常にすべてのライブ アイテムに対して動作する必要があるガベージ コレクター。これが、ガベージ コレクターが歴史的に悪い評判を得てきた理由です。Commodore 64 の BASIC インタープリター (ちなみに、 MS-DOS の前にMicrosoft によって作成されたもの) は、数百の文字列の配列を持つプログラムでガベージ コレクションを実行するのに何秒もかかりました。多くのアイテムが最初のガベージ コレクションを生き残るまで、最初のガベージ コレクションを生き延びたアイテムを無視できる場合、パフォーマンスは大幅に改善されます。および 2 つのガベージ コレクションを生き残った (他の多くのオブジェクトが最初のコレクションに参加するまで、2 番目のコレクションに参加する必要はないことに注意してください) は、他の多くのオブジェクトも参加して 2 回目のコレクションに参加し、生き残るまで無視できます。この概念は部分的に簡単に実装できます (Commodore 64 でも、特定の時点で存在するすべての文字列を将来のガベージ コレクションから除外するように強制できます。変更) ですが、ハードウェア サポートを少し追加することでより強力になります。

ガベージ コレクターが、保持されるオブジェクトを可能な限りメモリの最後に近づけようとする場合、世代のサポートには、どの (連続した) 範囲のメモリが使用されているかを追跡する以外に何もする必要はありません。各世代のオブジェクトによって。すべての世代のすべてのオブジェクトをスキャンして、すべての新しい世代の生きているオブジェクトを見つけて保存する必要がありますが、古い世代のオブジェクトは移動する必要はありません。これは、それらが占有するメモリが完全に削除される危険がないためです。このアプローチは実装が非常に簡単で、非世代 GC に比べてパフォーマンスが大幅に向上しますが、多くのライブ オブジェクトがある場合、GC のスキャン フェーズでさえコストがかかる可能性があります。

「新しい世代」のガベージ コレクションを高速化するための鍵は、オブジェクト「Fred」が、参加した最後のガベージ コレクション以降に書き込まれていない場合、そのオブジェクトが以前に作成されたオブジェクトへの参照を含むことができないことを観察することです。その時から作成されています。したがって、参照を保持しているオブジェクトは、Fred 自体が削除の対象となるまで、削除の危険にさらされることはありません。もちろん、最後の下位レベル GC 以降に新しいオブジェクトへの参照が Fred に格納されている場合、それらの参照をスキャンする必要があります。これを実現するために、高度なガベージ コレクターは、古い世代のヒープの一部が書き込まれたときに起動するハードウェア トラップを設定します。このようなトラップが発生すると、その領域内のオブジェクトが、スキャンが必要な古い世代のオブジェクトのリストに追加されます。次に、その領域に関連付けられたトラップを無効にします。古い世代のオブジェクトが新しいオブジェクトへの参照を格納していることが多い場合、この余分な簿記はパフォーマンスを低下させる可能性がありますが、ほとんどの場合、最終的にはパフォーマンスが大幅に向上します。

于 2013-07-16T17:04:44.627 に答える
6

あなたの考えは一般的に非常に洞察力に富み、よく考えられています。基本的な情報が不足しているだけです。

ガベージ コレクターは、オブジェクトがスコープから外れたときにオブジェクトの割り当てを解除します。

それは一般的に完全に間違っています。ガベージ コレクターは、実行時にスコープの概念が取り除かれた表現で動作します。たとえば、ライブネス分析のインライン化とアプリケーションはスコープを破壊します。

トレース ガベージ コレクタは、最後の参照が消えた後、ある時点でスペースをリサイクルします。活性分析では、変数がまだスコープ内にある場合でも、スタック フレーム内の参照が他の参照で上書きされる可能性があります。これは、活性分析によって、変数が二度と使用されないため、必要がなくなったと判断されたためです。

フレームワークは、参照の数がゼロになるとすぐに割り当てを解除できるように思えますが、私が遭遇したすべての実装は、しばらく待ってから、一度に多くのオブジェクトの割り当てを解除します。私の質問は、なぜですか？

パフォーマンス。スタック エントリとレジスタのレベルでカウントを参照できますが、パフォーマンスはまったくひどいものです。すべての実用的な参照カウント ガベージ コレクターは、妥当な (ただしまだ悪い) パフォーマンスを達成するために、カウンターのデクリメントをスコープの最後まで延期します。最先端の参照カウント ガベージ コレクターはデクリメントを延期してバッチ処理を行い、競争力のあるパフォーマンスを達成できると言われています。

フレームワークが各オブジェクトの整数を保持していると仮定しています

必ずしも。たとえば、OCaml は単一のビットを使用します。

プログラミングの観点からは、オブジェクトがスコープ外になった直後に割り当てが解除されると便利です。

プログラミングの観点からは、コードが楽に 10 倍高速に実行されるとよいでしょう。

デストラクタは、関数型プログラミングで非常に重要な末尾呼び出しの削除を禁止することに注意してください。

それがより速いか、または他の理由で推奨される方法であることに驚いています。大変な作業のように聞こえます。

チェス盤の座標のリストを操作して n-queens 問題を解くプログラムを考えてみましょう。入力は単一の整数です。出力は、いくつかのボード座標を含むリストです。中間データは、リンクされたリスト ノードの巨大なスパゲッティ スタックです。リンクされたリストノードの十分な大きさのスタックを事前に割り当て、それらを操作して答えを取得し、(小さな) 答えをコピーしてから、freeスタック全体で 1 回呼び出すことでこれをコード化した場合、ほとんど同じことを行うことになります。世代別ガベージコレクタが行うこと。特に、データの最大 6% のみをコピーし、残りの最大 94% を 1 回の呼び出しで割り当て解除しますfree。

これは、「ほとんどのオブジェクトは若くして消滅し、古いオブジェクトが新しいオブジェクトを参照することはめったにない」という仮説に固執する世代別ガベージ コレクターにとって、完璧なハッピー デイ シナリオでした。世代別ガベージ コレクターが苦戦する病理学的反例は、新たに割り当てられたオブジェクトでハッシュ テーブルを埋めることです。ハッシュテーブルの背骨は生き残る大きな配列なので古い世代になります。それに挿入されたすべての新しいオブジェクトは、古い世代から新しい世代へのバックポインターです。すべての新しいオブジェクトは生き残ります。そのため、世代別ガベージ コレクターはすばやく割り当てますが、すべてをマークし、すべてをコピーし、すべてへのポインターを更新するため、単純な C または C++ ソリューションよりも約 3 倍遅くなります。

デストラクタが必要なときに実行されることに依存できるだけでなく (Python の落とし穴の 1 つは、予測可能な時間にdelが呼び出されないことです)、プログラムのメモリ プロファイリングがはるかに簡単になります。

デストラクタとガベージ コレクションは直交する概念であることに注意してください。たとえば、.NET は .NET の形式でデストラクタを提供しますIDisposable。

FWIW、ガベージコレクションされた言語を約15年間使用して、メモリプロファイリングをおそらく3回使用しました。

なぜハイブリッドアプローチではないのですか？参照カウントがゼロになるとすぐにオブジェクトの割り当てを解除し、定期的にスイープを行って循環参照を探します。このようなフレームワークで作業するプログラマーは、可能な限り非循環参照に固執するパフォーマンス/決定論の理由があります。多くの場合、実現可能です (たとえば、すべてのデータが、親へのポインターを持たない JSON オブジェクトの形式になっている場合)。これは、一般的なガベージコレクターの仕組みですか?

CPython はそれを行っていると思います。Mathematica と Erlang は設計上、ヒープを DAG に制限しているため、参照カウントのみを使用できます。GC 研究者は、サイクルを検出するための補助アルゴリズムとして試行削除などの関連手法を提案しています。

また、パフォーマンスが (ライブ) ヒープのサイズに依存しないため、参照カウントはガベージ コレクションのトレースよりも理論的には漸近的に高速であることに注意してください。実際には、ガベージ コレクションのトレースは、100GB のヒープを使用してもはるかに高速です。

于 2015-04-30T11:25:02.253 に答える
0

@ジムはかなりの数に答えました。さらに追加します。

0まず、カウントが終了したらすぐに [A1] の割り当てを解除することが良い代替手段であると考える理由は何ですか?

ガベージ コレクターは、オブジェクトの割り当てを解除するだけでなく、完全なメモリ管理を担当します。から始まり、fragmentationガベージ コレクターの最大の問題の 1 つです。適切に行わないと、不要なページ ヒットやキャッシュ ミスが発生します。ガベージ コレクターは、最初からこの問題を処理するように設計されています。世代が異なると、これを処理しやすくなります。ではA[1]、定期的にスレッドをセットアップして処理する必要があります。

さらに、複数のオブジェクトをクリアする方が、 のようにするよりも高速であることがわかりますA[1]。(考えてみてください、砂が敷き詰められた部屋の場合、それらを個別に拾うよりも、すべてまとめてクリアする方が高速です)

第 2 に、マルチスレッド システムでのスレッド セーフのために、すべてのオブジェクトのロックを保持してカウントを増減する必要があります。これは、パフォーマンスの低下とメモリの増加につながります。さらに、最新のコレクターには、停止ではなく並行して実行する機能があります。 The World (例: Java の ParallelGC)、これがA[1].

于 2013-07-15T06:42:27.017 に答える
0

参照カウントを使用したガベージ コレクションは、特にスレッド化された環境では非常に遅くなります。

ブライアン・ハリーによるこの投稿を本当にお勧めします。

私を納得させるのに十分なコードサンプルがそこに提供されています（C＃）：

public interface IRefCounted : IDisposable
{
        void AddRef();
}

// ref counted base class.
class RefCountable : IRefCountable
{
        private m_ref;
        public RefCountable()
        {
                m_ref = 1;
        }
        public void AddRef()
        {
                Interlocked.Increment(ref m_ref);
        }
        public void Dispose()
        {
                if (Interlocked.Decrement(ref m_ref) == 0)
                        OnFinalDispose();
        }
        protected virtual void OnFinalDispose()
        {
        }
}

Interlocked.Increment(ref m_ref)は、数百回のメモリ サイクルを必要とするアトミック操作です。

于 2015-04-30T11:38:29.763 に答える