ジャンク・バスターズパート2: オリノコ

2016年4月12日 · 約8分

ジャンク・バスターズ: ウラン・デゲンバイエフ、ミハエル・リップアウツ、ハンネス・ペイヤー

以前のブログ記事では、ガベージコレクションがスムーズなブラウジング体験を妨げるジャンクの問題について紹介しました。本記事では、「オリノコ」というコードネームで呼ばれるV8の新しいガベージコレクタの基盤となる3つの最適化を紹介します。オリノコは、厳密な世代境界を持たない主に並列かつ同時的なガベージコレクタを実装することで、ガベージコレクションによるジャンクとメモリ消費を削減しつつ高いスループットを提供することを目指しています。オリノコを別個のガベージコレクタとして旗印の背後に実装するのではなく、V8の最新バージョンにオリノコの機能を段階的に搭載することで、ユーザーにすぐに恩恵をもたらすことにしました。この記事で紹介する3つの機能は、並列圧縮、並列リメンバードセット処理、およびブラックアロケーションです。

V8は、オブジェクトが若い世代内で移動したり、若い世代から古い世代に移動したり、古い世代内で移動したりする世代別ガベージコレクタを実装しています。オブジェクトの移動はコストが高く、オブジェクトの基盤となるメモリを新しい場所にコピーし、そこへのポインタも更新する必要があるためです。図1は、オリノコ以前における各フェーズとその実行方法を示しています。要するに、オブジェクトをまず移動させ、その間のポインタを後で順次更新するという手法が取られており、それによるジャンクが観察されていました。

図1: オブジェクトの順次移動とポインタの更新

V8は、ヒープメモリを固定サイズのチャンク、いわゆるページに分割し、それを若い世代用または古い世代用のメモリスペースに割り当てます。オブジェクトは最初に若い世代に割り当てられます。ガベージコレクション時には、生存オブジェクトが一度若い世代内で移動されます。さらに別のガベージコレクションにも生存したオブジェクトは古い世代に昇格します。この2つのフェーズ（合わせて若い世代のエバキュエーションと呼びます）では、ページを基準にメモリのコピーが並列化されています。若い世代内のオブジェクト移動は常に新しいページ上にメモリを割り当てる（古いページを解放する）形で行われ、コンパクトなメモリレイアウトが残されます。古い世代では、このプロセスがわずかに異なります。なぜなら、使われなくなったメモリが断片（またはフラグメンテーション）として残るためです。これらの断片の一部はフリーリストを使って再利用できますが、他のものは再配置を必要とし、生存オブジェクトをより整理された（新しい可能性がある）ページに移す必要があります。若い世代に似て、このプロセスもページレベルで並列化されています。

若い世代のエバキュエーションと古い世代の圧縮の間には依存関係がないため、オリノコではこれらのフェーズを並列で実行するようになりました（図2を参照）。これらの改良の結果、圧縮時間が約75%短縮され、平均約7msから2ms未満になりました。

図2: オブジェクトの並列移動とポインタの更新

オリノコによって導入された2つ目の最適化は、ガベージコレクションがポインタを追跡する方法の改善です。ヒープ上でオブジェクトの位置が移動すると、ガベージコレクタは移動したオブジェクトの古い位置を含むすべてのポインタを見つけ、新しい位置でそれらを更新する必要があります。ただし、ヒープを反復してポインタを見つけるのは非常に遅いため、V8はリメンバードセットと呼ばれるデータ構造を使用して、ヒープ上のすべての「重要な」ポインタを追跡しています。ポインタは、ガベージコレクション中に移動する可能性のあるオブジェクトを指している場合に「重要」と見なされます。たとえば、古い世代から新しい世代へのポインタは、毎回のガベージコレクションで新しい世代オブジェクトが移動するため、重要です。また、重度にフラグメント化されたページ上のオブジェクトを指すポインタも重要であり、圧縮中にこれらのオブジェクトが他のページに移動するためです。

以前、V8は、記憶集合をポインタアドレスの配列、すなわち_ストアバッファ_として実装していました。若い世代には1つのストアバッファがあり、断片化された古い世代のページにはそれぞれ1つのストアバッファがありました。ページのストアバッファには、図3のようにすべての入力ポインタのアドレスが含まれています。_書き込みバリア_でストアバッファにエントリが追加され、JavaScriptコード内の書き込み操作を保護します。これにより、ストアバッファに同じポインタが複数回含まれたり、異なる2つのストアバッファに同一ポインタが含まれる場合があるため、重複エントリが生成されます。重複エントリは、2つのスレッドが同じポインタを更新しようとするために引き起こされるデータ競合のため、ポインタ更新フェーズの並列化を困難にします。

図3：古い記憶集合

Orinocoは記憶集合を再編成することで、この複雑さを排除し、ポインタの更新に関する並列化を簡素化し、スレッドがポインタの非重複集合を確実に取得するようにします。配列に興味深い入力ポインタを保存する代わりに、各ページは現在そのページから生成される興味深いポインタのオフセットを図4のようにビットマップのバケットに格納します。各バケットは空か、固定長のビットマップを指します。ビットマップ内のビットはページ内のポインタオフセットに対応します。ビットが設定されている場合、ポインタは興味深いものであり、記憶集合に含まれています。このデータ構造を使用すると、ページに基づいてポインタ更新を並列化できます。重複エントリの不在やポインタの密集型表現により、記憶集合オーバーフローを処理するための複雑なコードを削除することができました。長時間実行されるGmailベンチマークでは、この変更により最大停止時間が42msから23msに45%削減されました。

図4：新しい記憶集合

Orinocoが導入する第3の最適化は、ガベージコレクタのマーキングフェーズの改善である_ブラックアロケーション_です。ブラックアロケーション（V8 5.1で導入）は、古い世代に割り当てられたすべてのオブジェクト（例：事前年配割り当てまたはガベージコレクションによる昇格オブジェクト）が即座にブラックとしてマークされ、「生存」と指定されるガベージコレクション技術です。ブラックアロケーションの直感は、古い世代に割り当てられたオブジェクトが通常長寿である可能性が高いということです。したがって、古い世代に最近割り当てられたオブジェクトは、次の古い世代ガベージコレクションを少なくとも生き残るべきであり、それ以外の場合は誤って昇格されたことを意味します。新しく割り当てられたオブジェクトをブラックとして着色した後、ガベージコレクタはそれらを訪問しません。ブラックオブジェクトの着色を高速化するために、デフォルトですべてのオブジェクトがブラックであるブラックページ上にそれらを割り当てます。ブラックページのもう1つの利点は、そこに割り当てられたすべてのオブジェクトが（定義上）生存しているため、スイープする必要がないことです。ブラックアロケーションにより、着色作業が新しい割り当てに伴って増加しないため、インクリメンタルマーキングの進捗が高速化します。ブラックアロケーションの影響は、Octane Splayベンチマークで明確に見られ、スループットと遅延スコアが約30%向上し、マーキングの進捗が速く、全体のガベージコレクション作業量が少ないため、約20%のメモリを節約できました。

まもなくさらに多くのOrinoco機能を展開する予定です。まだ試行錯誤中ですのでお楽しみに！