yodaの備忘録

エンジニアのゆるいブログ

Shenandoahの話をしました

少し前のことになりますが会社の勉強会で1時間ほどGCの話をする機会があり、普通のGCの話ばかりしてもつまらないので後半はShenandoahをテーマにしてみました。以下そのときの話の備忘録です。

 

はじめに

早速ですがShenadoahの資料はプロジェクトメンバーのRoman Kennkeさんが公開してくれているので、英語が苦ではない方、ちゃんとした資料が見たい方はそちらを参照した方が幸せになれます。

https://rkennke.files.wordpress.com/2014/02/shenandoahtake4.pdf

また以下の文章には、自分の勘違いや記憶違い、開発が進んで変更されるところもあると思います。もしそういうところに気付かれた方はやさしく教えていただけるとありがたいです。

 

Shenadoahとは 

ShenandoahはOpenJDKのプロジェクトの一つで、"ultra-low pause time garbage collector"の開発プロジェクトであり、(少なくとも現時点では)GCの名前そのものでもあります。現在HotSpotに実装されているCMSでは、回収フェイズがミューテータと並行で動作するものの、スイープしか行わないため断片化を招いてしまいます。一方G1GCではコピーGCを行うことで断片化を防いでいますが、コピーしている間ミューテータは停止しています。ということでShenandoahではミューテータを動かしつつコピーをするといういいとこ取りを目指しています。

 

Shenandoahは一見G1GCにとてもよく似ています。例えばヒープをリージョンに分け、回収効率の良いリージョンをコピーGC(退避)により回収する、というところはそっくりです。Humongousリージョン等も相変わらず出てきます。そのくせ違う所はガラッと違うというところが面白いところです。

 

Concurrent Evacuation を実現するために 

では一番の特徴である並行退避(Concurrent Evacuation)を実現するための仕組みを見ていきましょう。あるオブジェクトを別のリージョンに退避させる場合、そのオブジェクトを指すポインタも退避先を指すように更新する必要があります。stop the worldしている間に全てのポインタをチェックして更新できればいいのですが、ミューテータの動作を止めない場合、どうしてもポインタの更新を始めてから全てのポインタを更新し終わるまでにタイムラグができてしまいます。そのラグの間はプログラマが同じオブジェクトだと思っているものが実は別のオブジェクトだということが発生してしまい、フィールドの更新が発生すると大事故になります。

 

この問題へのアプローチには2つ候補があります。

  • From領域のメモリ空間をプロテクトして、アクセスがきたらTo領域にリダイレクトする。
  • 間接参照を導入して、一箇所更新すれば全てのアクセスが更新されるようにする。

パフォーマンスを考えれば余計なステップを踏まないぶんどう考えても前者の方がベターで、無停止コレクタとして有名なC4はこの方法を使っています。Shenandoahは後者の方法を採用していますが、これはできるだけJVMのレイヤーで実装してポーティングしやすいようにしたいためなどの理由があるそうです。ということで、Shenandoahではオブジェクトごとに対になるポインタが一つ用意され*1オブジェクトへのアクセスはそのポインタを経由して行うことになります(リードバリア)*2。ちなみにこのポインタのことはBrooksPointerと呼びます。

 

通常BrooksPointerは対になるオブジェクトを指していますが、GCによりそのオブジェクトが退避させられると、退避先のオブジェクトのアドレスを指すように変更されます。From領域のオブジェクトにアクセスした場合でもBrooksPointerを経由してTo領域のオブジェクトにアクセスすることになるので、参照の経路によってFrom領域のオブジェクトにアクセスしたり、To領域のオブジェクトにアクセスしたりということはなくなります。

 

ただし、このアプローチによって発生する問題もあります。次のような順番で処理が行われた時のことを考えてみましょう。

  1. GCスレッドがFrom領域にあるオブジェクトをTo領域にコピーする
  2. ミューテータがBrooksPointerを見て、From領域にあるオブジェクトを更新する
  3. GCスレッドがBrooksPointerの指す先をFrom領域からTo領域に更新する

このとき2番目の操作で更新した内容は消えてしまいます。

 

ということでFromリージョンにあるオブジェクト（かつBrooksPointerもFromリージョンを指している）を更新する場合はこんな感じで動くよう、ライトバリアが必要です。

  •  ミューテータは更新を行う前にToリージョンへオブジェクトをコピーする
  •  ミューテータもGCスレッドも、BrooksPointerの更新はCAS命令で行う

 CAS命令を使うことで、コピーしてからBrooksPointerを更新するまでの間に別のスレッドがBrooksPointerを更新してしまっていた場合はBrooksPointerを更新できないようにしています*3。競合した場合は既にToリージョンにコピーが作られているはずなのでそちらに対して更新を行えばよいだけですし、その際にできてしまう無駄なコピーはもったいないですがそのうち回収されるでしょうからあまり気にしないことにします。

 

ここまでShenandoahの大きな特徴である退避関連の動作について説明してきました。もちろんこれだけでGCはできないので、今度は全体像について見ていきます。

 

Shenandoahのサイクル

Shenandoahのサイクルは3つのフェイズに分けると把握しやすいと思います。

 

  • マークフェイズ
  • 準備フェイズ
  • 退避フェイズ

 

マークフェイズのメインの仕事は、文字通り生存オブジェクトのマークです。動作としてはG1GCのConcurrent Markのようなものですが、主目的が異なる点は抑えておきましょう。G1GCのConcurrentMarkの主目的はリージョンごとのオブジェクトの生存状況を確認し、効率的な退避を行えるようにすることです。退避時には別途生存オブジェクトの確認を行うため、ConcurrentMarkと退避は一対一で行われるわけではありません。一方ShenandoahのConcurrentMarkは退避フェイズにおけるオブジェクトの生死判定を主目的とします。従ってShenandoahではConcurrentMark一回の直後に退避フェイズが一回走ります*4。このフェイズは基本的にはミューテータと並行に実施されますが、最初のルートセットのスキャンからルートオブジェクトのマークまで(initial mark)と、最後に行うフェイズ中の変更分の集計(final mark)はstop the worldの処理です。

 

ここまででヒープ全体の生存オブジェクトをマークすることが出来ました。早速退避フェイズに入る…前に準備が必要です。退避対象となるリージョン、つまりCollectionSetの選択をします。Shenandoahでは退避フェイズの停止時間はないので、ゴミの量が基準を超えているリージョンは全てCollectionSetに含めることができます*5。このフェイズもstop the worldの処理です*6。

 

準備が完了したら退避フェイズの開始です。CollectionSetに含まれたリージョン内の生存オブジェクトを順次空きリージョンに退避していきます。既に説明したように、退避はGCスレッドだけでなく、回収対象リージョンのオブジェクトを更新しようとしたミューテータによっても行われます。

 

退避フェイズ終了時点では退避対象リージョンへのポインタがそのまま残っていることに注意してください。退避前のオブジェクトをA、退避先にコピーされたオブジェクトをA’とした場合、A’への参照はAのBrooksPointerを経由します。従ってAの存在するリージョンを回収してしまうとA’への参照経路も絶たれてしまいます。次に行うべきは退避対象リージョンのオブジェクトへのポインタを退避先へと更新していくことです。

 

この作業を完了するためには、全ての有効なポインタをチェックする必要があります。ポインタのチェックは既にやっていますよね。そう、マークフェイズです。マークフェイズでは、生存オブジェクトを確認すると同時に、前回の退避フェイズでCollectionSetに含まれたリージョンへのポインタを、退避先リージョンへのポインタに更新していきます。マークフェイズが終了すると全てのポインタの更新が完了するので、準備の段階でCollectionSetに含まれたリージョンを解放することができます。

 

まとめると、以下の様なサイクルでGCは進みます。

マークフェイズ

  1. ルートセットから到達可能な全てのポインタをスキャンし、生存オブジェクトを確定する。
  2. スキャンしたポインタのアドレスが、前回のConcurrent Evacuation PhaseのCollectionSet内だった場合、退避先オブジェクトを指すようポインタを更新する。

準備フェイズ

  1. 前回のGCでCollectionSetに含まれていたリージョンを解放する。
  2. 到達不能になったHumongousリージョンを解放する。
  3. リージョンごとのごみの量をチェックし、基準を超えたリージョンをCollectionSetに含める。

退避フェイズ

  1. CollectionSetに含まれたリージョンのオブジェクトを順次空きリージョンへコピーする。コピーしたオブジェクトのBrooksPointerを更新し、コピー先のオブジェクトが参照されるようにする。
  2. GCスレッドが退避させる前にオブジェクトをミューテータが更新しようとした場合は、ミューテータは空きリージョンへのオブジェクトのコピーとBrooksPointerの更新を行い、退避先のオブジェクトを更新する。

 

世代

ここまでYoungやOldのような世代の話はしてきませんでした。なぜでしょう？Shenandoahは世代別GCではないのです。世代別GCは(ちょっと乱暴に説明すると)弱い世代別仮説に基づいてヒープを分割し、回収効率が良いと期待されるオブジェクト群だけを回収することで効率を上げる方法です。Shenandoahは退避前に全てのリージョンのごみの量を確認してリージョンを選択するので、特定の仮定に基づく必要はなく、アプリケーションの動作が弱い世代別仮説にあてはまらない場合でも効率を落とすことがありません。

 

また、Shenandoahは毎回ヒープ全体の生存オブジェクトをマークしてから一部のリージョンだけを解放します。G1は毎回ヒープ全体をマークするわけではないので、そのほうが効率が良さそうです。しかし、そのためにG1ではRememberedSetが必要になります。これはリージョン間をまたぐ参照を管理しておくことで、ヒープ全体をスキャンせずともリージョンの生存オブジェクトを確定できるようにするためのものです。G1はヒープを数千のリージョンに分けるので、その分のRemenbered Setを管理しておく必要があり*7、RemenberedSetをちゃんとアップデートしていくためのコストはG1GCを選択した場合にスループットの悪化として現れてしまいます*8。Shenandoahは毎回ヒープ全体をスキャンすることでRememberedSetを不要にしてオーバーヘッドを削減しています。

 

将来の話

まだShenandoahは開発中なので、Productionで使えるようになるまではだいぶ時間がかかると思われます。ただ現在開発中のShenandoahはShenandoah1.0と位置づけられており、Shenandoah2.0ではstop the worldの処理が取り除かれて完全にConcurrentなGCになる*9ことを目指しているそうなので、楽しみに待ちましょう*10。

*1:instanceOopに追加されるわけではない

*2:もちろんポインタを配置する分メモリを余分に使い、リードバリアの分CPUも余計に使う

*3:要するに楽観的ロックを行っている

*4:G1GCはコピーGCだがShenandoahはマークコピーGCであるという言い方もできる

*5:100％ごみしかなかったリージョンはCollectionSetに含まずこの時点で回収される

*6:「これもstop the world」というよりは、実装を踏まえるとfinal markから退避開始までをひと固まりの処理であるとみなすのが妥当なのですが、じゃあこいつはマークなのか退避なのかと言われるとつらいので、今回は説明しやすいように一つの固まりとして切り出しています

*7:実際にはYoungのリージョンは必ずCollectionSetに含まれるためYoungからOldへの参照を管理しておく必要はない

*8:GCの停止時間が長いという話ではなく、ライトバリアによってGCしていないときのミューテータの処理が遅くなるということ

*9:一度にスレッドを止めずに順次止めながらスキャンする仕組みなどが必要。Pauselessのマークの仕組みがよくわからないので誰か教えて下さい…

*10:待てない方はZing使いましょう