GoのGCなどで見かける3色マーキング

これはあくあたん工房お盆休みアドベントカレンダー2日目の記事です．
本当はGoでDeepLearningする記事を書きたかったのですが，ギリギリまで粘ってもバグが取り切れずとても悲しいので，GoのGC¹に関係する話をちょっと書きます．

先日mattnさんがGo ランタイムのデバッグをサポートする環境変数という記事を公開されました．
最近趣味でGCを勉強し始めた身としては，runtimeのコードを読む際にとてもためになる記事で大変ありがたいです．

Concurrent GC

昔話にはなりますが，Goは1.5にて並行GCを導入しました²．それまでは停止形GC(Mark&SweepGC)を採用しており，ヒープのサイズによってはMarkフェーズのたびに秒単位でプログラムが止まるということがあったらしいです³⁴.
この頃Goを触っていた方はどのように対処されていたのでしょうか．気になります．

3色マーキング

Goは並行GCということもあり，3色マーキング(Tri-color Marking)という言葉をよく見かけます．
これは実際にオブジェクトを3色に塗っているわけではなく，マーク処理における3種類のオブジェクトの状態に便宜上つぎのように色を付けて呼んでいます．

• 白: マークされていないオブジェクト
• 灰色: 探索候補に入っているオブジェクト
• 黒: 探索済みのオブジェクト

白と黒は従来のMark&SweepGCと同様，オブジェクトのヘッダ(Goでは別に確保したbitmap)にフラグを建てることで表現します．
では灰色の「探索候補」とは何でしょう？

並行GCではマークフェーズとミューテータによるオブジェクトの操作が交互に行われるため，前回のマークフェーズにどこまで探索したのかを記録しておかなければなりません．
そこで，Goではルートから直接オブジェクトをマークしていくのではなく，一度探索対象のオブジェクトをキューに詰めるという作業を挟みます．このときオブジェクトは灰色の状態になります．
そして，キューからオブジェクトを取り出し，マークをした(黒に塗った)あと，そのオブジェクトがさらに参照しているオブジェクトをキューに詰めます．

しかし，ミューテータによって参照関係が変えられたり，新しいオブジェクトが追加されたりした場合はどうなるでしょうか．

コレクタはミューテータによって参照構造が書き換わったとしてもルートから辿れるオブジェクトすべてを黒にしなければなりません．
このような事故を防ぐために，ミューテータ自身も新しくオブジェクトを確保した場合はすぐに黒に塗ったり，参照関係を変更したときは灰色オブジェクトから到達可能な状況になくなるかどうかを判断してそのオブジェクトをキューに詰めたりと，コレクタが次のマークフェーズで生存オブジェクトを見失わないようにします(WriteBarrier)⁵．

このようにしてコレクタは見落としの無いようにオブジェクトをマークしていき，キューが空になるか，一定回のマークフェーズの後，ガッとすべてをマークしてスイープ側に処理を譲ります．

最後に

Goのruntimeは一部アセンブリもありますがほとんどがGoで書かれていたり，コメントがしっかり書いてあったりして，比較的読みやすいように思えたのですが，そもそも概念が難しいのでなかなか理解が進みません．
間違いがある場合はぜひご指摘よろしくお願い致します．

参考文献

• 「ガベージコレクションのアルゴリズムと実装」
• 「ガベージコレクション 自動メモリ管理を構成する理論と実装」
• https://deeeet.com/writing/2016/05/08/gogc-2016/
• https://engineering.linecorp.com/ja/blog/go-gc/
• https://github.com/golang/go/blob/4e15604ada/src/runtime/mgc.go

1. Garbage Collection ↩

2. https://golang.org/doc/go1.5 ↩

3. https://talks.golang.org/2015/go-gc.pdf ↩

4. Sweepフェーズはこのときすでに非同期で実行されていました ↩

5. https://github.com/golang/go/blob/db16de920370892b0241d3fa0617dddff2417a4d/src/runtime/mbarrier.go ↩