ガーベージコレクションのコスト

このページについて 全てのコンピュータプログラムはメモリを必要とします。メモリは有限であるため、長期間実行されるプログラムは必要に応じてオペレーティングシステムからメモリを借り、不要になったら解放する必要があります。興味深いのは、誰がいつそのメモリを回収するかです。何らかのコードがメモリが不要になったことを判断し、それを解放しなければなりませんが、それを判断するのは簡単ではありません。値は別の関数に渡されたり、より長く存続するものに格納されたり、スレッド間で共有されたりする可能性があり、何かが参照している限り必要とされます。早期に回収するとメモリ破損が発生します。回収が遅すぎるとメモリリークが発生します。 パラダイム メモリ管理には2つのパラダイムがあり、それぞれ異なるものを最適化しています。最初のパラダイムは、言語ランタイムに任せることです。プログラムは必要に応じてメモリを割り当て、必要な間使用し、最終的に参照を停止します。ガーベージコレクタは、何が到達不可能になったかを判断し、それを回収します。Go、Java、その他多くの広く使われている言語がこのカテゴリに属します。メモリ解放のタイミングを自分で決定することを諦める代わりに、早期に解放したり、二重に解放したり、解放し忘れたりすることを防ぐことができます。ほとんどのソフトウェアにとって、これは非常に良い妥協点です。メモリ管理の認知的オーバーヘッドを減らし、実際の課題に集中できます。解放し忘れることに起因するリークは完全に解消されます。 2番目のパラダイムは、現時点で非常に明白であるはずですが、決定権を自分で持つことです。C言語では、手動で割り当てと解放を行い、その結果生じるあらゆるバグの責任を負います。Rustでは、解放を自分で記述しませんが、ランタイムに決定を委ねることもありません。コンパイラはビルド時に各値の寿命の終わりを判断し、そこで回収し、安全性を証明できない場合はプログラムのビルドを拒否します。そのため、メモリの制御とよりタイトなフットプリントを得られますが、労力はシフトします。C言語では、デバッグによる破損でその代償を払います。Rustでは、コンパイラが検証できる方法でプログラムを構成することで代償を払います。 その中間に位置するのが参照カウントで、SwiftやPythonが行っていることです。これは実際には3番目のパラダイムというよりは最初の回答のバリアントであり、それだけでは十分なことはめったにありません。カウントは循環を検出できないため、言語は他の方法でそれに対処する必要があります。Pythonは循環を検出するトレーシングコレクタを組み込んでいます。Swiftはそうせず、代わりにweakやunownedアノテーションを通じて問題の開発者に押し付けます。参照カウントには、ポインタのコピーごと、およびドロップするたびに支払われる独自の実行時コストもあります。 どれを選ぶべきか？ ガーベージコレクションが無料であれば、全員がメモリを自分で管理するランタイムを選ぶでしょう。しかし、それは無料ではないため、GCのパフォーマンスペナルティと、それが問題になるかどうかを議論します。 スタックとヒープ プログラムがメモリを必要とする場合、それはスタックまたはヒープのいずれかから供給されます。スタックメモリはコレクタにコストをかけません。関数が呼び出され、戻るにつれて成長・縮小し、マシンは単にポインタを移動させるだけです。関数が戻ると値は消え、何も回収する必要はありません。スタックはコレクタにとって完全に不可視ではありません。ライブオブジェクトがどこから始まるかを見つけるためにルートとしてスキャンする必要があるからです。しかし、スタック上のものを解放する必要は決してありません。 値がヒープに配置されるのは、次の2つの理由のいずれかです。1つは、それが作成した関数よりも長く存続する必要がある場合です。なぜなら、その参照を返したか、どこかに長く存続するものに格納したからです。または、そのサイズが事前にわからず、成長する可能性がある場合です。例えば、継続的に追加していくスライス、ユーザー入力からサイズが決まるバッファなどです。ヒープ割り当ては、GCが監視および回収するメモリのクラスであり、GCコストに影響します。これについては次のセクションで説明します。 コレクションのコスト 何がコレクションのコストになるかを理解するには、次の2つの質問に答える必要があります。コレクタはどのくらいの頻度で実行されるか、そして単一の実行にはどのくらいのコストがかかるかです。コレクタが実行される頻度は、バイトを消費する速度によって決まります。メモリがいっぱいになると、コレクタはライブオブジェクトの画像を再構築するために強制的に実行されます。コレクタが実行されるたびに、1つの質問に答えなければなりません。何がまだ到達可能か？それに答えるために、プログラムのライブオブジェクトとその間の参照のグラフを構築し、グラフに含まれていないものをすべて回収します。このプロセス全体、つまり起動、グラフの構築、残りの回収は1回のGCサイクルであり、グラフの構築が一般的にマーキングと呼ばれる部分です。それを構築することは、ルートから始めて見つかったすべての参照をたどることを意味し、これがサイクルのコストを決定します。GCサイクルは、実際には使用されているメモリに対して課金されているのではなく、オブジェクトと参照に対して課金されています。それらの参照のいずれかの背後にあるメモリの量は決して考慮されません。互いにポインタを指す100万個の小さなオブジェクトからなる4GBのグラフを収集することは、単一の4GBバッファよりも桁違いに高価です。両方のプログラムは同じ量のメモリを使用していますが、要求される作業量は全く異なります。この驚くべき結果の1つは、コレクションステップでは、コストはデッドポインタやガベージではなく、ライブポインタに比例するということです。 マーキングには2番目のコストが関連付けられています。コレクタがグラフを構築している間、プログラムは実行を続け、ポインタを変更し続けており、その下で動いているものをマークすることはできません。グラフが古くなるのを防ぐために、ウォーク中にプログラムが行うすべてのポインタ書き込みは、変更を報告するために少し余分な作業を行います。その作業はコレクタではなくプログラムに課金されるため、測定したGC時間には表示されません。これも、ポインタが多いコードがGC中にコストが高くなるもう1つの理由です。 ランタイムはこれらすべてを行う方法において大きく異なります。それぞれが数十年にわたる慎重な作業に支えられています。一部は時々最初から画像を再構築し、一部は進捗に合わせて最新の状態に保ち、一部はほとんどのオブジェクトがすぐに死ぬという理由で若いオブジェクト用に別の画像を用意します（Javaの世代別GC）。ほとんどはどこかにダイヤルを提供しており、収集前にヒープをさらに成長させることで、実行頻度は減りますが、その間により多くのデッドメモリが残ります。これらすべては、特定のランタイム上の特定のプログラムを調整する際に非常に重要です。しかし、それが変更するのは定数であり、どの種類のアロケーションプロファイルを最適化するかです。それはコストに影響する要因を変更しません。 これらすべてを手動またはコンパイラ管理の世界と比較してください。そこでの割り当ても無料ではありません。mallocには独自のフリーリストとロック競合があります。しかし、コストはポインタを割り当ててから解放する命令にあります。ポインタが到達可能かどうかを判断するためにセット全体をスキャンする必要があるシステムはありません。 何を測定するか プログラムがGCの圧力のために遅い、またはOOM（メモリ不足）になっていると言うとき、追求すべきは使用しているメモリの量ではありません。どのプログラムでも、どの言語でも、代わりに尋ねる価値のある3つのことがあります。保持しているライブオブジェクトはいくつですか？それらのオブジェクトは互いにどのくらい密接にリンクされていますか？そして、それらをどのくらいの速さで切り替えていますか？測定は3つのフェーズで行われます。最初のフェーズはトリアージで、時間の価値があるかどうかだけを教えてくれます。2番目のフェーズは3番目の質問、つまり切り替えの速さを答えます。3番目のフェーズは最初の2つ、つまり保持している量とリンクの密度を答えます。 最初のステップは、コレクタが問題であるかどうかを測定することです。ここで探すべきはCPUです。プログラムではなく、コレクションにどのくらいのプロセッサ時間が費やされているかです。GCが使用するCPUサイクルは、実際の作業を実行するためのプログラムから奪われるCPUサイクルです。Goはruntime/metricsパッケージを通じてこれを公開しており、コレクションに費やされたCPU秒数を総利用可能時間に対して報告します。JavaはGCログまたはプロファイラから同じ画像を提供します。そのシェアが小さい場合は、ここで止めることができます。GCは op が必要とする問題ではありません。