Go言語の Garbage Collector を理解したい


Posted by Akira Masuda on Tue, Oct 22, 2019
Tags golang, gc, language

Go言語の Garbage Collector を理解したい

プログラミング言語をマスターしていく上で、その言語のランタイムの特性を把握するのは非常に大切。 Go 言語を理解するために、Go の GC が何を行っているのかを知りたい

まずそもそも GC (Garbage Collection) とは何か?

GC はメモリの管理を自動にし、mutator が作成し不要になった object を削除すること。

object とは?

GC でいうところの object はメモリを利用するデータの塊のことを指す。object 内には header が埋め込まれており、object のサイズや種類が入っている。

mutator とは?

mutator (変化させるもの) は基本的に実行しているアプリケーションプログラムを指す。 mutator は、object を作成したり、object の参照を更新したりする。しかし、object の領域を解放することはしない(それは GC の仕事)。

GC のない言語では、object のメモリ領域の解放もアプリケーションプログラムが行う。(C 入門時に malloc や free 関数を使うのに苦労した記憶が蘇る…) これを GC の対義語として、 manual memory management と言ったりする。

GC のある言語では、mutator が使い終わって不要になった領域を GC が健気に回収していく。 このとき、mutator に利用されている object は live object、そして、不要になった object を dead object と呼ぶ。

chunk とは?

chunk という言葉は情報工学の中で様々な使われ方をされるが、GC の世界では、将来的に object として利用できる空き領域を指す。

memory heap の中でまず mutator が起動する前は chunk の状態から始まる。 そこから、live object が作られ、その後 dead object になり、GC がそれを回収して chunk に戻る、というライフサイクルを送る。

GC の基本 Mark & Sweep

Mark & Sweep アルゴリズムは、live object を Mark するフェーズと Mark されていない dead object を Sweep するフェーズにわかれる。

Mark フェーズでは、すべての root をなめていき、利用されている object にマークをつけていく。このとき、object が Mark 済みかどうかフラグをつけることで無限ループに陥らないようにする。

面白いのは、この root をなめていく処理の際、object 参照を探索していくため、幅優先探索か深さ優先探索を行う。しかし、深さ優先探索のほうがメモリ使用率が少ないため、よく使われる。 GC も自身のメモリ消費を気をつけないといけないのだ。

Sweep フェーズでは、heap の先頭から object が Mark されているかどうかを調べていき、Mark されていない object については、free list に追加する。 そうすることで、次に mutator から chunk が求められたとき、free list の中から求められたサイズにあった object を返して、mutator はそれを利用することがデキる。

参考

ガベージコレクションのアルゴリズムと実装
中村 成洋, 相川 光, 竹内 郁雄(監修)
達人出版会
発行日: 2013-12-24
対応フォーマット: PDF, EPUB

Go言語の GC について

Getting to Go: The Journey of Go’s Garbage Collector - The Go Blog を抄訳しつつ、自分なりの理解を補足します)

Go のプログラムは膨大な数のスタックがあり、これらは Go scheduler によって管理され、 GC safepoint で差し替えられる。 Go scheduler は数々の goroutine を OS の thread にひもづけて、できるだけ 1 OS thread が 1 HW thread で動作するように調整する。 (HW thread とは、ここでは CPU の物理的なコアと推測される)

Go scheduler はスタックとそのサイズ情報をコピーして、スタック内のポインタを更新することによって管理する。

Go scheduler について

にもあるとおり、これはこれでまた長い説明が必要なため、また別の機会とする。

Go は値型中心の言語

多くの参照型中心な managed runtime な言語とはことなり、Go は値型中心な言語である。 例えば、

type Reader struct {
	r    io.Reader
	pad  int64      // Amount of padding (ignored) after current file entry
	curr fileReader // Reader for current file entry
	blk  block      // Buffer to use as temporary local storage
	err error
}

tar - Golang について考えてみる。

すべてのフィールドは直接 Reader 構造体の値として埋め込まれている。 このように、プログラマにはメモリのレイアウトについてよりコントロールを与えられる。 例えば、関連する値を持つフィールドを集約でき、その結果、cache locality を高めることができる。

値型中心の設計は Foreign Function Interface (FFI) にも役立つ。 Go には C と C++ の高速な FFI が存在する(cgo)。 Google にはたくさんのソフトウェア資産があるが、それらは C++ で記述されているため、移植が進めやすい。(C, C++ は値型中心の言語)

この値型中心な言語仕様が他の GC を持つ言語とは大きく異なる点である。

Go のコンパイルについて

Go は ahead of time (AOT) compilation を行う。これにより、生成されたバイナリファイルは native に実行が可能となる。 (Ahead-of-time compilation - Wikipedia。日本語だと事前コンパイルと言われたりするようだ)

Go では Just in time (JIT) compilation を実行しないが、これにはメリデメが存在する。

  • メリット:プログラムの再現性が JIT compilation と比べてかなり簡単のため、コンパイラの改善がずっと簡単に行える。
  • デメリット:JIT のようにプログラム実行時のフィードバック最適化が行えないため、実行速度は JIT ほど出せないことがある。

JIT コンパイルとは

実行時コンパイルで、例えば Java の場合だとソースコードを機械語に変換するのではなく、バイトコードという OS や CPU に依存しない中間言語 (.class) に変換する。 そして、バイトコードを JVM がプログラム実行時にコンパイルしてメモリに機械語を展開する。

JIT コンパイルの 1つのメリットは、このバイトコードを配布すれば、JVM の動く環境でプログラムが実行できる。 もう 1つのメリットは、実行時の情報をもとに関数のインライン化、 

参考

GC を調整するための2つのパラメータ

GC を調整するためのパラメータが2つある。

1つ目は、GCPercent である。これは、GC にどれほどの CPU と RAM を利用させるかを調整する。 デフォルトは 100 で heap の半分が live memory, 残りの半分が allocation に利用される。

2つ目が、MaxHeap である。これは、heap の最大値を設定できるようになる。 Out of memory (OOM) は Go では大問題となる。一時的なメモリのスパイクには処理の中断ではなく、CPU コストでカバーしたい。 Go の場合、GC がメモリの上昇を検知した場合、アプリケーションに対して負荷を減らすように通知する。 (メモリを守るような動作を行う)

MaxHeap はメモリのスケジューリングにもより柔軟性をもたせる。 heap サイズの上限を定めることで、runtime はどれほどメモリが使えるのかいつも気にしなくてよくなる。

Go の runtime の歴史

2014 年 Go にとって GC の遅延が脅威だった

2014 年の段階で、GC の遅延が Go の存在意義に関わる脅威であった。

他の新しい言語も同じ問題に抱えており、例えば Rust は別の方法でその問題に対応した。(FYI: RustはGCなしでどうやってヒープを管理しているかのメモ – ukitaka – iOS開発とかのメモ

GC の遅延は積み重なる

例えば、Go のサーバで 100 リクエストを捌くとする。

99 パーセンタイルのユーザに対して、GC の処理時間を 10ms に抑えようとすると、GC が利用できる時間は 1% ではなく、実際は 0.01 % に抑える必要があった。 (Google の規模の処理を実施するためにはこれほどまでに突き詰めた性能が必要であり、これを「暴虐な9s (tyranny of the 9s) 問題」と Google 内では呼んだそうな。99.99% を GC 以外の処理にあてる必要があったため)

そもそもなんで 99 パーセンタイルというような高い指標を達成する必要があったのかというと、Google のスケールとなるとサーバーのスケールアウトでカバーしようにも、新しいデータセンターが必要なくらいコストがかかってしまう。 逆に言えば、このコストが Go の GC をチューニングする良い機会になった。

最初に取り組んだのは、すべての runtime とコンパイラを Go に変えることだった(それまでは C だったが、バグに悩まされた。)

そして、read barrier のない concurrent GC を作ることにした。(最初は Copying GC で作ろうとしたがやめた) 具体的には tri-color concurrent アルゴリズムを利用する。 この決断に至ったのは、Dijkstra のアルゴリズムが複数のアプリケーションスレッドの問題に対して機能したのと、STW (Stop the world) 問題に対応できることが研究でわかったからだった。

STW (Stop the world) とは?

GC が object の参照状態を一時的にすべて解析し、不要なものを解放する。 その間、新しい object の allocation が行えないため、mutator にとっては「世界が止まった」ように見える。

Copying GC とは?

Mark & Sweep GC ではフラグメンテーションが起きてしまうが、Copying GC では heap 内の隙間を詰めていくため、フラグメンテーションが起きないように鳴っている。

参考

comments powered by Disqus