Go のGCのオーバーヘッドが高くなるケースと、その回避策

# Go のGCのオーバーヘッドについて

GoのGarbage Collector (GC)の性能は非常に優秀で、オーバーヘッドが問題となることはあまりありません。ただヒープを非常に多く使っている場合、GCが多くのCPU時間を消費するケースがあります。

本記事では、まずGoのGCの概要に触れ、その後GCオーバーヘッドが高くなるケース、そして回避策を検討します。

本記事は下記記事を大きく参考にしています。素晴らしい記事に感謝いたします。
[Avoiding high GC overhead with large heaps](https://blog.gopheracademy.com/advent-2018/avoid-gc-overhead-large-heaps/)


### 注意点

単に pprof を取得し、GCが多くCPU時間を消費していた場合、必ずしも本記事が扱う、ヒープの多さ依存の問題が原因とは限りません。
GoのGCは、直近のGCを行った結果生き残ったデータ量に対して、新たにアロケートしたデータの量が一定値を超えると実行されます。 [^1]
このスレッショルドは `GOGC` 環境変数によって指定できます。
つまり、新たにアロケートしたデータ量が多ければ多いほど、GCの頻度が高くなります。GCがCPU時間を多く消費していた場合、まずはアロケートするデータ量が無意味に多くなっていないか、探してみましょう。[^2]

なお現在のGoのGCの実装だと、[少なくとも2分に一度GCが強制的に走る](https://github.com/golang/go/blob/f4e7a6b905ce60448e506a3f6578d01b60602cdd/src/runtime/proc.go#L5016-L5021)ので、2分おきにGCが原因でCPU使用率がスパイクした[Discordの事例](https://blog.discord.com/why-discord-is-switching-from-go-to-rust-a190bbca2b1f)もあります。

# Go の GC の概要

GoのGCは concurrent な Mark-Sweep GC です。[^3]
このMark-Sweep GCではマークフェイズとスイープフェーズに別れ、

* マークフェイズでは、レジスタや大域変数などルートからポインタをたどっていき、使われる可能性のあるメモリ上のオブジェクトをマークしていきます。
* スイープフェーズでは、マークフェイズの結果、どこからも参照されていないオブジェクトを解放します。

GoのGCでは、ユーザープログラムと平行して行うことで、ユーザープログラムの停止時間(StW; Stop the World)を減らしリアルタイム性を高めています。ただユーザプログラムが行なう「オブジェクトの書き換え」がGCを破綻させないよう、write barrierによるStWは短いですが発生しています。

オブジェクトの生存時間が長いものはGCの頻度をへらす Generational GC といった仕組みはGOでは採用されていないので、スキャンするメモリが多いほど、時間がかかることとなります。




# GCオーバーヘッドが高くなるケース

前項のとおり、GoのGCは仕組み上、スキャンするメモリが多いほど、マークフェイズで時間がかかります。使用しているオブジェクトがよほど多くない特殊なケース以外では、問題なく高速に動き、StWも短いです。

ただ、メモリを大規模に使うケースでは問題が発生しうるでしょう。

* 巨大なインメモリデータベースを作る
* 巨大な道路網をメモリ上に持った位置情報システムを作る
* 機械学習システムでFeature Storeを作る


例を見てみましょう。10億（1e9）の8バイトポインタ、つまり約8GBのメモリを割り当て、GCの所要時間を計測します。

``` golang
func main() {
	a := make([]*int, 1e9)

	for i := 0; i < 10; i++ {
		start := time.Now()
		runtime.GC()
		fmt.Printf("GC took %s\n", time.Since(start))
	}

	runtime.KeepAlive(a)
}
```
( source: [Avoiding high GC overhead with large heaps](https://blog.gopheracademy.com/advent-2018/avoid-gc-overhead-large-heaps/) )

手元のMacBook Pro、go1.15.5 だと以下の実行時間を得ます。

```
GC took 5.614972137s
GC took 1.972851931s
GC took 597.176024ms
GC took 565.235619ms
GC took 575.405193ms
GC took 534.041162ms
GC took 572.019893ms
GC took 562.320811ms
GC took 529.456775ms
GC took 531.40725ms
```

10億個のポインタの生存チェックを数秒で行っているのは性能が高いと言えますが、数秒のパフォーマンスは課題となりえます。
ポインタが多いと、GCのマークワーカーがCPU時間を消費していくこととなります。

ここで、ポインタではなく、10億の8バイトintのスライスを割り当ててみるとどうでしょうか。メモリのサイズは同じです。

``` golang
func main() {
	a := make([]int, 1e9)

	for i := 0; i < 10; i++ {
		start := time.Now()
		runtime.GC()
		fmt.Printf("GC took %s\n", time.Since(start))
	}

	runtime.KeepAlive(a)
}
```
( source: [Avoiding high GC overhead with large heaps](https://blog.gopheracademy.com/advent-2018/avoid-gc-overhead-large-heaps/) )

これを同じマシンで実行します。

```
GC took 692.498µs
GC took 282.914µs
GC took 317.577µs
GC took 311.76µs
GC took 282.647µs
GC took 286.659µs
GC took 216.436µs
GC took 210.239µs
GC took 292.877µs
GC took 257.876µs
```

メモリのサイズは同じですが、GCは1000倍以上高速となっています。これはポインターの量がマークフェイズの仕事量に関わってきているのでしょう。

今回は `*int` 型で実験しましたが、ポインターを暗黙的に含む型でも同じ問題が起きます。例えば以下のような型です。これらの型のオブジェクトが多数あるとこの問題が発生します。

- string型
- time.Time型

また以下のようなmapの要素数が大きくても問題が出ます。

- valueがsliceのmap
- keyがstringのmap

例えば、二次元マップで行列を表現しようとすると( `map[int]map[int]int` ) 同じ問題に直面します。メモリ量が増えるので数を減らして実験します。

``` golang
func main() {

	a := make(map[int]map[int]int, 1e7)

	for i := 0; i < 10; i++ {
		start := time.Now()
		runtime.GC()
		fmt.Printf("GC took %s\n", time.Since(start))
	}

	runtime.KeepAlive(a)
}
```

```
GC took 75.645528ms
GC took 44.313414ms
GC took 22.037132ms
GC took 25.841337ms
GC took 23.272759ms
GC took 24.587415ms
GC took 21.945317ms
GC took 23.831554ms
GC took 23.023176ms
GC took 23.530684ms
```

なおこれはあくまで、GCのワーカーがこれだけCPU時間を消費しているという問題であり、この時間だけStWが発生しているわけではありません。

# 回避策
* GCの管轄外でメモリアロケートする
* データ構造を工夫してポインターを持たないようにする

方法が考えられますがいずれも銀の弾丸ではありません。

## GCの管轄外でメモリアロケートする

mmap syscallを直接呼びunsafe packageで型を割り当てる方法が考えられますが、互換性やメンテナンス性、安全性から奨励できないでしょう。

## データ構造を工夫してポインターを持たないようにする

こちらはケースバイケースであり、使い勝手が失われるケースもあります。

* ポインタのスライスを使う前に、値のスライスで済まないか検討しましょう
* 多数の string を持つのではなく、一つの string変数にconcatする。各文字列の開始、終了のindexを記憶しておき、スライスで部分文字列にアクセスしましょう
* ポインタを含むtime.Time型ではなく、unixtimeをintで持ちましょう
* 二次元マップは1次元のスライスで表現しましょう。各keyのvalueが、1次元のスライスではどのインデックスになるかマップで管理しましょう。

# 所感
大量にメモリを使ってインメモリデータベースを作る用途だとGCがパフォーマンスに影響出るのは仕方ないと思われます。Generational GCといった古いオブジェクトはGC対象外とする仕組みがあればインメモリデータベースの用途では問題は出なくなりますが、ないものは仕方ないです。
なおGoでGenerational GCが採用されなかった理由は、[Getting to Go: The Journey of Go's Garbage Collector](https://blog.golang.org/ismmkeynote)やその紹介記事 [Go言語のGCについて
](https://engineering.linecorp.com/ja/blog/go-gc/)にあります。
GoのGCはよくバージョンアップされている箇所なので、個人的に今後のアップデートに注目しています。

# 参考資料
* [Avoiding high GC overhead with large heaps](https://blog.gopheracademy.com/advent-2018/avoid-gc-overhead-large-heaps/)
* [一般教養としてのGarbage Collection(コンパイラ演習番外編)](http://matsu-www.is.titech.ac.jp/~endo/gc/gc.pdf)
* [Why Discord is switching from Go to Rust](https://blog.discord.com/why-discord-is-switching-from-go-to-rust-a190bbca2b1f)
* [Getting to Go: The Journey of Go's Garbage Collector](https://blog.golang.org/ismmkeynote)

[^1]: https://godoc.org/runtime
[^2]: 塀記事  [Go slice ベストプラクティス](https://qiita.com/imoty/items/bb18fb50d526474d2d10) が参考になれば幸いです。
[^3]: https://github.com/golang/go/blob/master/src/runtime/mgc.go#L7-L10