HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

What Garbage Collection Costs (shivanshuag.com)

19 pointsby shivanshuag32 コメント

要約

プログラムがメモリを必要とする際、その管理方法には主に2つのパラダイムがあります。一つは言語ランタイムが自動で管理するガーベージコレクション(GC)で、GoやJavaなどが採用しています。もう一つは開発者が手動で管理するか、Rustのようにコンパイラがビルド時に管理する方法です。GCはメモリリークを防ぎ開発者の負担を減らしますが、実行時にCPU時間やメモリを消費するコストが発生します。

全文翻訳

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

すべてのコンピュータプログラムはメモリを必要とします。メモリは有限であるため、長時間実行されるプログラムは、必要に応じてオペレーティングシステムからメモリを借り、不要になったら解放する必要があります。

興味深いのは、そのメモリを誰が、いつ回収するかということです。コードの一部が、メモリが不要になったことを突き止め、それを解放しなければなりません。そして、それを突き止めるのは簡単ではありません。値が別の関数に渡されたり、より長く存続するものに格納されたり、スレッド間で共有されたりする可能性があり、何かが参照し続けている限り、それは必要とされ続けます。早期に回収すると、メモリ破損が発生します。回収が遅すぎると、メモリリークが発生します。

パラダイム

メモリ管理には2つのパラダイムがあり、それぞれ異なるものを最適化しています。

最初のパラダイムは、言語ランタイムに任せることです。プログラムは必要に応じてメモリを割り当て、必要なだけ使用し、最終的に参照を停止します。ガベージコレクタは、到達不能になったものを突き止め、それを回収します。Go、Java、その他多くの広く使われている言語がこのカテゴリに属します。メモリ解放のタイミングを自分で決定することはできませんが、その代わりに、早すぎる解放、二重解放、または解放忘れを防ぐことができます。ほとんどのソフトウェアにとって、これは非常に良い妥協点です。メモリ管理の認知的オーバーヘッドを削減し、実際の課題に集中できます。解放し忘れることによるリークは完全に解消されます。

2番目のパラダイムは、現時点では非常に明白であるはずですが、自分で決定を保持することです。C言語では、手動で割り当てと解放を行い、その結果生じるすべてのバグの責任を負います。Rustでは、解放を自分で記述しませんが、ランタイムに決定を委ねることもありません。コンパイラはビルド時に各値の寿命の終わりを計算し、そこで回収し、それが安全であることを証明できない場合はプログラムのビルドを拒否します。これにより、メモリの制御とよりタイトなフットプリントが得られますが、労力がシフトします。C言語ではデバッグによる破損でその代償を払います。Rustでは、コンパイラが検証できる方法でプログラムを構成することで代償を払います。

その中間に位置するのが参照カウントであり、SwiftやPythonが行っていることです。これは実際には3番目のパラダイムというよりは最初の回答のバリアントであり、それだけでは十分なことはめったにありません。カウントはサイクルを検出できないため、言語は他の方法でそれらを処理する必要があります。Pythonはサイクルを探すトレーシングコレクタを組み込んでいます。Swiftはそうせず、代わりに weak および unowned アノテーションを通じて問題をユーザーに押し付けます。参照カウントには、ポインタのコピーごと、および解放するたびに支払われる実行時コストも伴います。

どちらを選ぶべきでしょうか?ガベージコレクションが無料であれば、私たち全員がメモリを自分で管理するランタイムを選ぶでしょう。しかし、それは無料ではないため、GCのパフォーマンスペナルティと、それが重要かどうかについて議論します。

スタックとヒープ

プログラムがメモリを必要とするとき、それはスタックまたはヒープの2つの場所のいずれかから取得されます。スタックメモリはコレクタにとってコストがかかりません。関数が呼び出され、戻るにつれて増減し、マシンは単にポインタを移動させるだけです。関数が戻ると値は消え、何も回収する必要はありません。スタックはコレクタにとって完全に不可視ではありません。ライブオブジェクトがどこから始まるかを見つけるためのルートとしてスキャンする必要があるためですが、そこにあるものを解放する必要はありません。

値がヒープに配置されるのは、次の2つの理由のいずれかです。作成した関数よりも長く存続する必要があるため、その参照を返したか、より長く存続するものに格納しました。または、そのサイズが事前にわからず、成長する可能性があるためです。たとえば、スライスを継続的に追加したり、ユーザー入力からサイズが決定されるバッファなどです。ヒープ割り当ては、GCが監視および回収するメモリのクラスであり、GCコストに影響します。次のセクションでこれを議論します。

コレクションのコスト

コレクションが何によってコストがかかるかを理解するには、2つの質問に答える必要があります。コレクタがどれくらいの頻度で実行されるか、そして1回の実行にどれくらいのコストがかかるかです。

コレクタが実行される頻度は、バイトを消費する速度によって決まります。メモリがいっぱいになると、コレクタはライブオブジェクトの全体像を再構築するために強制されます。

コレクタが実行されるたびに、1つの質問に答えなければなりません。何がまだ到達可能か?それに答えるために、プログラムのライブオブジェクトとそれらの間の参照のグラフを構築し、グラフに含まれていないすべてを回収します。このプロセス全体、つまり起動、グラフの構築、残りの回収は1回のGCサイクルであり、グラフの構築は通常マーキングと呼ばれる部分です。それを構築するには、ルートから歩き、見つかったすべての参照をたどり、これがサイクルのコストを決定します。

GCサイクルは、実際には使用されているメモリに対して課金しているのではなく、オブジェクトと参照に対して課金しています。それらの参照のいずれかの背後にあるメモリの量は関係ありません。百万個の小さなオブジェクトが互いに指し合っている4GBのグラフを収集することは、単一の4GBバッファよりも桁違いに高価です。両方のプログラムは同じ量のメモリを使用しており、まったく異なる量の作業を要求しています。この驚くべき結果は、コレクションステップでは、コストはデッドポインタやガベージではなく、ライブポインタに比例するということです。

マーキングには2番目のコストが伴います。コレクタがグラフを構築している間、プログラムは実行を続け、ポインタを変更し続けており、その下で動いている画像にマーキングすることはできません。グラフが古くなるのを防ぐために、プログラムがウォーク中に実行するすべてのポインタ書き込みは、変更を報告するために少し余分な作業を行います。その作業はコレクタではなくプログラムに課金されるため、測定したGC時間には表示されません。これも、ポインタを多用するコードがGC中にコストが高くなる別の理由です。

ランタイムは、これらすべてをどのように行うかについて大きく異なります。それぞれが数十年にわたる慎重な作業の成果です。一部は時々最初から全体像を再構築し、一部は常に最新の状態に保ち、一部はほとんどのオブジェクトがすぐに死ぬという理由で若いオブジェクト用に別の全体像を保持します(Javaの世代別GC)。ほとんどはどこかにダイヤルを提供しており、コレクションの前にヒープをさらに成長させることで、実行頻度は低くなりますが、その間により多くのデッドメモリが残ります。これらすべては、特定のランタイムで特定のプログラムを調整する際に非常に重要です。しかし、それが変更するのは定数であり、どの種類のアロケーションプロファイルを最適化するかです。コストに影響する要因は変更しません。

手動またはコンパイラ管理の世界と比較してください。そこでの割り当ては無料ではありません。malloc には独自のフリーリストとロック競合があります。しかし、コストはポインタを割り当ててから解放する命令にあります。ポインタが到達可能かどうかを判断するために全体をスイープする必要があるシステムはありません。

測定すべきこと

プログラムがGCの圧力のために遅い、またはOOM(Out Of Memory)になっていると言うとき、追求すべきは使用しているメモリの量ではありません。どのようなプログラムでも、どのような言語でも、代わりに尋ねる価値のある3つのことがあります。

  1. ライブオブジェクトをいくつ保持していますか?
  2. それらのオブジェクトは互いにどれだけ密接にリンクされていますか?
  3. そして、それらをどれくらいの速さで処理していますか?

測定は3つのフェーズで行われます。最初のフェーズはトリアージ(優先順位付け)で、時間の価値があるかどうかだけを教えてくれます。2番目のフェーズは3番目の質問、つまり処理速度に答えます。3番目のフェーズは最初の2つ、つまり保持している量とリンクの密度に答えます。

最初のステップは、コレクタが問題であるかどうかを測定することです。ここで探すべきはCPUです。プログラムではなく、コレクションにどれだけのプロセッサ時間が費やされているか。GCが使用するCPUサイクルはすべて、実際の作業を実行するためにプログラムから奪われるCPUサイクルです。Goは runtime/metrics パッケージを通じてこれを公開しており、コレクションに費やされたCPU秒数と利用可能な合計時間を報告します。Javaは、GCログまたはプロファイラから同じ画像を提供します。そのシェアが小さい場合、ここで停止できます。GCはプログラムの最適化が必要な問題ではありません。

2番目は、どのコード部分がガベージを生成しているかです。これはアロケーションプロファイルであり、発生元に帰属する割り当て数と1アロケーションあたりのバイト数を測定したいと考えます。Goでは、alloc_objects と alloc_space を介して読み取られるヒーププロファイル、またはベンチマークから作業している場合は allocs/op と B/op です。Javaでは、プロファイラからのアロケーションイベントで、スタックトレースに帰属します。ほとんどの場合、ほとんどのチャーン(急激な変化)の原因となっているのは少数のコールサイトであることがわかり、これらを最適化する必要があります。

3番目は、プログラムが何に固執しているかです。ほとんどの場合、ホットなアロケーションパスを最適化するだけで十分であり、これを行う必要はありません。さらに進む必要がある場合は、単一GCサイクルのコストは、デッドポインタではなくライブポインタの数に比例することを覚えておいてください。アロケーションプロファイルは作成されたものを教えてくれますが、生き残ったものについては何も教えてくれないため、真の問題がメモリに保持されている大きな構造体であるプログラムは、アロケーションプロファイルではまったく目立たないように見えます。そのためには、ライブビュー、つまりGoの inuse_objects と inuse_space、またはJavaのヒープヒストグラムが必要です。

ポインタ密度は、直接報告されるメトリックではありませんが、派生させることができます。ライブバイトをライブオブジェクトで割り、平均サイズを見ます。多数の小さなオブジェクトは、それらをまとめる多くのポインタを意味するため高価であり、少数の大きなオブジェクトは安価です。このシグナルは、平均サイズがコレクタがたどる必要があるポインタの数の代理であるため、測定というよりはラフなものです。平均サイズが正しい方向に移動し、ポインタ数がそれに伴って移動する場合、通常は望ましい最適化が得られます。

早すぎる最適化

ほとんどのソフトウェアにとって、GCのオーバーヘッドを心配することは間違いであり、最適化を試みることは早すぎる最適化になります。

しかし、この方程式が逆転し、アロケーションの挙動が成功または失敗の要因となる特定のクラスのプログラムがあります。ここに短いチェックリストがありますので、後からの最適化としてではなく、ソフトウェアの設計にその決定を組み込むことができます。次の質問を自問してください。

ホットパスを通過するデータ量はどれくらいですか? ウェブリクエストあたりのアロケーションは問題ないかもしれません。1000万行のループでの同じアロケーションは問題になるかもしれません。

レイテンシのテールは重要ですか? 平均レイテンシではなく、テールです。コレクションが実行されている間、CPUの一部はプログラムから奪われます。そして、Goを含む多くのランタイムでは、コレクションの進行中に割り当てを行うスレッドはマーキングの支援に引き込まれるため、その作業はそれが完了するまで待機します。時折の応答遅延が許容できるなら、これを心配する必要はありません。

ハードウェアを限界までプッシュしていますか? ほとんどのプログラムはマシンをほとんどアイドル状態のままにして、ネットワーク、データベース、ディスクなどの他のものに待機する時間を費やします。そのような場合、コレクタの作業はスラック(余裕)に消えます。CPUを飽和させようとするときにのみ表面化します。

プロセスは長時間実行され、多くのものを保持しますか? 大量のキャッシュをメモリに保持するサービス、または数百万個の小さなオブジェクトで構成され、それらがすべて互いを指しているインデックスを考えてみてください。それらのポインタのそれぞれは、プロセスが稼働している限り、すべてのサイクルでたどられなければなりません。そして、これはサービスが何もしていないときでも発生します。コストは作成しているものではなく、保持しているものにあるため、割り当てを減らすことはここでは役に立ちません。

データパイプライン、データベース、ゲームエンジン、または高スループットサービスは、これらのいくつかに「はい」と答えるかもしれません。典型的なWebバックエンドやCLIツールはそうではないかもしれません。

次に来るもの

実務経験から、ほとんどの人はパラダイムを選択する機会さえありません。会社に入社してプロジェクトを引き継ぐか、社内ツールが高価すぎて新しい言語の採用が決して行われないかのどちらかです。選択はすでに数年前にされていました。

したがって、有用な質問は、すでに立っている側から何ができるかです。GCの最適化に触れましたが、これらの最適化が何であるかについては議論しませんでした。Goは、その評判が示唆するよりもはるかに多くの余地を与えてくれます。適切な仕事に適切なツールを使用するだけです。割り当てを減らすことができます。すでに割り当てたものを再利用できます。そして、コレクタがまったく歩く必要のないメモリ領域を切り出すことができます。これが次に進むことです。