LINE Engineering
Blog
Go言語のGCについて
この記事はLINE Engineering Blog「夏休みの自由研究 -Summer Homework-」の6日目の記事です。
こんにちは、LINE Ads Platformの開発をしている岡田(@ocadaruma)です。
今回、個人的に以前から気になっていたGo言語のGCについて、この機会に調べましたので紹介いたします。
Go言語
Go言語はGoogleによって開発されたシステムプログラミング言語で、Channelを利用した並行性のサポートやGCを備えていることが特徴です。
Googleをはじめとして多くの企業が使用しており、LINE社内にもGoで開発しているツールやサービスが多数あります。
Go言語のGC
素朴な感覚で言えば、Go言語では低レイテンシなアプリケーションを容易に開発できるいっぽう、GCは他のランタイムと比較してシンプルに見えます。
たとえば、Go 1.10の時点で、Go言語のGCはConcurrent Mark & Sweep(以下CMS)コレクタであり、JVMなどで一般的なコンパクションや世代別GCは行いません。
It is a concurrent mark and sweep that uses a write barrier. It is non-generational and non-compacting.
その他、まとめると以下のようになります。
| JVM (Java8 HotSpot VM) | Go | |
|---|---|---|
| コレクタ | 複数（Serial, Parallel, CMS, G1） | CMSのみ |
| コンパクション | あり | なし |
| 世代別GC | あり | なし |
| チューニングパラメータ | コレクタにより異なるが複数 | GOGCのみ |
そこで、なぜGo言語のGCはシンプルに見えるのにうまく機能するのか興味が湧き、調べてみました。
コンパクション
GCは非移動型と移動型に分けられます。
非移動型GCは、GCによってヒープ内のオブジェクトの再配置を行いません。
たとえば、Go言語の採用しているMark & Sweep GCは非移動型です。
一般的に非移動型GCでは、メモリのアロケートと解放を繰り返すことでヒープの断片化が発生し、アロケーションのパフォーマンスが悪化することが問題と言われます。（ただし、これはメモリアロケーターの実装によります）
いっぽう移動型GCでは、GCの際に生きているオブジェクトをヒープの端に寄せて再配置することで、ヒープの圧縮（コンパクション）を行います。HotSpot VMのGCなどで利用されているコピーGCは、移動型です。
コンパクションを行うことで、以下のメリットが得られます。
- 断片化の回避
- 逐次割付（bump allocation）による高速なメモリアロケーションが実装できる
- 移動型GCでは、オブジェクトはヒープの端に寄っているため、新たにメモリをアロケートする際は、その端からインクリメントしていくだけで済みます。
なぜGo言語はコンパクションを採用していないのか
GoogleのRick Hudson氏によるISMM 2018 Keynote "Getting To Go"を参照すると、以下のことがわかります。
- 2014年の時点では"Read barrier free concurrent copying GC"を計画していた
- しかし期間的な制約から断念し、CMSに舵を切った（この時期に彼らは、ランライムをCからGoに書き換える作業も行う必要がありました。Changes to the runtime）
- TCMallocをベースとしたメモリアロケーターを採用することで、断片化およびアロケーションの速度の問題を解決した
Go言語のメモリアロケーションについては、ランタイムのコードのコメントにも詳しく記載されています。
This was originally based on tcmalloc, but has diverged quite a bit. http://goog-perftools.sourceforge.net/doc/tcmalloc.html
世代別GC
次に、世代別GCについてです。
世代別GCは、ヒープ内のオブジェクトを寿命（GCを生き延びた回数などで表します）によって分類し、GCの効率を向上させようというものです。
「多くのアプリケーションにおいて、新しくアロケートされたオブジェクトのほとんどが短期間で死ぬ」という仮説（世代別仮説）があります。
これに基づくと以下のような戦略を取ることで、長寿命なオブジェクトを何度もスキャンする無駄を避けて、GCを効率化することが可能です。
- 新しくオブジェクトをアロケートする領域に対して頻繁にGCを行う（Minor GC）
- 複数回のGCを生き延びた年長オブジェクトは昇格（promote）させ、別の領域に移動する。別の領域に対しては頻度を下げてGCを行う（Major GC）
Java8 HotSpot VMでは、すべてのコレクタが世代別GCを備えています。
ライトバリア
ただし世代別GCを実現するためには、GCを実行していない時でもアプリケーション側にオーバーヘッドがかかります。
Minor GCを行う方法について考えます。
ルートから新世代の参照のみを辿って、たどり着かなかったものを回収してしまうと、obj2のように、年長オブジェクトから参照されている新世代オブジェクトが誤って回収されてしまいます。
だからと言って年長オブジェクト含めたヒープ全体を辿るのでは、世代別GCの意味がありません。
そこで、アプリケーションにおいて参照を代入したり書き換える際に、年長世代から新世代への参照を別途記録する処理を挟みます。
このように、参照のミューテートに付随して行う処理をライトバリアと呼びます。
したがって世代別GCでは、ライトバリアのオーバーヘッドに対して、得られるメリットのほうが大きいことが期待されます。
なぜGo言語は世代別GCを採用していないのか
前述のとおり、世代別GCではライトバリアを用いて世代間ポインタを記録する必要があります。
ここで再度"Getting To Go"にあたると、世代別GCは検討したものの、ライトバリアのオーバーヘッドが許容できなかったことがわかります。
The write barrier was fast but it simply wasn't fast enough
またGo言語の場合、コンパイラのエスケープ解析が高性能であることに加え、必要に応じてヒープへのアロケーションが行われないようにプログラマが制御可能であることから、世代別仮説における短命なオブジェクトはヒープではなくスタックに割り当てられる傾向があります。（GCする必要が無い）
したがって、世代別GCのメリットは一般的なGCランタイムと比較して薄れます。
実際、高速であることをを謳うGo言語のライブラリには、0-Allocationを実現しているものも数多く存在します。
しかしながら、長寿命なオブジェクトをGC毎に何度もスキャンする無駄自体は残ります。
この点に関してはGoogleのIan Lance Taylor氏も、golang-nutsのトピック"Why golang garbage-collector not implement Generational and Compact gc?"で言及しています。
That is a good point. Go's current GC is clearly doing extra work, but it's doing it in parallel with other work, so on a system with spare CPU capacity Go is making a reasonable choice. But see https://golang.org/issue/17969 .
これは個人の感想ですが、将来的には、なんらかの世代別の戦略を取り入れる可能性はあるかもしれません。
まとめ
今回Go言語のGCについて掘り下げた結果、GCが現在のような構成になっている経緯と、そのデメリットをどう克服しているかについて、理解が深まりました。
Go言語は進化が早く、GCの改善を含め、今後の動向に目が離せません。（今月にはGo 1.11がリリースされます）
明日は、立花翔さんによる「Clovaに関連する開発関連情報のアップデートとスキル開発のインセンティブについて」です。お楽しみに！