Yoshi Yamaguchi

Getting to Go：Goのガベージコレクタが歩んできた道

Getting to Go: The Journey of Go’s Garbage Collector by Rick Hudson

これは、2018年6月18日に開催されたInternational Symposium on Memory Management (ISMM) で私が行った基調講演の書き起こしです。ISMMはこの25年間、メモリ管理とガベージコレクションに関する論文を発表する最も権威ある場であり続けてきました。そこで基調講演をする機会をいただけたことを光栄に思います。

概要

Go言語の機能、目標、そしてユースケースは、私たちにガベージコレクションのスタック全体を根本から考え直すことを強い、驚くべき場所へと私たちを導きました。この旅はスリリングなものでした。この講演では私たちのその旅について語ります。それはオープンソースであることと、Googleのプロダクション環境からの要求に突き動かされた旅です。中には行き止まりの峡谷への寄り道もありましたが、数字が私たちを正しい道へと導いてくれました。この講演では、私たちがどのように、そしてなぜこの旅をしてきたのか、2018年現在私たちがどこにいるのか、そして次の旅路に向けたGoの準備について、洞察を提供します。

経歴

Richard L. Hudson（Rick）は、メモリ管理に関する研究で最もよく知られています。Train、Sapphire、Mississippi Deltaといったアルゴリズムの考案に加えて、Modula-3、Java、C#、Goのような静的型付け言語でのガベージコレクションを可能にしたGCスタックマップの考案者でもあります。Rickは現在Googleの Goチームのメンバーとして、Goのガベージコレクションとランタイムに関する課題に取り組んでいます。

連絡先はrlh@golang.orgです。

コメントは、golang-devでの議論を参照してください。

書き起こし

ismmkeynote_image63

Rick Hudsonです。

この講演はGoランタイム、特にガベージコレクタについてのものです。用意した資料はだいたい45分から50分程度で、そのあとディスカッションの時間を設けます。講演のあとも会場に残っていますので、気軽に声をかけてください。

ismmkeynote_image24

始める前に、何人かの方に謝辞を述べたいと思います。

この講演の中身の多くはAustin Clementsによるものです。CambridgeのGoチームの他のメンバーである、Russ、Than、Cherry、Davidも、刺激的で、エキサイティングで、一緒に仕事をしていて楽しい仲間たちです。

また、世界中の160万人のGoユーザーにも感謝したいと思います。彼らが興味深い問題を私たちに提供してくれなければ、こうした問題の多くは明るみに出ることはなかったでしょう。

そして最後に、長年にわたって素敵なGopherたちを生み出してくれたRenee Frenchにも謝辞を送ります。この講演を通じて彼女の作品をいくつも目にすることになるでしょう。

ismmkeynote_image38

本題に入る前に、GCから見たGoがどのようなものかをお見せしなければなりません。

ismmkeynote_image32

まず第一に、Goのプログラムは数十万ものスタックを持っています。これらはGoのスケジューラによって管理されており、GCのセーフポイントで常にプリエンプトされます。GoのスケジューラはゴルーチンをOSのスレッドに多重化し、理想的には1つのハードウェアスレッドにつき1つのOSスレッドが動作するようにします。私たちはスタックをコピーし、スタック内のポインタを更新することでスタックとそのサイズを管理しています。これはローカルな操作なので、かなりうまくスケールします。

ismmkeynote_image22

次に重要なのは、Goがほとんどのマネージドランタイム言語の伝統である参照指向言語ではなく、Cのようなシステム言語の伝統に連なる値指向の言語であるという事実です。例えば、これは tar パッケージのある型がメモリ上でどのようにレイアウトされているかを示しています。すべてのフィールドは Reader の値に直接埋め込まれています。これによって、プログラマは必要なときにメモリレイアウトをより細かく制御できます。関連する値を持つフィールドを隣接させることができ、キャッシュの局所性にも役立ちます。

値指向であることは外部関数インターフェース（FFI）においても役立ちます。私たちはCおよびC++との高速なFFIを持っています。Googleには膨大な数の便利な機能がありますが、それらはC++で書かれています。Goはそれらすべてをわざわざ書き直す余裕はなかったので、外部関数インターフェースを通じてこれらのシステムにアクセスできる必要がありました。

このたった一つの設計判断が、ランタイムで行われなければならないいくつかの驚くべき事柄につながっています。これはおそらく、Goを他のガベージコレクション付き言語と区別する最も重要な点でしょう。

ismmkeynote_image60

もちろんGoにはポインタがありますし、実際には内部ポインタも持てます。こうしたポインタは値全体を生存させ続けますし、かなりよく使われています。

ismmkeynote_image29

私たちはアヘッド・オブ・タイム（AOT）コンパイル方式を採用しており、バイナリにはランタイム全体が含まれています。

JITによる再コンパイルはありません。これには一長一短あります。まず、プログラムの実行の再現性がずっと容易になり、コンパイラの改善を進めるのがずっと速くなります。

悲しい面としては、JIT方式のシステムのようなフィードバック最適化を行う機会がないことです。

というわけで、一長一短があるのです。

ismmkeynote_image13

GoにはGCを制御するための2つのつまみが用意されています。1つ目は GCPercent です。これは基本的に、どれだけのCPUを使いたいか、どれだけのメモリを使いたいかを調整するつまみです。デフォルト値は100で、これはヒープの半分が生存中のメモリに割り当てられ、残りの半分が新規のアロケーションに割り当てられることを意味します。この値はどちらの方向にも変更できます。

MaxHeap はまだリリースされていませんが、社内では既に使用と評価が進められています。これはプログラマがヒープサイズの上限を設定できるようにするものです。メモリ不足（OOM）はGoにとって厳しい問題です。メモリ使用量の一時的な急増は、プロセスを中断するのではなくCPUコストを増やすことで対処すべきです。基本的に、GCがメモリの圧迫を検知すると、アプリケーションに負荷を減らすよう伝えます。状況が正常に戻れば、GCはアプリケーションに通常の負荷に戻ってよいと伝えます。MaxHeap はスケジューリングにおいてもより多くの柔軟性を提供します。常にどれだけメモリが使えるかを気にし続けるのではなく、ランタイムは MaxHeap までヒープサイズを大きくできるのです。

これでガベージコレクタにとって重要なGoの各要素についての説明は終わりです。

ismmkeynote_image3

それでは、Goランタイムについて、そして私たちがどうやってここまで辿り着いたのか、今いる場所にどうやって至ったのかを話しましょう。

ismmkeynote_image59

2014年当時の話です。もしGoがこのGCのレイテンシ問題を何とか解決できなければ、Goは成功しないだろう。それは明らかでした。

他の新しい言語も同じ問題に直面していました。Rustのような言語は別の道を選びましたが、ここではGoが辿った道についてお話しします。

なぜレイテンシがそれほど重要なのでしょうか？

ismmkeynote_image7

この点について、数学はまったく容赦がありません。

「99%の確率でGCサイクルが10ミリ秒未満で終わる」といった、単体のGCレイテンシに関する99パーセンタイルのサービスレベル目標（SLO）は、単純にスケールしません。重要なのは、セッション全体を通じてのレイテンシ、あるいは1日に何度もアプリを使う過程全体でのレイテンシです。複数のWebページを閲覧するセッションが最終的に100回のサーバーリクエストを発生させる、あるいは1回のセッションで20回のリクエストを発生させ、1日に5回セッションが積み重なるとします。この状況では、セッション全体を通して一貫して10ミリ秒未満の体験を得られるユーザーはわずか37%にしかなりません。

私たちが提案しているように、99%のユーザーに10ミリ秒未満の体験をしてもらいたいのであれば、数学的には4ナイン、つまり99.99パーセンタイルを目標にする必要があります。

2014年、Jeff Deanがちょうど「The Tail at Scale」という論文を発表し、この問題をさらに深く掘り下げていました。この論文はGoogle社内で広く読まれていました。というのも、今後Googleがそのスケールでスケールしていこうとするうえで、深刻な意味合いを持っていたからです。

私たちはこの問題を「ナインの圧政（tyranny of the 9s）」と呼んでいます。

ismmkeynote_image36

では、この「ナインの圧政」とどう戦えばよいのでしょうか。

2014年当時、さまざまな対策が取られていました。

10個の答えが欲しければ、それより多く要求しておいて、最初に返ってきた10個を検索結果ページに載せる。リクエストが50パーセンタイルを超えたら、再発行するか別のサーバーに転送する。GCが実行されそうになったら、新しいリクエストを拒否するか、GCが終わるまで別のサーバーに転送する。といった具合です。

これらはすべて、非常に頭のいい人たちが現実の問題に対して編み出した回避策ですが、GCレイテンシという根本問題には手を付けていませんでした。Googleの規模では、この根本問題に取り組まなければなりませんでした。なぜでしょうか。

ismmkeynote_image48

冗長化ではスケールしません。冗長化には大きなコストがかかります。新しいサーバーファームを必要とするコストです。

私たちはこの問題を解決できることを願っていましたし、これをサーバーのエコシステムを改善する機会だと捉えていました。そしてその過程で、絶滅の危機に瀕したトウモロコシ畑をいくらか救い、独立記念日（7月4日）までに膝の高さまで育つはずのトウモロコシの粒に、その本来の可能性を発揮するチャンスを与えられればと考えていました。

ismmkeynote_image56

これが2014年のSLOです。正直に言うと、私は控えめな目標を設定していました。当時チームに入ったばかりで、このプロセス自体が私にとって初めてのものだったので、過剰な約束をしたくなかったのです。

さらに、他の言語のGCレイテンシに関する発表は、はっきり言って恐ろしいものでした。

ismmkeynote_image67

当初の計画は、リードバリアなしの並行コピーGCを実現することでした。それが長期的な計画でした。リードバリアのオーバーヘッドについては不確実な点が多かったため、Goはそれを避けたいと考えていました。

しかし2014年当時、短期的にはまず体制を整える必要がありました。ランタイムとコンパイラのすべてをGoに書き換えなければなりませんでした。当時それらはCで書かれていました。もうCコードは要りません。GCを理解していないのに文字列のコピー方法について格好いいアイデアを持っているCのコーダーに起因する、いつまでも尾を引くバグもなくなります。また、レイテンシに焦点を当てた何かを素早く用意する必要がありましたが、そのパフォーマンスへの影響は、コンパイラがもたらす高速化分よりも小さくなければいけませんでした。つまり制約がありました。GCを並行化することで消費してよいのは、基本的にコンパイラの1年分のパフォーマンス改善分だけでした。それが限界でした。Goのプログラムを遅くするわけにはいきませんでした。2014年当時、それは到底受け入れられないことだったのです。

ismmkeynote_image28

そこで私たちは少し後退することにしました。コピーの部分は諦めることにしたのです。

私たちが下した決断は、三色（tri-color）並行アルゴリズムを採用することでした。私はキャリアの初期に、Eliot Mossとともに、Dijkstraのアルゴリズムが複数のアプリケーションスレッドでも機能することを示す論文の証明を行ったことがあります。また、ストップ・ザ・ワールド（STW）の問題を取り除けることも示しており、それが可能であるという証明も持っていました。

私たちはコンパイラの速度、つまりコンパイラが生成するコードの速度についても懸念していました。ライトバリアをほとんどの時間オフにしておけば、コンパイラの最適化への影響は最小限に抑えられ、コンパイラチームは迅速に前進できます。Goには2015年に短期的な成功がどうしても必要でもありました。

ismmkeynote_image55

では、私たちが実際に行ったことのいくつかを見ていきましょう。

私たちはサイズ別に分離されたスパン（size segregated span）を採用しました。内部ポインタが問題だったのです。

ガベージコレクタはオブジェクトの先頭を効率よく見つけ出す必要があります。スパン内のオブジェクトのサイズが分かっていれば、単純にそのサイズに切り下げるだけでオブジェクトの先頭が求まります。

もちろん、サイズ別に分離されたスパンには他にも利点があります。

断片化が少ないこと：Cでの経験に加え、GoogleのTCMallocやHoardだけでなく、私自身IntelのScalable Mallocに深く関わっていました。その経験から、非移動型のアロケータであれば断片化は問題にならないという確信を得ていました。

内部構造：私たちはこれを完全に理解しており、経験もありました。サイズ別に分離されたスパンの実現方法も、競合の少ない、あるいはまったくないアロケーションパスの実現方法も理解していました。

速度：非コピー方式であることは懸念材料ではありませんでした。アロケーションは多少遅くなるかもしれませんが、それでもCと同程度のオーダーです。バンプポインタ方式ほど速くはないかもしれませんが、それで構いませんでした。

また、外部関数インターフェースの問題もありました。オブジェクトを移動させなければ、移動型のコレクタでオブジェクトをピン留めしようとしたり、CとGoのオブジェクトの間に間接参照の層を設けようとしたりする際に遭遇しうる、いつまでも尾を引くバグに対処する必要がなくなります。

ismmkeynote_image5

次の設計上の選択は、オブジェクトのメタデータをどこに置くかでした。ヘッダーを持たない以上、オブジェクトに関するなんらかの情報を持っておく必要がありました。マークビットは別の場所に保持され、マーキングとアロケーションの両方に使われます。各ワードには2ビットが対応付けられており、そのワードの中身がスカラー値なのかポインタなのかを示します。また、そのオブジェクトの中にまだポインタが残っているかどうかも符号化されており、それによってオブジェクトのスキャンを早めに打ち切ることができます。さらに、追加のマークビットとして使ったり、他のデバッグ用途に使ったりできる、もう1ビット分の余分な符号化も用意していました。これはこの仕組みを実際に動かし、バグを見つける上で非常に貴重でした。

ismmkeynote_image19

では、ライトバリアについてはどうでしょうか。ライトバリアはGCの実行中だけオンになります。それ以外のときは、コンパイル済みのコードがグローバル変数をロードして参照するだけです。GCは通常オフになっているため、ハードウェアはライトバリアを迂回する分岐を正しく投機実行してくれます。GCの中にいるときはその変数の値が異なっており、ライトバリアは三色アルゴリズムの操作中に到達可能なオブジェクトが失われないようにする役割を担っています。

ismmkeynote_image50

このコードのもう一つの重要な部品がGCペーサーです。これはAustinによる素晴らしい仕事の一つです。基本的には、GCサイクルを開始する最適なタイミングを決定するフィードバックループに基づいています。システムが定常状態にあり、局面の変化がなければ、マーキングはちょうどメモリが尽きる頃に終わるようになっています。

しかし常にそうとは限らないため、ペーサーはマーキングの進捗も監視し、アロケーションが並行マーキングを追い越してしまわないようにする必要があります。

必要であれば、ペーサーはアロケーションを遅くしつつマーキングを速めます。大まかに言うと、ペーサーは大量のアロケーションを行っているゴルーチンを止め、そのゴルーチンにマーキングの作業をさせます。その作業量はゴルーチンのアロケーション量に比例します。これによってガベージコレクタは高速化される一方、ミューテータは遅くなります。

これらすべてが終わると、ペーサーは今回のGCサイクルとそれ以前のサイクルから学んだことをもとに、次のGCをいつ開始すべきかを予測します。

実際にはこれ以上に多くのことをしていますが、これが基本的な考え方です。

この数学的な部分は本当に魅力的なので、設計ドキュメントが欲しければ私に連絡してください。並行GCに取り組んでいるのであれば、ぜひこの数学に目を通して、自分たちの数学と同じかどうか確かめてみるべきです。何か提案があれば教えてください。

*Go 1.5 concurrent garbage collector pacing と Proposal: Separate soft and hard heap size goal

ismmkeynote_image40

そう、私たちには成功がありました。それもたくさん。もっと若く、もっとクレイジーだった頃のRickなら、これらのグラフのいくつかを肩にタトゥーとして彫っていたかもしれません。それくらい誇らしいものでした。

ismmkeynote_image20

これはTwitterの本番サーバーについて作成された一連のグラフです。もちろん私たちはその本番サーバーには一切関与していません。Brian Hatfieldがこれらの計測を行い、奇妙なことに、それについてツイートしていました。

Y軸はミリ秒単位のGCレイテンシです。X軸は時間です。各点はそのGCにおけるストップ・ザ・ワールドの停止時間を表しています。

2015年8月の最初のリリースでは、300〜400ミリ秒程度から30〜40ミリ秒へと低下しました。これは良い結果で、桁が一つ変わるレベルの改善でした。

ここでY軸のスケールを大きく変更します。0〜400ミリ秒から0〜50ミリ秒にします。

ismmkeynote_image54

これはその6か月後です。この改善は主に、ストップ・ザ・ワールドの間に行っていたO(heap)の処理をすべて体系的に排除したことによるものです。これが2回目の桁の改善で、40ミリ秒から4〜5ミリ秒になりました。

ismmkeynote_image1

そこにはいくつかのバグがあり、それらをマイナーリリースの1.6.3で修正する必要がありました。これによってレイテンシは私たちのSLOであった10ミリ秒を大きく下回るまで低下しました。

ここで再びY軸を変更します。今度は0〜5ミリ秒にします。

ismmkeynote_image68

さて、これは2016年8月、最初のリリースから1年後の状態です。ここでも引き続きO(heap size)のストップ・ザ・ワールド処理を取り除いていきました。ここで扱っているのは18ギガバイトのヒープです。実際にはもっと大きなヒープもありましたが、O(heap size)のストップ・ザ・ワールド停止を取り除いていくにつれ、レイテンシに影響を与えることなくヒープサイズを大幅に大きくできるようになりました。これは1.7でのちょっとした助けになりました。

ismmkeynote_image58

次のリリースは2017年3月でした。ここで大きなレイテンシの低下としては最後のものがありました。それは、GCサイクルの終わりで行っていたストップ・ザ・ワールドでのスタックスキャンを回避する方法を見つけたことによるものです。これによってサブミリ秒の範囲まで低下しました。ここでも再びY軸が1.5ミリ秒に変わり、3回目の桁の改善が見て取れます。

ismmkeynote_image45

2017年8月のリリースでの改善はわずかでした。残っているポーズの原因は分かっています。ここでのSLOの内々の目標値はおよそ100〜200マイクロ秒で、私たちはそこを目指していくつもりです。もし数百マイクロ秒を超えるものを目にしたら、ぜひ私たちに教えてください。それが私たちが把握している事象に当てはまるものなのか、まだ調査していない新しい何かなのかを見極めたいと思います。いずれにせよ、これ以上レイテンシを下げてほしいという要望はあまりないようです。こうしたレベルのレイテンシは、GCとは関係のないさまざまな理由によって発生しうるということは重要な点です。よく言われるように、「クマより速く走る必要はない、隣にいる人より速ければいい」のです。

2018年2月の1.10リリースでは大きな変更はなく、いくらかの整理とコーナーケースの追いかけだけでした。

ismmkeynote_image6

新しい年になり、新しいSLOです。これが私たちの2018年のSLOです。

全体のCPU使用量から、GCサイクル中に使用するCPU使用量へと目標を切り替えました。

ヒープは引き続き2倍のままです。

現在、GCサイクルあたりのストップ・ザ・ワールドの停止時間を500マイクロ秒にするという目標を掲げています。これも多少控えめな数字かもしれません。

アロケーションは引き続きGCアシストに比例します。

ペーサーはずっと良くなったので、定常状態ではGCアシストが最小限に抑えられることを目指しています。

私たちはこれにかなり満足していました。繰り返しになりますが、これはSLAではなくSLOです。つまり合意事項ではなく目標です。OSのような要素は私たちにはコントロールできないからです。

ismmkeynote_image64

良い話はここまでです。次は私たちの失敗について話していきましょう。これらは私たちの傷跡であり、いわばタトゥーのようなもので、誰もが持っているものです。とはいえ、失敗にはより面白い話がついてくるものなので、そうした話をいくつかしていきましょう。

ismmkeynote_image46

私たちの最初の試みは、リクエスト指向コレクタ（request oriented collector、ROC）と呼ばれるものでした。その仮説はここに示されています。

ismmkeynote_image34

これはどういうことでしょうか。

ゴルーチンはGopherのような見た目をした軽量スレッドです。ここでは2つのゴルーチンがあります。それらは中央にある2つの青いオブジェクトのように、いくつかのものを共有しています。それぞれが自分専用のスタックと、自分専用のオブジェクト群を持っています。左側のゴルーチンが緑のオブジェクトを共有したいとしましょう。

ismmkeynote_image9

そのゴルーチンはオブジェクトを共有領域に置き、もう一方のゴルーチンがアクセスできるようにします。共有ヒープ上の何かに結びつけたり、グローバル変数に代入したりすることで、もう一方のゴルーチンからも見えるようになります。

ismmkeynote_image26

そして最後に、左側のゴルーチンは死の床につきます。まもなく終了しようとしています。悲しいことです。

ismmkeynote_image14

ご存知の通り、死ぬときに自分のオブジェクトを持っていくことはできません。スタックも持っていけません。実はこの時点でスタックは空になっており、それらのオブジェクトは到達不可能になっているので、単純に回収してしまえます。

ismmkeynote_image2

ここで重要なのは、すべての操作がローカルで完結し、グローバルな同期を必要としないという点です。これは世代別GCのようなアプローチとは根本的に異なっており、その同期が不要であることによって得られるスケーラビリティが、私たちにとって十分な勝算になることを期待していました。

ismmkeynote_image27

このシステムにおけるもう一つの問題は、ライトバリアが常にオンになっていたことです。書き込みが発生するたびに、それがプライベートなオブジェクトへのポインタをパブリックなオブジェクトに書き込むものかどうかを確認する必要がありました。もしそうであれば、参照先のオブジェクトをパブリックにし、さらに到達可能なオブジェクトを推移的にたどって、それらもすべてパブリックにする必要がありました。これはかなりコストの高いライトバリアで、多くのキャッシュミスを引き起こしかねないものでした。

ismmkeynote_image30

とはいえ、いくつかかなり良い成功も収めました。

これはエンドツーエンドのRPCベンチマークです。ラベル付けを間違えたY軸は0から5ミリ秒までを表しています（値が小さいほど良い）。まあそういうものだと思ってください。X軸は基本的にバラスト、つまりインコアデータベースの大きさを表しています。

ご覧の通り、ROCをオンにして共有があまり多くない場合、実際にかなりうまくスケールしています。ROCをオンにしていない場合は、それほど良い結果にはなりませんでした。

ismmkeynote_image35

しかしそれだけでは十分ではありませんでした。ROCがシステムの他の部分を遅くしないことも確認しなければならなかったのです。当時、私たちのコンパイラについては大きな懸念があり、コンパイラを遅くするわけにはいきませんでした。残念なことに、コンパイラはまさにROCが苦手とするタイプのプログラムでした。30%、40%、50%、あるいはそれ以上の速度低下が見られ、それは受け入れられないものでした。Goはコンパイラの速さを誇りにしているので、コンパイラを、しかもこれほどまでに遅くするわけにはいきませんでした。

ismmkeynote_image61

そこで私たちは他のプログラムについても調べてみました。これらは私たちのパフォーマンスベンチマークです。私たちは200から300ほどのベンチマーク群を持っており、これらはコンパイラチームが取り組んで改善すべきだと判断したものでした。GCチームが選んだものではまったくありません。結果は軒並み悪く、ROCが勝者になることはありませんでした。

ismmkeynote_image44

確かにスケールはしましたが、私たちが持っていたのは4から12ハードウェアスレッドのシステムに過ぎず、ライトバリアの税をそれで乗り越えることはできませんでした。おそらく将来、128コアのシステムが登場し、Goがそれを活用できるようになれば、ROCのスケーリング特性が勝算になるかもしれません。その時が来たら、この件に立ち戻ってくるかもしれませんが、現時点ではROCは分の悪い賭けでした。

ismmkeynote_image66

では次に何をすべきか。世代別GCを試してみましょう。古くからある、しかし良いものです。ROCがうまくいかなかったので、私たちがずっと多くの経験を持っているものに立ち返ることにしました。

ismmkeynote_image41

私たちはレイテンシを犠牲にするつもりはありませんでしたし、非移動型であるという性質も手放すつもりはありませんでした。そのため、非移動型の世代別GCが必要でした。

ismmkeynote_image27

では、それは実現できるのでしょうか。答えはイエスです。ただし世代別GCでは、ライトバリアは常にオンになります。GCサイクルが実行中のときは今日使っているのと同じライトバリアを使いますが、GCがオフのときは、ポインタをバッファに溜めておき、あふれたらそれをカードマークテーブルに書き出す、高速なGC用ライトバリアを使います。

ismmkeynote_image4

では、これは非移動型の状況でどのように機能するのでしょうか。これがマーク／アロケーションマップです。基本的には現在位置を示すポインタを保持しておきます。アロケーションを行う際には次のゼロを探し、そのゼロが見つかったらその場所にオブジェクトを割り当てます。

ismmkeynote_image51

それから現在位置のポインタを次のゼロの位置に更新します。

ismmkeynote_image17

これをある時点で世代別GCを行うタイミングになるまで続けます。マーク／アロケーションのベクトルの中に1が立っていれば、そのオブジェクトは前回のGCの時点で生存していた、つまり成熟した（mature）オブジェクトだと分かります。0であり、そこに到達したのであれば、それは若い（young）オブジェクトだと分かります。

ismmkeynote_image53

では、どのように昇格（promoting）を行うのでしょうか。1でマークされたものが0でマークされたものを指しているのを見つけたら、その参照先を単純にゼロから1に変えることで昇格させます。

ismmkeynote_image49

到達可能なオブジェクトがすべて昇格されるように、推移的にたどっていく必要があります。

ismmkeynote_image69

到達可能なオブジェクトがすべて昇格されたら、マイナーGCは終了します。

ismmkeynote_image62

最後に、世代別GCのサイクルを終えるには、現在位置のポインタをベクトルの先頭に戻すだけでよく、そのまま処理を続けられます。そのGCサイクル中に到達しなかったゼロはすべて空きであり、再利用できます。多くの方がご存知の通り、これは「スティッキービット（sticky bits）」と呼ばれるもので、Hans Boehmと彼の同僚たちによって考案されました。

ismmkeynote_image21

それでパフォーマンスはどうだったのでしょうか。大きなヒープに関しては悪くありませんでした。これらはGCが得意とするはずのベンチマークです。ここまでは順調でした。

ismmkeynote_image65

そこで私たちのパフォーマンスベンチマークで実行してみたところ、あまりうまくいきませんでした。いったい何が起きていたのでしょうか。

ismmkeynote_image43

ライトバリアは高速でしたが、単純に十分な速さではありませんでした。さらに、最適化を行うのも困難でした。例えば、オブジェクトがアロケートされてから次のセーフポイントまでの間に初期化のための書き込みがあれば、ライトバリアの省略（elision）が可能になります。しかし私たちは、あらゆる命令でGCセーフポイントを持つシステムへと移行しつつあったため、今後省略できるライトバリアは実質的になくなっていました。

ismmkeynote_image47

私たちにはエスケープ解析もあり、それはどんどん良くなっていました。先ほどお話しした値指向の話を覚えているでしょうか。関数にポインタを渡す代わりに、実際の値を渡すのです。値を渡しているため、エスケープ解析は手続き間解析ではなく、手続き内解析だけで済みます。

もちろん、ローカルオブジェクトへのポインタがエスケープする場合には、そのオブジェクトはヒープに割り当てられます。

世代別仮説がGoに当てはまらないというわけではありません。単に、若いオブジェクトはスタック上で生まれてすぐに死んでいくのです。その結果、世代別コレクションは他のマネージドランタイム言語で見られるほどの効果を発揮しません。

ismmkeynote_image10

こうしてライトバリアに不利に働く力が集まり始めていました。今日、私たちのコンパイラは2014年当時よりもずっと良くなっています。エスケープ解析は、世代別コレクタが役立ったであろうような多くのオブジェクトを検出し、スタック上に留めています。私たちはユーザーがエスケープしているオブジェクトを見つける手助けとなるツールを作り始めました。もしそれがちょっとしたものであれば、ユーザーはコードを変更して、コンパイラがそのオブジェクトをスタックに割り当てられるように手助けできます。

ユーザーは値指向のアプローチを取り入れることに関してどんどん賢くなっており、ポインタの数は減ってきています。配列やマップは構造体へのポインタではなく値そのものを保持するようになっています。すべて順調です。

しかし、Goにおいてライトバリアが今後も厳しい戦いを強いられる主な理由は、それだけではありません。

ismmkeynote_image8

このグラフを見てみましょう。これは単にマークコストについての分析グラフです。各線は、それぞれ異なるマークコストを持ちうるアプリケーションを表しています。マークコストが20%だとしましょう。これはかなり高い値ですが、あり得ないことではありません。赤い線は10%で、これもまだ高い値です。下の線は5%で、これは今日のライトバリアのコストに近い値です。では、ヒープサイズを2倍にするとどうなるでしょうか。それが右側の点です。GCサイクルの頻度が下がるため、マークフェーズの累積コストはかなり下がります。ライトバリアのコストは一定なので、ヒープサイズを大きくすることで、そのマーキングコストはライトバリアのコストを下回るようになります。

ismmkeynote_image39

こちらはより一般的なライトバリアのコストである4%の場合です。この場合でも、単にヒープサイズを大きくするだけで、マークバリアのコストをライトバリアのコストより下げられることが分かります。

世代別GCの本当の価値は、GC時間だけを見た場合、ライトバリアのコストがミューテータ全体に薄く広がっているために無視されるという点にあります。これが世代別GCの大きな利点であり、フルGCサイクルの長いSTW時間を大幅に削減しますが、必ずしもスループットを改善するわけではありません。Goにはこのストップ・ザ・ワールドの問題がなかったため、私たちはスループットの問題により注意深く目を向ける必要があり、実際にそうしてきました。

ismmkeynote_image23

たくさんの失敗を経験しましたが、そうした失敗にはランチや食事がついてきます。私はいつものように「ああ、ライトバリアさえなければどんなに素晴らしいことか」とぼやいていました。

その頃、AustinはGoogle社内のハードウェアGC担当の何人かと1時間ほど話をしてきたところで、彼らと話をして、役立ちそうなハードウェアGCサポートを実現する方法を考えるべきだと言っていました。それを聞いて私は、ゼロ埋めキャッシュラインや、再開可能なアトミックシーケンスなど、大手ハードウェア企業で働いていた頃に実現しなかった話を昔語りし始めました。確かにItaniumというチップにはいくつかの機能を入れ込むことができましたが、今日のもっと一般的なチップに入れることはできませんでした。この話の教訓は、単純に手元にあるハードウェアを使うしかない、ということです。

とにかくそんな話をしているうちに、何か突飛なことをやってみたらどうだろうという話になりました。

ismmkeynote_image25

ライトバリアなしでカードマーキングをするというのはどうでしょうか。実はAustinはいくつかのファイルを持っていて、そこにはなぜか私には教えてくれない、彼の突飛なアイデアがすべて書き込まれているのです。ある種のセラピーのようなものだと思っています。私もかつてEliotと同じようなことをしていました。新しいアイデアは簡単に叩き潰されてしまうものなので、世に出す前にそれを守り、鍛えておく必要があるのです。ともあれ、彼はそこからこのアイデアを取り出してきました。

そのアイデアとは、各カードごとに成熟したポインタのハッシュを保持しておくというものです。あるカードにポインタが書き込まれると、そのハッシュ値が変化し、そのカードはマークされたとみなされます。これはライトバリアのコストをハッシュ計算のコストと交換することになります。

ismmkeynote_image31

しかしそれ以上に重要なのは、これがハードウェアの特性に合致しているという点です。

今日の最新のアーキテクチャにはAES（Advanced Encryption Standard）命令が備わっています。この命令の一つを使えば暗号強度のハッシュ計算ができ、標準的な暗号方式のポリシーに従っている限り、暗号強度のハッシュであれば衝突を心配する必要もありません。ですのでハッシュ計算自体にはあまりコストがかかりませんが、ハッシュ計算の対象となるデータを読み込んでくる必要はあります。幸い私たちはメモリを順番に走査しているので、メモリおよびキャッシュのパフォーマンスは良好です。DIMMがあり、連続したアドレスにアクセスするのであれば、ランダムなアドレスにアクセスするより速くなるので有利です。ハードウェアのプリフェッチャーも働いてくれて、これも助けになります。ともあれ、私たちには、Fortranを動かすため、Cを動かすため、そしてSPECintベンチマークを動かすために、50年、60年かけてハードウェアを設計してきた歴史があります。その結果として、こうした処理を高速に実行できるハードウェアが出来上がっているのも当然のことです。

ismmkeynote_image12

実際に計測してみました。かなり良い結果です。これは大きなヒープ向けのベンチマークスイートなので、良い結果になるはずのものです。

ismmkeynote_image18

では、パフォーマンスベンチマークではどうだったのでしょうか。あまり良くなく、いくつか外れ値がありました。しかしこれによって、ライトバリアをミューテータ内で常時オンにしておく方式から、GCサイクルの一部として実行する方式へと移すことができました。世代別GCを行うかどうかの判断は、GCサイクルの開始時まで先送りできるようになりました。カードに関する作業を局所化したことで、そこでのコントロールが増しています。この仕組みが手に入ったので、あとはペーサーに任せることができ、ペーサーは右側に外れて世代別GCの恩恵を受けられないプログラムを動的に切り捨てるという役目をうまく果たしてくれます。しかしこれは今後も勝ち続けられるのでしょうか。今後ハードウェアがどうなっていくのかを知っておく、あるいは少なくとも考えておく必要があります。

ismmkeynote_image52

未来のメモリはどのようなものになるのでしょうか。

ismmkeynote_image11

このグラフを見てみましょう。これは定番のムーアの法則のグラフです。Y軸は対数スケールで、1つのチップに搭載されているトランジスタの数を表しています。X軸は1971年から2016年までの年です。これらの年はどこかの誰かが「ムーアの法則は終わった」と予言した年でもあることを付け加えておきます。

デナードスケーリングは10年ほど前に周波数の改善を終わらせました。新しいプロセスの立ち上げにはより長い時間がかかるようになっています。かつては2年ごとだったものが、今では4年かそれ以上になっています。ですので、私たちがムーアの法則の減速期に入りつつあることは、かなり明らかです。

赤い丸で囲まれたチップに注目してみましょう。これらはムーアの法則を最もよく維持しているチップです。

これらはロジックがますます単純になり、何度も複製されているチップです。数多くの同一のコア、複数のメモリコントローラやキャッシュ、GPU、TPUなどがその例です。

単純化と複製を進めていくと、最終的には数本の配線と1つのトランジスタ、1つのコンデンサに漸近的に行き着きます。つまり、DRAMのメモリセルです。

言い換えると、コアの数を倍にするよりも、メモリの容量を倍にするほうが良い価値を生むと私たちは考えています。

元のグラフ は www.kurzweilai.net/ask-ray-the-future-of-moores-law にあります。

ismmkeynote_image57

次にDRAMに焦点を当てた別のグラフを見てみましょう。これはカーネギーメロン大学（CMU）の最近の博士論文からの数値です。これを見ると、ムーアの法則は青い線で表されています。赤い線は容量で、これはムーアの法則に従っているように見えます。奇妙なことに、私はドラムメモリを使っていた1939年まで遡るグラフを見たことがあり、そのときも容量とムーアの法則は一緒に歩調を合わせていました。つまりこのグラフはずっと以前から続いているもので、おそらくこの会場にいる誰よりも長く続いているものです。

このグラフをCPUの周波数や、さまざまな「ムーアの法則は死んだ」グラフと比較すると、メモリ、少なくともチップの容量については、CPUよりも長くムーアの法則に従い続けるだろうという結論に至ります。黄色い線である帯域幅は、メモリの周波数だけでなく、チップから取り出せるピンの数にも関係しているため、それほど追いついていませんが、悪くもありません。

緑の線であるレイテンシは、かなり悪い結果です。ただし、シーケンシャルアクセスのレイテンシはランダムアクセスのレイテンシよりも良い結果を示していることは付け加えておきます。

（データの出典：“Understanding and Improving the Latency of DRAM-Based Memory Systems”、Kevin K. Chang氏がElectrical and Computer Engineeringの博士号取得のために提出した論文より。Carnegie Mellon University、Pittsburgh, PA、2017年5月。Kevin K. Changの論文を参照してください。導入部にあった元のグラフは、ムーアの法則の線を簡単に引ける形式ではなかったため、X軸をより均一になるように変更しました。）

ismmkeynote_image15

ここからは、実際に現実と向き合う話をしましょう。これは実際のDRAMの価格で、2005年から2016年にかけて全体的に下落しています。2005年を選んだのは、その頃がちょうどデナードスケーリングが終わり、それに伴って周波数の改善も終わった時期だからです。

赤い丸で囲まれた部分、つまり基本的に私たちがGoのGCレイテンシを削減する作業をしてきた期間を見てみると、最初の数年は価格が順調に下がっていたことが分かります。しかし最近はあまり良くなく、需要が供給を上回ったことで、この2年間は価格が上昇しています。もちろんトランジスタが大きくなったわけではなく、むしろチップの容量が増えているケースもあるので、これは市場の力によるものです。RAMBUSをはじめとするチップメーカーは、今後2019年から2020年にかけて次のプロセスの微細化が見られるだろうと言っています。

メモリ業界における世界的な市場動向について推測するのはこれくらいにしておきますが、価格は循環的なものであり、長期的には供給が需要に追いついていく傾向があるということだけは指摘しておきます。

長期的には、メモリの価格はCPUの価格よりもずっと速いペースで下落していくだろうと私たちは考えています。

（出典：https://hblok.net/blog/ および https://hblok.net/storage_data/storage_memory_prices_2005-2017-12.png）

ismmkeynote_image37

こちらの別の線を見てみましょう。この線に乗れたらいいのですが。これはSSDの線です。こちらのほうが価格を低く保てています。これらのチップの物理的な材料はDRAMよりもずっと複雑です。ロジックもより複雑で、1セルあたり1トランジスタではなく、半ダースほどのトランジスタが必要です。

今後は、DRAMとSSDの間に、Intelの3D XPointや相変化メモリ（PCM）といったNVRAMが位置することになるでしょう。今後10年でこの種のメモリの利用可能性が高まり、より主流になっていくと考えられ、これはメモリを追加することがサーバーに価値を追加する安価な方法であるという考えをさらに裏付けるものになるでしょう。

さらに重要なことに、DRAMに代わる競合する選択肢が他にも登場してくることが予想されます。5年後、10年後にどれが優位に立つかを知っているふりをするつもりはありませんが、競争は激しくなり、ヒープメモリはここで強調している青いSSDの線に近づいていくでしょう。

こうしたことすべてが、常時オンのバリアを避け、メモリを増やす方向を選ぶという私たちの決断を裏付けています。

ismmkeynote_image16

では、これらすべてが今後のGoにとって何を意味するのでしょうか。

ismmkeynote_image42

私たちは、ユーザーから寄せられるコーナーケースを検討しながら、ランタイムをより柔軟かつ堅牢なものにしていくつもりです。スケジューラを引き締め、決定性と公平性を向上させたいと考えていますが、パフォーマンスを犠牲にするつもりはありません。

また、GCのAPIの範囲を広げるつもりもありません。この10年近く、私たちには2つのつまみしかありませんが、それでちょうど良いと感じています。新しいフラグを追加するに値するほど重要なアプリケーションは存在していません。

また、すでにかなり優れているエスケープ解析をさらに改善する方法や、Goの値指向プログラミングに合わせた最適化についても検討していきます。これはプログラミング言語自体だけでなく、ユーザーに提供するツールについても同様です。

アルゴリズムの面では、バリア、特に常時オンになっているバリアの使用を最小限に抑えるような設計空間の部分に注力していきます。

そして最後に、最も重要なこととして、少なくとも今後5年間、できれば今後10年間にわたって、ムーアの法則がCPUよりもRAMを優遇する傾向に乗っていきたいと考えています。

以上です。ありがとうございました。

ismmkeynote_image33

なお、Goチームでは、Goランタイムとコンパイラのツールチェーンの開発や保守を手伝ってくれるエンジニアを募集しています。

興味がある方は、募集中のポジションをご覧ください。

By Rick Hudson