Goブログ
Goへの道：Goのガベージコレクタの軌跡
これは、2018年6月18日に開催された国際メモリ管理シンポジウム（ISMM）での私の基調講演の書き起こしです。過去25年間、ISMMはメモリ管理とガベージコレクションに関する論文を発表する最高の場であり、基調講演に招待されたことは光栄でした。
概要
Go言語の機能、目標、およびユースケースは、ガベージコレクションスタック全体を見直すことを余儀なくさせ、驚くべき場所へと私たちを導きました。この旅は爽快なものでした。この講演では、私たちの旅について説明します。これは、オープンソースとGoogleの生産要求に動機付けられた旅です。数字が私たちを家に導いた、行き止まりの箱型の峡谷への寄り道も含まれています。この講演では、私たちの旅の経緯と理由、2018年現在における私たちの位置、そしてGoの次の旅への準備についての洞察を提供します。
略歴
リチャード L. ハドソン（リック）は、Train、Sapphire、Mississippi Deltaのアルゴリズムの発明、およびModula-3、Java、C#、Goなどの静的型付き言語でのガベージコレクションを可能にしたGCスタックマップを含むメモリ管理の分野での業績で最もよく知られています。リックは現在、GoogleのGoチームのメンバーであり、Goのガベージコレクションとランタイムの問題に取り組んでいます。
連絡先: rlh@golang.org
コメント: golang-devでの議論をご覧ください。
書き起こし
リック・ハドソンです。
これはGoランタイム、特にガベージコレクタに関する講演です。準備された資料が約45〜50分あり、その後、質疑応答の時間がありますので、後でお気軽にお越しください。
始める前に、何人かの人に感謝の意を表したいと思います。
講演での良い部分の多くは、オースティン・クレメンツによって行われました。ケンブリッジのGoチームの他のメンバーであるラス、タン、チェリー、デイビッドも、魅力的で刺激的で楽しいグループでした。
また、世界中の160万人のGoユーザーにも、解決すべき興味深い問題を与えていただいたことに感謝したいと思います。彼らがいなければ、これらの問題の多くは決して明らかにならなかったでしょう。
そして最後に、長年にわたってこれらの素敵なゴーファーを制作してくれたルネ・フレンチにも感謝したいと思います。講演全体で彼らの何人かを目にするでしょう。
この件に取り掛かる前に、GCがGoをどのように見ているかを実際に見る必要があります。
まず第一に、Goプログラムには何十万ものスタックがあります。これらはGoスケジューラによって管理され、常にGCセーフポイントでプリエンプトされます。Goスケジューラは、GoルーチンをOSスレッドに多重化します。これは、1つのOSスレッドが1つのHWスレッドで実行されることを期待します。スタックとそのサイズは、スタックをコピーし、スタック内のポインタを更新することによって管理します。これはローカルな操作であるため、かなりうまくスケールします。
次に重要なことは、Goが、ほとんどのマネージドランタイム言語の慣習である参照指向言語ではなく、Cのようなシステム言語の伝統である値指向言語であるということです。たとえば、これはtarパッケージの型がメモリにどのようにレイアウトされるかを示しています。すべてのフィールドはReader値に直接埋め込まれています。これにより、プログラマーは必要な場合にメモリレイアウトをより詳細に制御できます。関連する値を持つフィールドを配置でき、キャッシュの局所性に役立ちます。
値指向は、外部関数インターフェイスにも役立ちます。CおよびC++との高速なFFIがあります。明らかに、Googleには非常に多くの施設がありますが、それらはC++で記述されています。Goは、これらのすべてをGoで再実装するのを待つことができなかったため、Goは外部関数インターフェイスを介してこれらのシステムにアクセスする必要がありました。
この1つの設計上の決定は、ランタイムで発生しなければならないより驚くべきことにつながりました。これはおそらく、Goを他のGC付き言語と区別する最も重要なことです。
もちろん、Goにはポインタを含めることができ、実際には内部ポインタを含めることもできます。このようなポインタは、値全体をライブ状態に保ち、非常に一般的です。
また、コンパイルシステムを事前に実行するため、バイナリにはランタイム全体が含まれています。
JIT再コンパイルはありません。これにはプラスとマイナスがあります。まず、プログラム実行の再現性がはるかに容易になり、コンパイラの改善を迅速に進めることができます。
残念なことに、JITシステムで行うようなフィードバック最適化を行う機会はありません。
したがって、プラスとマイナスがあります。
Goには、GCを制御するための2つのノブが付属しています。最初の1つはGCPercentです。基本的に、これは使用するCPUと使用するメモリの量を調整するノブです。デフォルトは100で、これはヒープの半分がライブメモリ専用であり、ヒープの半分が割り当て専用であることを意味します。これはどちらの方向にも変更できます。
MaxHeapは、まだリリースされていませんが、内部で評価されているもので、プログラマーが最大ヒープサイズを設定できるようにします。メモリ不足、つまりOOMはGoにとって困難です。メモリ使用量の急な増加は、中止ではなく、CPUコストを増やすことによって処理する必要があります。基本的に、GCがメモリプレッシャーを認識すると、アプリケーションに負荷を軽減するように通知します。状況が正常に戻ると、GCはアプリケーションに通常の負荷に戻ることができることを通知します。MaxHeapは、スケジューリングにおいてもより柔軟性を提供します。常に利用可能なメモリ量について懸念する代わりに、ランタイムはヒープをMaxHeapまでサイズ変更できます。
これで、ガベージコレクタにとって重要なGoの要素に関する説明は終わりです。
それでは、Goランタイムと、私たちがどのようにしてここに至ったか、現在の場所にたどり着いたかについてお話しましょう。
2014年のことです。GoがこのGCレイテンシーの問題を何らかの方法で解決しない限り、Goは成功しないでしょう。それは明らかでした。
他の新しい言語も同じ問題に直面していました。Rustのような言語は異なる道を進みましたが、ここではGoがたどった道について説明します。
なぜレイテンシーがそれほど重要なのでしょうか？
この件に関する計算は完全に容赦ないものです。
99％の時間のGCサイクルが10ミリ秒未満であるなど、99パーセンタイルの分離されたGCレイテンシーサービスレベル目標（SLO）は、スケールアップしません。重要なのは、セッション全体または1日に何度もアプリを使用する過程でのレイテンシーです。1つのセッションで複数のWebページを閲覧し、セッション中に100回のサーバーリクエストを実行するか、20回のリクエストを実行し、1日に5つのセッションを詰め込んだと仮定します。その状況では、セッション全体で一貫して10ミリ秒未満のエクスペリエンスを持つユーザーは37％にすぎません。
提案しているように、ユーザーの99％に10ミリ秒未満のエクスペリエンスを提供したい場合、計算では、実際には4つの9、つまり99.99パーセンタイルをターゲットにする必要があると言っています。
2014年当時、ジェフ・ディーンは、これをさらに掘り下げた「テールアットスケール」という論文を発表したばかりでした。これは、Googleが今後進歩し、Google規模でスケーリングしようとすることに重大な影響を与えたため、Google周辺で広く読まれていました。
私たちはこの問題を「9の暴政」と呼んでいます。
では、9の暴政にどのように立ち向かうのでしょうか？
2014年には多くのことが行われていました。
10個の回答が必要な場合は、さらにいくつか質問して最初の10個を取得し、それらを検索ページに掲載します。リクエストが50パーセンタイルを超える場合は、リクエストを再発行するか、別のサーバーに転送します。GCが実行されそうな場合は、GCが完了するまで新しいリクエストを拒否するか、別のサーバーに転送します。などなど。
これらはすべて、非常に現実的な問題を抱えた非常に賢い人々からの回避策ですが、GCレイテンシーの根本的な問題には対処していません。Google規模では、根本的な問題に対処する必要がありました。なぜ？
冗長性はスケールアップしませんでした。冗長性にはコストがかかります。それは新しいサーバーファームのコストがかかります。
私たちはこの問題を解決できることを期待し、サーバーエコシステムを改善する機会であると捉え、その過程で、絶滅危惧種のトウモロコシ畑をいくつか救い、いくつかのトウモロコシの粒が7月4日までに膝の高さになり、その潜在能力を最大限に発揮する機会を与えることができました。
これが2014年のSLOです。はい、私が過小評価していたのは事実です。私はチームに新しく、私にとっては新しいプロセスであり、過剰な約束をしたくありませんでした。
さらに、他の言語でのGCレイテンシーに関するプレゼンテーションは、ただただ恐ろしいものでした。
当初の計画は、リードバリアフリーの同時コピーGCを行うことでした。それが長期的な計画でした。リードバリアのオーバーヘッドについては多くの不確実性があったため、Goはそれを回避したかったのです。
しかし、2014年の短期的な目標として、我々は体制を立て直す必要がありました。ランタイムとコンパイラをすべてGoに変換する必要がありました。当時はCで書かれていました。Cでのコードはもう不要で、GCを理解していないCコーダーが、文字列のコピー方法についてクールなアイデアを持っているせいで発生するバグの長期的な影響も不要でした。また、迅速に何かを必要としており、レイテンシに焦点を当てる必要がありましたが、パフォーマンスの低下はコンパイラの高速化によってもたらされるスピードアップよりも小さくする必要がありました。そのため、我々は制限されていました。基本的に、GCを並行化することで、1年間分のコンパイラのパフォーマンス向上を吸収できるだけでした。しかし、それが限界でした。Goプログラムを遅くすることはできませんでした。それは2014年には受け入れられなかったでしょう。
そのため、私たちは少し後退しました。コピーの部分はやらないことにしました。
決定は、トライカラー並行アルゴリズムを実行することでした。私のキャリアの初期に、エリオット・モスと私は、ダイクストラのアルゴリズムが複数のアプリケーションスレッドで機能することを証明するジャーナル論文を作成しました。また、STW（stop-the-world）の問題も解決できることを示し、それが可能であるという証拠も持っていました。
また、コンパイラの速度、つまりコンパイラが生成するコードについても懸念していました。書き込みバリアをほとんどの時間オフに保てば、コンパイラの最適化への影響は最小限に抑えられ、コンパイラチームは迅速に進めることができました。Goはまた、2015年に短期的な成功を強く必要としていました。
では、私たちがやったことのいくつかを見てみましょう。
私たちはサイズ分離されたスパンを採用しました。内部ポインタは問題でした。
ガベージコレクタは、オブジェクトの先頭を効率的に見つける必要があります。スパン内のオブジェクトのサイズがわかっていれば、そのサイズに切り下げるだけで、それがオブジェクトの先頭になります。
もちろん、サイズ分離されたスパンには他にも利点があります。
低フラグメンテーション：GoogleのTCMallocやHoardに加えて、Cでの経験として、私はインテルのScalable Mallocに深く関わっており、その作業によって、非移動アロケータではフラグメンテーションが問題にならないという自信を得ることができました。
内部構造：私たちはそれを完全に理解しており、経験もありました。サイズ分離されたスパンのやり方、低またはゼロの競合アロケーションパスのやり方を理解していました。
スピード：非コピーは私たちにとって懸念事項ではありませんでした。アロケーションは確かに遅くなるかもしれませんが、それでもCのオーダーです。バンプポインタほど速くないかもしれませんが、それは問題ありませんでした。
また、この外部関数インターフェースの問題もありました。オブジェクトを移動しない場合、オブジェクトを固定し、Cと作業中のGoオブジェクトの間に間接参照のレベルを置こうとした場合に発生する可能性のある、移動コレクタを使用した場合に遭遇する可能性のあるバグの長期的な影響に対処する必要はありませんでした。
次の設計上の選択は、オブジェクトのメタデータをどこに置くかでした。ヘッダーがないため、オブジェクトに関する情報が必要でした。マークビットは側面に保持され、マーク付けとアロケーションに使用されます。各ワードには、それがスカラーか、そのワード内のポインタかを示すために、2ビットが関連付けられています。また、オブジェクト内にさらにポインタがあるかどうかをエンコードして、オブジェクトのスキャンを早く終了できるようにしました。また、追加のマークビットとして、または他のデバッグを行うために使用できる追加のビットエンコーディングもありました。これは、この機能を実行し、バグを見つけるのに非常に価値がありました。
では、書き込みバリアはどうでしょうか？書き込みバリアはGC中のみオンになります。他の時間では、コンパイルされたコードはグローバル変数をロードしてそれを調べます。GCは通常オフであるため、ハードウェアは書き込みバリアを回避するように正しく推測します。GC内部にいるときは、その変数は異なり、書き込みバリアは、トライカラー操作中に到達可能なオブジェクトが失われないようにする役割を担います。
このコードのもう1つの部分はGCペーサーです。これはオースティンが行った素晴らしい作業の一部です。基本的に、GCサイクルを開始する最適なタイミングを決定するフィードバックループに基づいています。システムが定常状態にあり、位相変化がない場合、メモリがなくなる頃にマーク付けが終了します。
そうでない可能性もあるため、ペーサーはマーク付けの進行状況も監視し、アロケーションが並行マーク付けをオーバーランしないようにする必要があります。
必要に応じて、ペーサーはマーク付けを高速化しながらアロケーションを遅くします。大まかに言うと、ペーサーは多くのアロケーションを行っているゴルーチンを停止し、マーク付けを行うように指示します。作業量は、ゴルーチンのアロケーションに比例します。これにより、ミューテータを遅くしながら、ガベージコレクタを高速化します。
このすべてが完了すると、ペーサーはこのGCサイクルと以前のサイクルから学習したことを活用して、次のGCを開始するタイミングを予測します。
それ以上のこともたくさんありますが、それが基本的なアプローチです。
数学は非常に魅力的です。設計ドキュメントについては私に連絡してください。並行GCを実行している場合は、この数学を調べて、自分の数学と同じかどうかを確認する必要があります。何か提案があれば教えてください。
*Go 1.5 並行ガベージコレクタのペーシング および 提案：ソフトヒープサイズ目標とハードヒープサイズ目標の分離
はい、私たちは成功を収めました。たくさんありました。若くてクレイジーだったリックなら、これらのグラフのいくつかを肩にタトゥーとして入れていたでしょう。それほど誇りに思っていました。
これは、Twitterの本番サーバーで行われた一連のグラフです。もちろん、その本番サーバーとは何の関係もありませんでした。ブライアン・ハットフィールドがこれらの測定を行い、奇妙なことにそれについてツイートしました。
Y軸は、ミリ秒単位でのGCレイテンシを示しています。X軸は時間を示しています。各点は、そのGC中のstop-the-worldポーズ時間です。
2015年8月の最初のリリースでは、約300〜400ミリ秒から30〜40ミリ秒に低下しました。これは良かった、桁違いに良かったです。
ここでは、Y軸を0〜400ミリ秒から0〜50ミリ秒に大幅に変更します。
これは6か月後です。改善の主な理由は、stop-the-world時間中に実行していたすべてのO（ヒープ）処理を体系的に排除したことでした。これは、40ミリ秒から4〜5ミリ秒に移行したため、2桁の改善でした。
1.6.3のマイナーリリース中にクリーンアップする必要があったバグがいくつかありました。これにより、レイテンシは10ミリ秒未満に低下しました。これは、私たちのSLOでした。
ここで、Y軸を再度変更し、今回は0〜5ミリ秒にします。
さて、ここが2016年8月で、最初のリリースから1年後です。ここでも、これらのO（ヒープサイズ）のstop-the-world処理を削減し続けました。ここでは18Gバイトのヒープについて話しています。私たちははるかに大きなヒープを持っており、これらのO（ヒープサイズ）のstop-the-worldポーズを削減するにつれて、レイテンシに影響を与えることなく、ヒープのサイズを大幅に増やすことができることは明らかでした。そのため、これは1.7で少し役立ちました。
次のリリースは2017年3月でした。GCサイクルの最後にstop-the-worldスタックのスキャンを回避する方法を理解したことで、大きなレイテンシの低下の最後がありました。これにより、ミリ秒未満の範囲にまで低下しました。ここでも、Y軸は1.5ミリ秒に変更されようとしており、3桁の改善が見られます。
2017年8月のリリースでは、ほとんど改善が見られませんでした。残りのポーズの原因はわかっています。ここでのSLOのささやき数は約100〜200マイクロ秒であり、私たちはそれに向けて推進していきます。200マイクロ秒を超えるものを見つけた場合は、それが私たちが知っているものに適合するか、または私たちが調査していない何か新しいものかどうかを判断するために、ぜひお話しさせてください。いずれにしても、レイテンシの低下に対する需要はほとんどないようです。これらのレイテンシレベルは、GC以外のさまざまな理由で発生する可能性があることに注意することが重要であり、ことわざにあるように「クマより速くする必要はない。隣の人より速ければいいだけだ」です。
2018年2月の1.10リリースでは、大幅な変更はなく、クリーンアップとコーナーケースの追跡だけでした。
さて、新しい年と新しいSLOです。これが2018年のSLOです。
GCサイクル中に使用される合計CPUをCPUに削減しました。
ヒープは依然として2倍です。
GCサイクルごとに500マイクロ秒のstop-the-worldポーズという目標を設定しました。おそらく、少し保守的な目標です。
アロケーションは引き続きGCアシストに比例します。
ペーサーは大幅に改善されたため、定常状態でのGCアシストを最小限に抑えることにしました。
私たちはこれにかなり満足していました。繰り返しますが、これはSLAではなくSLOであるため、目標であり、OSなどの制御できないものがあるため、合意ではありません。
それは良いことでした。では、話題を変えて、私たちの失敗について話し始めましょう。これらは私たちの傷跡です。タトゥーのようなもので、誰もが手に入れます。とにかく、もっと良い話が付いてくるので、それらの話をいくつかしましょう。
私たちの最初の試みは、リクエスト指向コレクタ（ROC）と呼ばれるものを実行することでした。仮説はここに示されています。
これはどういう意味でしょうか？
ゴルーチンは、ゴーファーのように見える軽量スレッドです。ここでは、2つのゴルーチンがあります。それらは、中央にある2つの青いオブジェクトなど、いくつかのものを共有しています。それらは、独自のプライベートスタックと、独自のプライベートオブジェクトの選択肢を持っています。たとえば、左側の人が緑色のオブジェクトを共有したいとします。
ゴルーチンはそれを共有領域に入れるため、他のゴルーチンがそれにアクセスできます。それらはそれを共有ヒープ内の何かに接続したり、グローバル変数に割り当てたりすることができ、他のゴルーチンはそれを見ることができます。
最後に、左側のゴルーチンは死の床に伏せており、今にも死にそうです。悲しいことに。
ご存知のように、死ぬときにオブジェクトを持っていくことはできません。スタックも持ってはいけません。スタックはこの時点で実際には空であり、オブジェクトは到達不能であるため、それらを単に再利用できます。
ここで重要なのは、すべてのアクションがローカルであり、グローバルな同期を必要としなかったことです。これは、世代別GCのようなアプローチとは根本的に異なり、その同期を行う必要がないことから得られるスケーリングが、勝つために十分であると期待されていました。
このシステムで他に問題だったのは、書き込みバリアが常にオンになっていたことです。書き込みが発生するたびに、プライベートオブジェクトへのポインタがパブリックオブジェクトに書き込まれていないかを確認する必要がありました。もしそうであれば、参照先のオブジェクトをパブリックにし、さらに到達可能なオブジェクトの推移的なウォークを実行して、それらもパブリックであることを確認する必要がありました。これは非常にコストのかかる書き込みバリアであり、多くのキャッシュミスを引き起こす可能性がありました。
とは言え、驚くほど大きな成功もありました。
これはエンドツーエンドのRPCベンチマークです。誤ったラベルの付いたY軸は0から5ミリ秒までを示しています（低いほど良い）。とにかく、そういうものです。X軸は基本的にバラスト、つまりインコアデータベースの大きさです。
ご覧のとおり、ROCがオンで、共有があまりない場合は、実際にはかなりうまくスケールします。ROCがオフの場合は、それほど良くありませんでした。
しかし、それだけでは十分ではありませんでした。ROCがシステムの他の部分を遅くしないようにする必要もありました。その時点で、コンパイラに対する懸念が大きく、コンパイラを遅くすることはできませんでした。残念ながら、コンパイラはまさにROCがうまく機能しないプログラムでした。30％、40％、50％以上の遅延が見られ、それは許容できませんでした。Goはコンパイラの高速さを誇っているので、コンパイラを遅くすることはできません。ましてや、これほど遅くすることはあり得ませんでした。
そこで、他のプログラムを調べました。これらはパフォーマンスベンチマークです。200〜300のベンチマークのコーパスがあり、これらはコンパイラの担当者が、作業して改善することが重要だと判断したものです。これらはGCの担当者が選択したものではありません。数値は一様に悪く、ROCが勝者になることはありませんでした。
確かにスケールはしましたが、4〜12ハードウェアスレッドのシステムしか持っていなかったので、書き込みバリアのコストを克服できませんでした。将来、128コアのシステムが登場し、Goがそれを利用するようになった場合、ROCのスケーリング特性が有利になる可能性があります。そうなった際には、再検討するかもしれませんが、今のところROCはうまくいかないものでした。
では、次に何をすべきでしょうか？ジェネレーショナルGCを試してみましょう。古くからある良いものです。ROCはうまくいかなかったので、より多くの経験があるものに戻りましょう。
レイテンシを諦めるつもりはありませんでしたし、非移動型であるという事実も諦めるつもりはありませんでした。そのため、非移動型のジェネレーショナルGCが必要でした。
それで、これはできるのでしょうか？はい、できますが、ジェネレーショナルGCでは、書き込みバリアは常にオンになっています。GCサイクルが実行されているときは、現在使用しているのと同じ書き込みバリアを使用しますが、GCがオフのときは、ポインタをバッファリングし、オーバーフローしたときにバッファをカードマークテーブルにフラッシュする高速GC書き込みバリアを使用します。
では、非移動型の状況でこれはどのように機能するのでしょうか？ここにマーク/割り当てマップがあります。基本的に、現在のポインタを維持します。割り当てる際は、次のゼロを探し、そのゼロが見つかったら、そのスペースにオブジェクトを割り当てます。
次に、現在のポインタを次の0に更新します。
ある時点で世代GCを実行する時間になるまで続けます。マーク/割り当てベクトルに1がある場合は、そのオブジェクトが最後のGCで有効であったため成熟していることに気付くでしょう。それがゼロで、それに到達した場合は、若いことがわかります。
では、昇格はどのように行うのでしょうか？1でマークされたものが0でマークされたものを指しているのを見つけた場合は、その0を1に設定するだけで参照先を昇格させます。
到達可能なすべてのオブジェクトが昇格されていることを確認するために、推移的なウォークを実行する必要があります。
到達可能なすべてのオブジェクトが昇格されると、マイナーGCは終了します。
最後に、ジェネレーショナルGCサイクルを完了するには、現在のポインタをベクトルの先頭に戻すだけで、続行できます。そのGCサイクル中に到達しなかったゼロはすべて解放されており、再利用できます。多くの人がご存知のとおり、これは「スティッキービット」と呼ばれ、Hans Boehmとその同僚によって発明されました。
では、パフォーマンスはどうなったのでしょうか？大きなヒープでは悪くありませんでした。これらはGCがうまく機能するはずのベンチマークでした。これはすべてうまくいきました。
次に、パフォーマンスベンチマークで実行しましたが、うまくいきませんでした。何が起こっていたのでしょうか？
書き込みバリアは高速でしたが、十分に高速ではありませんでした。さらに、最適化が困難でした。たとえば、オブジェクトが割り当てられたときから次のセーフポイントまでの間に初期化書き込みがある場合、書き込みバリアの削除が発生する可能性があります。しかし、すべての命令にGCセーフポイントがあるシステムに移行する必要があったため、今後削除できる書き込みバリアは実際にはありませんでした。
また、エスケープ分析も行われており、ますます良くなっていました。私たちが話していた値指向のものを覚えていますか？関数へのポインタを渡すのではなく、実際の値を渡します。値を渡していたため、エスケープ分析は、手続き間分析ではなく、手続き内エスケープ分析のみを実行する必要がありました。
もちろん、ローカルオブジェクトへのポインタがエスケープする場合、オブジェクトはヒープに割り当てられます。
Goではジェネレーショナル仮説が真実ではないということではなく、若いオブジェクトはスタック上で短期間で存続して消滅するということです。その結果、ジェネレーショナルコレクションは、他のマネージドランタイム言語で見られるよりもはるかに効果が低いのです。
したがって、書き込みバリアに対するこれらの力が集まり始めていました。今日、私たちのコンパイラは2014年当時よりもはるかに優れています。エスケープ分析は、多くのオブジェクトを拾い上げてスタックに格納します。ジェネレーショナルコレクタが役立っていたはずのオブジェクトです。私たちは、エスケープしたオブジェクトをユーザーが見つけるのに役立つツールを作成し始めました。それが軽微な場合は、コードを変更して、コンパイラがスタックに割り当てるのを手伝うことができました。
ユーザーは値指向のアプローチを採用することにますます賢くなり、ポインタの数が減っています。配列とマップは、構造体へのポインタではなく値を保持します。すべてが順調です。
しかし、それは、今後Goで書き込みバリアが困難な状況に直面している主な理由ではありません。
このグラフを見てみましょう。これはマークコストの分析グラフにすぎません。各線は、マークコストを持つ可能性のある異なるアプリケーションを表しています。マークコストが20％だとしましょう。これはかなり高いですが、可能性はあります。赤い線は10％で、これもまだ高いです。下の線は5％で、これは最近の書き込みバリアのコストとほぼ同じです。では、ヒープサイズを2倍にするとどうなるでしょうか？それが右側の点です。GCサイクルが少なくなるため、マークフェーズの累積コストは大幅に低下します。書き込みバリアのコストは一定であるため、ヒープサイズを大きくすると、マークコストが書き込みバリアのコストを下回るようになります。
これが書き込みバリアのより一般的なコストで、4％です。それを使用しても、ヒープサイズを大きくするだけで、マークバリアのコストを書き込みバリアのコストよりも低くすることができることがわかります。
ジェネレーショナルGCの真の価値は、GC時間を検討する際に、書き込みバリアのコストがミューテータ全体に分散されるため無視されることです。これはジェネレーショナルGCの大きな利点であり、フルGCサイクルの長いSTW時間を大幅に短縮しますが、必ずしもスループットが向上するわけではありません。Goにはこの停止世界の問題がないため、スループットの問題をより詳しく検討する必要があり、それが私たちが行ったことです。
それは多くの失敗であり、そのような失敗とともに食事と昼食がやってきます。私はいつものように不満を言っています。「書き込みバリアがなければ、これは素晴らしいのに。」
一方、オースティンは、GoogleのHW GC担当者と1時間話したばかりで、彼らに連絡して、役立つ可能性のあるHW GCサポートをどのように得るかについて調べてみるべきだと言っていました。それから私は、ゼロフィルキャッシュライン、再開可能なアトミックシーケンス、および私が大手ハードウェア会社で働いていたときにはうまくいかなかった他のものについての戦いの話を始めました。確かに、Itaniumと呼ばれるチップにいくつかのものを搭載しましたが、今日のより一般的なチップには搭載できませんでした。したがって、教訓は、単に私たちが持っているHWを使用することです。
とにかく、それがきっかけで、私たちは何かクレイジーなことについて話し始めました。
書き込みバリアなしでカードマークを行うことはどうでしょう？オースティンはこれらのファイルを持っており、彼が私に話さない理由で、これらのファイルに彼のクレイジーなアイデアをすべて書き込んでいることがわかりました。それは一種の治療的なものだと思います。私も以前、エリオットとそうしていました。新しいアイデアは簡単に打ち砕かれてしまうため、世界に解き放つ前に保護して強くする必要があります。とにかく、彼はこのアイデアを取り出しました。
そのアイデアは、各カードの成熟したポインタのハッシュを維持するというものです。ポインタがカードに書き込まれると、ハッシュが変更され、カードはマークされたと見なされます。これにより、書き込みバリアのコストがハッシュのコストと交換されます。
しかし、さらに重要なことに、ハードウェアアラインメントされているのです。
今日の最新アーキテクチャには、AES（Advanced Encryption Standard）命令があります。これらの命令の1つは、暗号化グレードのハッシュを実行でき、暗号化グレードのハッシュを使用すると、標準の暗号化ポリシーにも従っていれば、衝突を心配する必要はありません。したがって、ハッシュにはあまりコストがかかりませんが、ハッシュするものをロードする必要があります。幸い、メモリを順次ウォークしているため、メモリとキャッシュのパフォーマンスが非常に優れています。DIMMがあり、連続したアドレスにアクセスする場合、ランダムなアドレスにアクセスするよりも高速になるため、メリットがあります。ハードウェアプリフェッチャが起動し、それも役立ちます。とにかく、Fortran、C、SPECintベンチマークを実行するためのハードウェアを設計するのに50年、60年を費やしてきました。その結果、この種の処理を高速に実行するハードウェアになることは驚くことではありません。
測定を行いました。これはかなり良いです。これは、良好であるはずの大きなヒープのベンチマークスイートです。
次に、パフォーマンスベンチマークではどうなるのかを尋ねました。それほど良くありません。いくつかの外れ値があります。しかし、これで、書き込みバリアがミューテータで常にオンになっている状態から、GCサイクルの一部として実行される状態に移行しました。世代GCを実行するかどうかを決定することが、GCサイクルの開始まで延期されました。カードワークをローカライズしたため、より多くの制御を行うことができます。ツールができたので、ペースメーカーに引き継ぐことができます。また、右側に逸脱し、世代GCの恩恵を受けないプログラムを動的にカットするのに役立ちます。しかし、これは今後勝利するでしょうか？ハードウェアが今後どうなるかを知るか、少なくとも考える必要があります。
未来の記憶とは何でしょうか？
このグラフを見てみましょう。これは典型的なムーアの法則のグラフです。Y軸は1つのチップに含まれるトランジスタ数の対数スケールを示しています。X軸は1971年から2016年までの年数です。これらの年は、どこかで誰かがムーアの法則は終わったと予測した年であることに注意してください。
デナードスケーリングは10年ほど前に周波数の向上を終えました。新しいプロセスは立ち上げに時間がかかるようになっています。そのため、2年ではなく、現在では4年以上かかっています。したがって、ムーアの法則の減速の時代に入っていることは明らかです。
赤い丸で囲まれたチップを見てみましょう。これらはムーアの法則を最も長く維持しているチップです。
これらのチップは、ロジックがますます単純になり、何度も複製されています。多数の同一のコア、複数のメモリコントローラーとキャッシュ、GPU、TPUなどです。
単純化と複製を続けると、最終的には2本のワイヤー、トランジスタ、およびコンデンサに漸近的に行き着きます。言い換えれば、DRAMメモリセルです。
別の言い方をすれば、メモリを倍増させる方がコアを倍増させるよりも価値があると私たちは考えています。
元のグラフはwww.kurzweilai.net/ask-ray-the-future-of-moores-lawにあります。
DRAMに焦点を当てた別のグラフを見てみましょう。これらはCMUの最近の博士論文からの数値です。これを見ると、ムーアの法則は青い線です。赤い線は容量で、ムーアの法則に従っているようです。奇妙なことに、1939年までさかのぼるグラフを見たことがありますが、その時はドラムメモリを使用していましたが、その容量とムーアの法則は一緒に進んでいました。したがって、このグラフは長い間続いており、おそらくこの部屋にいる誰よりも長く続いています。
このグラフをCPU周波数や、ムーアの法則は終わったというさまざまなグラフと比較すると、メモリ、少なくともチップ容量は、CPUよりも長くムーアの法則に従うだろうという結論に至ります。帯域幅、つまり黄色い線は、メモリの周波数だけでなく、チップから得られるピンの数にも関連しているため、十分に追いついていませんが、それほど悪くもありません。
レイテンシ、つまり緑の線は、非常にパフォーマンスが悪いです。ただし、シーケンシャルアクセスの場合のレイテンシは、ランダムアクセスの場合のレイテンシよりも優れていることに注意します。
（データは「Understanding and Improving the Latency of DRAM-Based Memory Systems Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Electrical and Computer Engineering Kevin K. Chang M.S., Electrical & Computer Engineering, Carnegie Mellon University B.S., Electrical & Computer Engineering, Carnegie Mellon University Carnegie Mellon University Pittsburgh, PA May, 2017」からです。Kevin K. Changの論文を参照してください。導入部の元のグラフは、ムーアの法則の線を簡単に引ける形式ではなかったので、X軸をより均一になるように変更しました。）
現実に即したところを見てみましょう。これは実際の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）
この別の線を見てみましょう。もし私たちがこの線に乗っていたら、いいでしょうね。これはSSDの線です。価格を低く抑えることには優れています。これらのチップの材料物理は、DRAMよりもはるかに複雑です。ロジックはより複雑で、セルあたり1つのトランジスタではなく、6つ程度あります。
今後は、Intelの3D XPointや相変化メモリ（PCM）などのNVRAMが存在するDRAMとSSDの間の線があります。今後10年間で、このタイプのメモリの入手性が高まるにつれて、主流になる可能性が高く、これはメモリの追加がサーバーに価値を追加するための安価な方法であるという考えをさらに強固にするでしょう。
さらに重要なことに、DRAMに代わる他の競合する選択肢が登場することが予想されます。5年または10年後にどれが好まれるかはわかりませんが、競争は激しくなり、ヒープメモリはここで強調表示されている青いSSDの線に近づくでしょう。
これらすべては、常にオンのバリアを避けてメモリを増やすという私たちの決定を裏付けています。
では、これらすべては今後のGoにとって何を意味するのでしょうか？
ユーザーから発生する特殊なケースを検討する際に、ランタイムをより柔軟で堅牢にするつもりです。スケジューラーを締め付け、より良い決定論と公平性を得ることを願っていますが、パフォーマンスを犠牲にしたくありません。
また、GC APIの表面を増やすつもりもありません。私たちはほぼ10年間やってきており、2つのノブがあり、それが適切に感じています。新しいフラグを追加するほど重要なアプリケーションはありません。
また、すでに非常に優れているエスケープ分析を改善し、Goの値指向プログラミングのために最適化する方法も検討します。プログラミングだけでなく、ユーザーに提供するツールでも同様です。
アルゴリズム的には、特に常にオンになっているバリアの使用を最小限に抑える設計空間の一部に焦点を当てます。
最後に、そして最も重要なこととして、ムーアの法則がCPUよりもRAMを優遇する傾向に乗ることを願っています。少なくとも今後5年間、そしてできれば今後10年間は。
以上です。ありがとうございました。
追伸：Goチームは、Goランタイムとコンパイラツールチェーンの開発と保守を支援するエンジニアを募集しています。
ご興味をお持ちですか？私たちの求人情報をご覧ください。
次の記事：Go Cloudを使用したポータブルクラウドプログラミング
前の記事：Go行動規範の更新
ブログインデックス