Loading article…
コンピュータ科学において、ガベージコレクション（GC）は自動メモリ管理の一形態である。[ 2 ]ガベージコレクタは、プログラムによって割り当てられたが、もはや参照されていないメモリを回収しようとする。このようなメモリはガベージと呼ばれる。ガベージコレクションは、 Lispでの手動メモリ管理を簡素化するために、1959 年頃にアメリカのコンピュータ科学者ジョン・マッカーシーによって考案された。[ 3 ]
ガベージコレクションは、プログラマがメモリシステムに解放して戻すオブジェクトとそのタイミングを指定する手動のメモリ管理からプログラマを解放します。 [ 2 ]他の同様の手法には、スタック割り当て、領域推論、メモリ所有権、およびそれらの組み合わせがあります。ガベージコレクションはプログラムの総処理時間の大部分を占める可能性があり、結果としてパフォーマンスに影響を与えます。
メモリ以外のリソース（ネットワークソケット、データベースハンドル、ウィンドウ、ファイルディスクリプタ、デバイスディスクリプタなど）は、通常、ガベージコレクションではなく、他の方法（デストラクタなど）によって処理されます。これらの方法の中には、メモリを解放するものもあります。
多くのプログラミング言語では、言語仕様の一部として（RPL、Java、C#、D、[ 4 ] Go、およびほとんどのスクリプト言語など）、または実用的な実装のために（ラムダ計算のような形式言語など）ガベージコレクションが必要です。[ 5 ]これらはガベージコレクション言語と呼ばれます。CやC++などの他の言語は、手動メモリ管理で使用するために設計されましたが、ガベージコレクションの実装が利用可能です。Ada 、Modula-3、C++/CLIなどの一部の言語では、収集されたオブジェクトと手動で管理されるオブジェクトに別々のヒープを使用することで、ガベージコレクションと手動メモリ管理の両方を同じアプリケーションで共存させることができます。Dなどの他の言語では、ガベージコレクションされますが、速度が必要な場合にユーザーがオブジェクトを手動で削除したり、ガベージコレクションを完全に無効にしたりすることができます。[ 6 ]
多くの言語はGCをコンパイラやランタイムシステムに統合しているが、自動参照カウント（ARC）などの事後GCシステムも存在する。これらの事後GCシステムの中には再コンパイルを必要としないものもある。[ 7 ]
GC はプログラマーが手動でメモリを解放するのを不要にします。これにより、いくつかの種類のエラーを回避することができます。[ 8 ]
GC は、どのメモリを解放するかを決定するために計算リソースを使用します。したがって、ソース コードでオブジェクトのライフタイムを手動で注釈しないという利便性に対する代償はオーバーヘッドであり、プログラムのパフォーマンスを低下させる可能性があります。[ 11 ] 2005 年の査読済み論文では、GC はこのオーバーヘッドを補償し、理想化された明示的なメモリ管理を使用する同じプログラムと同じ速度で動作するために 5 倍のメモリを必要とすると結論付けています。ただし、この比較は、プロファイラで実行されたプログラムからトレースを収集して実装されたオラクルを使用して解放呼び出しを挿入して生成されたプログラムに対して行われており、このプログラムは特定の 1 つの実行に対してのみ正しいものです。[ 12 ]メモリ階層効果との相互作用により、このオーバーヘッドは、予測が困難またはルーチン テストで検出が困難な状況では許容できないものになる可能性があります。パフォーマンスへの影響は、最も望まれている機能であるにもかかわらず、iOSでガベージ コレクションを採用しない理由として Apple によって挙げられました。 [ 13 ]
実際にガベージコレクションが行われるタイミングは予測不可能であり、セッション全体にわたってストール（メモリの解放や移動のための一時停止）が発生することがあります。このような予測不可能なストールは、リアルタイム環境、トランザクション処理、または対話型プログラムでは許容できない場合があります。インクリメンタル、コンカレント、リアルタイムのガベージコレクタは、それぞれ異なるトレードオフを持ちながら、これらの問題に対処します。
トレースガベージコレクションは最も一般的なガベージコレクションの種類であり、そのため「ガベージコレクション」は参照カウントなどの他の方法ではなく、トレースガベージコレクションを指すことが多い。全体的な戦略は、特定のルートオブジェクトからの参照チェーンで到達可能なオブジェクトをトレースして、ガベージコレクションするオブジェクトを決定し、残りをガベージとみなして収集することである。[ 14 ]ただし、実装には多数のアルゴリズムが使用されており、複雑さやパフォーマンス特性は大きく異なる。
参照カウント方式のガベージコレクションでは、各オブジェクトは自身への参照数をカウントします。ガベージは参照カウントがゼロであるオブジェクトとして識別されます。オブジェクトの参照カウントは、そのオブジェクトへの参照が作成されると増加し、参照が破棄されると減少します。カウントがゼロになると、オブジェクトのメモリが解放されます。[ 15 ]
手動メモリ管理と同様に、トレースガベージコレクションとは異なり、参照カウントは、オブジェクトが最後の参照が破棄されるとすぐに破棄されることを保証し、通常はCPUキャッシュ内、解放対象のオブジェクト内、またはそれらが直接指すメモリにのみアクセスするため、CPUキャッシュや仮想メモリの動作に大きな悪影響を与えることはありません。
参照カウントにはいくつかの欠点がありますが、これは一般的に、より高度なアルゴリズムによって解決または軽減できます。
const参照を使用して簡単に実装および実証されています。C++ の参照カウントは通常、「スマートポインタ」[ 19 ]を使用して実装され、そのコンストラクタ、デストラクタ、および代入演算子が参照を管理します。スマートポインタは参照によって関数に渡すことができ、新しいスマートポインタをコピー構築する必要がなくなります (これにより、関数に入るときに参照カウントが増加し、関数から出るときに減少します)。代わりに、関数は低コストで生成されるスマートポインタへの参照を受け取ります。Deutsch-Bobrow の参照カウント方式は、ほとんどの参照カウントの更新が実際にはローカル変数に格納されている参照によって生成されるという事実を活用しています。これらの参照は無視され、ヒープ内の参照のみがカウントされますが、参照カウントがゼロのオブジェクトを削除する前に、システムはスタックとレジスタのスキャンで、そのオブジェクトへの他の参照がまだ存在しないことを検証する必要があります。カウンタ更新のオーバーヘッドをさらに大幅に削減するには、Levanoni とPetrankによって導入された更新の統合を使用できます。[ 20 ] [ 21 ]実行の特定の間隔で複数回更新されるポインタを考えます。最初はオブジェクト を指しO1、次にオブジェクト を指しO2、間隔の終わりにオブジェクト を指すまで続きますOn。参照カウント アルゴリズムは通常rc(O1)--、rc(O2)++、rc(O2)--、rc(O3)++、rc(O3)--、 ...を実行しますrc(On)++。しかし、これらの更新のほとんどは冗長です。間隔の終わりに参照カウントを適切に評価するには、rc(O1)--とを実行するだけで十分ですrc(On)++。Levanoni と Petrank は、一般的な Java ベンチマークで、カウンタ更新の 99% 以上が削除されたことを測定しました。エスケープ解析は、コンパイル時にヒープ割り当てをスタック割り当てに変換することで、ガベージコレクションの量を減らすことができる技術です。この解析では、関数内で割り当てられたオブジェクトが関数外からアクセス可能かどうかを判断します。関数ローカル割り当てが別の関数またはスレッドからアクセス可能であることが判明した場合、その割り当ては「エスケープ」したとみなされ、スタック上では実行できません。そうでない場合は、オブジェクトはスタック上に直接割り当てられ、関数が戻るときに解放されるため、ヒープとそれに伴うメモリ管理コストを回避できます。[ 22 ]
一般的に、高水準プログラミング言語はガベージコレクションを標準機能として備えていることが多い。ガベージコレクションが組み込まれていない言語でも、 CやC++のBoehmガベージコレクタのように、ライブラリを通して追加することができる。
ML、Haskell、APLなどのほとんどの関数型プログラミング言語には、ガベージコレクションが組み込まれています。Lispは、最初の関数型プログラミング言語であると同時に、ガベージコレクションを導入した最初の言語としても特に注目に値します。[ 23 ]
RubyやJuliaなどの他の動的言語（ただし、参照カウントを使用するPerl 5やPHPバージョン5.3以前[ 24 ]は除く）、 JavaScript、ECMAScriptもGCを使用する傾向があります。Smalltalk 、ooRexx、RPL、Javaなどのオブジェクト指向プログラミング言語は、通常、統合されたガベージコレクションを提供します。注目すべき例外は、デストラクタを持つC++とDelphiです。
BASICとLogoは、プログラマーにメモリ管理の詳細を負担させないように、文字列やリストなどの可変長データ型にガベージコレクションをよく使用してきました。Altair 8800では、文字列変数が多く文字列領域が少ないプログラムでは、ガベージコレクションのために長い一時停止が発生する可能性がありました。[ 25 ]同様に、Applesoft BASICインタープリタのガベージコレクションアルゴリズムは、文字列記述子を繰り返しスキャンして、最も高いアドレスを持つ文字列を上位メモリに圧縮し、結果として、パフォーマンス[ 26 ]は数秒から数分の一時停止を伴います。[ 27 ] Randy WiggintonによるApplesoft BASIC用の代替ガベージコレクタは、ヒープを走査するたびに文字列のグループを識別し、収集時間を劇的に短縮します。[ 28 ] 1983年にProDOSとともにリリースされたBASIC.SYSTEMは、BASIC用のウィンドウ型ガベージコレクタを提供し、これははるかに高速です。[ 29 ]
C言語はこれまでガベージコレクションを公式にサポートしたことはありません。C ++はC++11で標準ライブラリにガベージコレクションのサポートを追加しましたが、この機能をサポートするコンパイラがなかったため、C++23で削除されました。 [ 30 ]この一部に含まれていた機能はポインタの安全性に関連していました。[ 31 ]
標準ライブラリのガベージコレクションのサポートは削除されましたが、Boehmガベージコレクタ（CおよびC++用）などの一部のガベージコレクタは引き続き使用できます。Boehm GCはトレースガベージコレクションを使用します。メモリ管理は手動のままですが、メモリリークやダブルフリーエラーを検出して報告できるリーク検出モードでも使用できます。その使用はヘッダーから呼び出すことができます<gc.h>。
C++ では、「リソース取得は初期化である」（RAII）イディオムとスマートポインタを使用することで、手動によるオブジェクト破棄を抽象化できます。std::unique_ptrはライフタイムを所有権に結び付け、 はstd::shared_ptr参照カウントを使用してライフタイムを決定します。 を使用するstd::weak_ptrと、参照カウントを増やさずにポインタを取得できます。ガベージコレクションとは異なり、RAII は決定論的です。
Objective-C は従来ガベージコレクションを持っていませんでしたが、 2007 年にOS X 10.5がリリースされると、 Apple は自社開発のランタイムコレクタを使用してObjective-C 2.0にガベージコレクションを導入しました。 [ 32 ]しかし、2012 年にOS X 10.8 がリリースされると、 OS X 10.7で導入されたLLVMの自動参照カウンタ(ARC)に置き換えられ、ガベージコレクションは非推奨になりました。[ 33 ]さらに、2015 年 5 月以降、Apple はApp Storeの新しい OS X アプリケーションでのガベージコレクションの使用を禁止しました。[ 34 ] [ 35 ] iOSでは、アプリケーションの応答性とパフォーマンスの問題からガベージコレクションは導入されていません。[ 13 ] [ 36 ]代わりに iOS は ARC を使用しています。[ 37 ] [ 38 ]
組み込みシステムやリアルタイムシステムでは、限られたリソースの使用を非常に厳密に制御する必要があるため、ガベージコレクションはめったに使用されません。しかし、多くの制限された環境と互換性のあるガベージコレクタが開発されています。 [ 39 ] Microsoft .NET Micro Framework、.NET nanoFramework [ 40 ]、Java Platform, Micro Editionは、より大きなものと同様にガベージコレクションを含む組み込みソフトウェアプラットフォームです。
Java OpenJDKs仮想マシン（JVM）で利用可能なガベージコレクタには、以下のものがあります。
コンパイル時ガベージコレクションは、コンパイル時に判明する不変条件に基づいてメモリを再利用および解放することを可能にする静的解析の一種である。
この形式のガベージコレクションはMercuryプログラミング言語で研究されており、[ 42 ] 2011年にLLVMの自動参照カウンタ（ARC）がAppleのエコシステム（iOSとOS X）に導入されたことで、より広く使用されるようになりました。 [ 37 ] [ 38 ] [ 34 ]
増分型、並行型、リアルタイム型のガベージコレクタが、例えばヘンリー・ベイカーやヘンリー・リーバーマンによって開発されている。[ 43 ] [ 44 ] [ 45 ]
ベイカーのアルゴリズムでは、メモリの単一領域のどちらかの半分に割り当てが行われます。半分いっぱいになると、ガベージコレクションが実行され、生存しているオブジェクトがもう一方の半分に移動され、残りのオブジェクトは暗黙的に解放されます。実行中のプログラム（「ミューテーター」）は、参照するオブジェクトが正しい半分にあるかどうかを確認し、そうでない場合は移動する必要があります。その間、バックグラウンドタスクがすべてのオブジェクトを見つけます。[ 46 ]
世代別ガベージコレクション方式は、ほとんどのオブジェクトが比較的短期間で消滅するという経験的観察に基づいています。世代別ガベージコレクションでは、オブジェクトの経過時間に基づいて分離された2つ以上の割り当て領域（世代）が保持されます。新しいオブジェクトは、定期的にガベージコレクションされる「若い」世代に作成され、ある世代が満杯になると、古い領域から参照されているオブジェクトが次の最も古い世代にコピーされます。時折、フルスキャンが実行されます。
一部の高級言語を用いたコンピュータアーキテクチャには、リアルタイムのガベージコレクションのためのハードウェアサポートが含まれている。
リアルタイムガベージコレクタの実装のほとんどはトレースを使用します。このようなリアルタイムガベージコレクタは、リアルタイムオペレーティングシステムで使用される場合、厳しいリアルタイム制約を満たします。 [ 47 ]
{{cite book}}:|journal=無視されました (ヘルプ){{cite book}}:|journal=無視されました (ヘルプ)