Oilpanにおけるポインタ圧縮
4ギガバイト未満のRAMを使用するプログラムをコンパイルする場合に、64ビットのポインタを使用するのは全くもって愚かなことです。このようなポインタの値が構造体内に現れると、メモリの半分を無駄にするだけでなく、キャッシュの半分を効果的に捨てることになります。
これ以上ないほど真実味を帯びた言葉です。CPU ベンダが実際には64ビットCPUを出荷していないことや、Android OEM がカーネル内でのページテーブルウォークを高速化するために39ビットのアドレス空間のみを選択することも目にしています。Chrome上で動作するV8もまた、サイトを別々のプロセスに分離することで、単一タブに必要なアドレス空間をさらなる制限に導いています。これらは全く新しいことではなく、このため私たちは2020年にV8でのポインタ圧縮を開始し、Web全体でメモリの大きな改善を目にしました。Oilpanライブラリを利用すれば、Webの別の構成要素も制御下に置くことができます。OilpanはC++向けのトレースベースのガベージコレクタで、Blinkの文書オブジェクトモデルをホストするためにも使用されており、メモリ最適化の興味深いターゲットとなります。
背景
ポインタ圧縮は、64ビットプラットフォーム上でポインタのサイズを縮小するメカニズムです。OilpanのポインタはMemberというスマートポインタにカプセル化されています。非圧縮ヒープレイアウトでは、Member参照はヒープオブジェクトを直接指すため、参照あたり8バイトのメモリが使用されます。このシナリオでは、各ポインタが対象オブジェクトを参照するためのすべての情報を含んでいるため、ヒープはアドレス空間全体に広がる可能性があります。
圧縮ヒープレイアウトでは、Member参照はヒープケージ内のオフセットのみを表します。ヒープケージは、連続したメモリ領域です。ヒープケージの始まりを指す基本ポインタ（base）とMemberを組み合わせると、完全なポインタが形成されます。これはセグメントアドレッシングに非常によく似ています。オフセットに使用可能なビット数によって、ヒープケージのサイズは制限されます。例えば、4GBのヒープケージは32ビットオフセットを必要とします。
便利なことに、Oilpanヒープは64ビットプラットフォーム上で既に4GBヒープケージに収束しているため、有効な任意のヒープポインタを最も近い4GB境界まで揃えるだけでガベージコレクションメタデータを参照できます。
Oilpanは、例えばBlink内のC++ヒープを持つWebワーカーをサポートするため、同じプロセス内で複数のヒープもサポートします。この設定から生じる問題は、ヒープを多数のヒープケージにどのようにマッピングするかです。ヒープはBlink内でネイティブスレッドにバインドされているため、ここでの解決策はスレッドローカルな基本ポインタを介してヒープケージを参照することです。V8およびその埋め込みがどのようにコンパイルされるかに応じて、スレッドローカルストレージ（TLS）モデルは、メモリから基本ポインタがロードされる速度を高速化するため制限可能です。最終的には、最も汎用的なTLSモードが必要ですが、Androidでは、レンダラー（つまりV8）がdlopen経由でロードされるためです。このような制約により、パフォーマンスの観点からTLSを使用するのは現実的ではありません1。最高のパフォーマンスを提供するため、OilpanはV8と同様に、ポインタ圧縮を使用する場合にすべてのヒープを単一のヒープケージに割り当てます。これにより全体の利用可能なメモリは制限されますが、ポインタ圧縮がすでにメモリ削減を目指していることを考えると、これは現在のところ容認可能であると信じています。4GBの単一ヒープケージが制限が厳しすぎると判明した場合でも、現在の圧縮スキームにより、パフォーマンスを犠牲にせず16GBにヒープケージのサイズを増加させることが可能です。
Oilpanにおける実装
要件
これまで、メンバーポインタに保存されているオフセットに基底値を加えることで完全なポインタを形成するという簡単なエンコーディング方式について説明しました。ただし、実際に実装されている方式は残念ながらそれほど単純ではありません。というのも、Oilpanではメンバーが以下のいずれかに割り当てられることを要求しているためです。
- オブジェクトへの有効なヒープポインタ;
- C++の
nullptr（または類似のもの）; - コンパイル時に既知でなければならないセンチネル値。例えば、センチネル値はハッシュテーブルで削除された値を示すために使用できます。このハッシュテーブルでは、
nullptrもエントリとしてサポートされます。
nullptrとセンチネルに関する問題点は、呼び出し側でこれらを明示的に捉える型が欠如していることです。
void* ptr = member.get();
if (ptr == nullptr) { /* ... */ }
圧縮されたnullptr値を格納する明示的な型が存在しないため、定数と比較するには実際のデコンプレッションが必要です。
この使用方法を考慮し、ケース1～3を透明に処理する方式を探しました。圧縮とデコンプレッションのシーケンスはMemberが使用されるすべての場所でインライン展開されるため、次の特性も望ましいです。
- icacheミスを最小限に抑える高速でコンパクトな命令シーケンス。
- 分岐予測器を使い尽くさない分岐のない命令シーケンス。
読み取りが書き込みを大幅に上回ることが予想されるため、デコンプレッションを高速化する非対称的な方式を許容しています。
圧縮とデコンプレッション
簡潔にするため、ここでは使用された最終的な圧縮方式のみを説明します。我々がそこに到達した方法や検討された代替案については、設計ドキュメントを参照してください。
今日実装されている方式の主なアイデアは、ヒープケージのアラインメントを利用して、通常のヒープポインタをnullptrやセンチネルから分離することです。基本的には、ヒープケージは上位半ワードの最下位ビットが常にセットされるようなアラインメントで割り当てられます。上位と下位の半分（各32ビット）をそれぞれU31...U0およびL31...L0と表記します。
| 上位半分 | 下位半分 | |
|---|---|---|
| ヒープポインタ | U31...U11 | L31...L3000 |
nullptr | 0...0 | 0...000 |
| センチネル | 0...0 | 0...010 |
圧縮は単に右シフトし、値の上位半分を切り捨てることで圧縮値を生成します。この方法では、アラインメントビット（圧縮値の最上位ビットになる）が有効なヒープポインタを示します。
| C++ | x64アセンブリ |
|---|---|
| ```cpp | ```asm \ |
| uint32_t Compress(void* ptr) { | mov rax, rdi \ |
| return ((uintptr_t)ptr) >> 1; | shr rax \ |
| } | ``` \ |
| ``` |
圧縮値に対するエンコーディング方式は次の通りです：
| 圧縮値 | |
|---|---|
| ヒープポインタ | 1L31...L200 |
nullptr | 0...00 |
| センチネル | 0...01 |
これにより、圧縮値がヒープポインタ、nullptr、またはセンチネル値を表しているかどうかを判断できるため、ユーザーコードで無駄なデコンプレッションを回避できます（以下参照）。
デコンプレッションのアイデアは、最下位32ビットがすべて1に設定された特別に作成された基底ポインタを利用することです。
| 上位半分 | 下位半分 | |
|---|---|---|
| 基底ポインタ | U31...U11 | 1...1 |
デコンプレッション操作はまず圧縮値を符号拡張し、続いて符号ビットの圧縮操作を元に戻すように左シフトします。結果として得られる中間値のエンコードは次の通りです。
| 上位半分 | 下位半分 | |
|---|---|---|
| ヒープポインタ | 1...1 | L31...L3000 |
nullptr | 0...0 | 0...000 |
| sentinel | 0...0 | 0...010 |
最後に、解凍されたポインタはこの中間値とベースポインタとのビット間論理積の結果です。
| C++ | x64 assembly |
|---|---|
| ```cpp | ```asm \ |
| void* Decompress(uint32_t compressed) { | movsxd rax, edi \ |
| uintptr_t intermediate = | add rax, rax \ |
| (uintptr_t)((int32_t)compressed) <<1; | and rax, qword ptr \ |
| return (void*)(intermediate & base); | [rip + base] \ |
| } | ``` \ |
| ``` |
結果として得られるスキームは、分岐のない非対称スキームを使用してケース1.-3.を透過的に処理します。圧縮には3バイトが使用されますが、初期のレジスター移動は呼び出しがインライン化されるためカウントされません。解凍には13バイトが使用され、初期の符号拡張レジスター移動が含まれています。
選択された詳細
前のセクションでは使用される圧縮方式を説明しました。高い性能を得るためにはコンパクトな圧縮方式が必要です。上記の圧縮方式はSpeedometerで観測可能な性能後退をもたらしました。以下の段落は、Oilpanの性能を許容可能なレベルまで向上させるために必要なさらにいくつかの情報を説明します。
ケージベースのロードの最適化
技術的には、C++の観点では、グローバルベースポインタは一定ではありえません。なぜなら、Oilpanを初期化するエンベッダーがmain()後にランタイムで初期化するからです。このグローバル変数を変更可能にすると重要なコンスト伝播の最適化を妨げる可能性があります。例えば、コンパイラがランダムな呼び出しがベースを変更しないと証明できないため、2回ロードする必要があります。
| C++ | x64 assembly |
|---|---|
| ```cpp | ```asm \ |
| void foo(GCed*); | baz(Member<GCed>): \ |
| void bar(GCed*); | movsxd rbx, edi \ |
| add rbx, rbx \ | |
| void baz(Member<GCed> m) { | mov rdi, qword ptr \ |
| foo(m.get()); | [rip + base] \ |
| bar(m.get()); | and rdi, rbx \ |
| } | call foo(GCed*) \ |
| ``` | and rbx, qword ptr \ |
| [rip + base] # extra load \ | |
| mov rdi, rbx \ | |
| jmp bar(GCed*) \ | |
| ``` |
追加の属性を追加することで、clangにグローバルベースを定数として扱わせ、実際にコンテキスト内で単一のロードのみを実行させました。
解凍を完全に回避する
最も高速な命令シーケンスはnopです！そのことを念頭に置いて、多くのポインタ操作では冗長な圧縮と解凍を簡単に回避できます。自明なことに、Memberをnullptrであるか確認する場合解凍は必要ありません。Memberから他のMemberを構築または代入するときも解凍と圧縮は不要です。ポインタの比較は圧縮によって保持されるため、それらの変換を回避することもできます。ここでMember抽象はボトルネックとしてうまく役立っています。
ハッシュは圧縮されたポインタを使用して高速化できます。ハッシュ計算の解凍は冗長であり、固定されたベースがハッシュのエントロピーを増加させません。その代わりに、32ビット整数向けのより簡易的なハッシュ関数を使用できます。BlinkにはMemberをキーとして使用する多くのハッシュテーブルがあり、32ビットハッシュはより早い収集を実現しました！
clangが最適化に失敗する場合への支援
生成されたコードを調査すると、コンパイラが十分な最適化を行わない別の興味深い場所が見つかりました：
| C++ | x64 assembly |
|---|---|
| ```cpp | ```asm \ |
| extern const uint64_t base; | Assign(unsigned int): \ |
| extern std::atomic_bool enabled; | mov dword ptr [rdi], esi \ |
| mov rdi, qword ptr \ | |
| void Assign(uint32_t ptr) { | [rip + base] \ |
| ptr_ = ptr | mov al, byte ptr \ |
| WriteBarrier(Decompress(ptr)); | [rip + enabled] \ |
| } | test al, 1 \ |
| jne .LBB4_2 # 非常に稀 \ | |
| void WriteBarrier(void* ptr) { | ret \ |
| if (LIKELY( | .LBB4_2: \ |
| !enabled.load(relaxed))) | movsxd rax, esi \ |
| return; | add rax, rax \ |
| SlowPath(ptr); | and rdi, rax \ |
| } | jmp SlowPath(void*) \ |
| ``` | ``` |
生成されたコードは、基本ブロック内の変数が使用されていないにもかかわらず、ホットな基本ブロックでベースロードを実行します。そして、それはコードの下に簡単に移動することができます。その基本ブロックで、SlowPath()の呼び出しが行われ、デコンプレッションされたポインタが実際に使用されます。コンパイラは、非アトミックロードとアトミックリラックスロードを並べ替えることを控えましたが、それは言語ルールに関して完全に合法です。私たちは手動でデコンプレッションをアトミックリードの下に移動し、WriteBarrierでの代入を可能な限り効率的にしました。
Blinkでの構造体パッキングの改善
Oilpanのポインタサイズを半分にする効果を推定するのは難しいです。基本的に、ポインタを含むような「パックされた」データ構造（例えばコンテナ）に対してメモリ利用率を向上させるはずです。ローカル測定では、Oilpanメモリの約16％の改善が見られました。しかし、調査の結果、いくつかの型では実際のサイズが減少せず、フィールド間の内部パディングが増加しただけでした。
このパディングを最小化するため、フィールドの並べ替えを行うことでクラス全体のサイズを縮小できるようなガベージコレクションされたクラスを自動的に識別するclangプラグインを書きました。Blinkコードベース全体でこのようなケースが多数ありました。最も使用頻度の高いものに並べ替えを適用しました。詳細は設計文書をご覧ください。
失敗した試み：ヒープケージサイズの制限
すべての最適化がうまくいくわけではありません。圧縮をさらに最適化しようとして、ヒープケージサイズを2GBに制限しました。ケージベースの下半ワードの最上位ビットが1であることを確認し、シフトを完全に回避できました。圧縮は単純な切り捨てになり、デコンプレッションは単純なロードとビット単位のAND操作になりました。
Blinkレンダラー内のOilpanメモリが平均して10MB未満であることを踏まえ、この迅速なスキームで進めることとケージサイズを制限することを安全であると想定しました。しかし、最適化を提供した後で、一部の稀なワークロードでメモリ不足エラーが発生し始めました。この最適化を元に戻すことを決定しました。
結果と今後
Oilpanでのポインタ圧縮はChrome 106でデフォルトで有効になりました。全体で素晴らしいメモリ改善が見られました：
| Blinkメモリ | P50 | P99 |
|---|---|---|
| Windows | -21% (-1.37MB) | -33% (-59MB) |
| Android | -6% (-0.1MB) | -8% (-3.9MB) |
報告された数値は、Oilpanで割り当てられたBlinkメモリの第50と99パーセンタイルを表しています。報告されたデータはChrome 105と106の安定版間の差を示しています。MB単位の絶対数値は、ユーザーが期待できる下限の指標となります。実際の改善は通常、Chrome全体のメモリ消費への間接的効果により少し高くなります。より大きな相対改善は、データのパッキングが優れていることを示唆し、これが良いパッキングを持つコレクション（例：ベクター）でより多くのメモリが使用されていることを示す指標となります。構造体の改善されたパディングはChrome 108で導入され、平均してBlinkメモリにさらに4％の改善を示しました。
BlinkでOilpanが普遍的に使用されるため、性能コストはSpeedometer2で推定できます。初期プロトタイプは、スレッドローカル版に基づいて15％の回帰を示しましたが、前述のすべての最適化後には顕著な回帰は観測されませんでした。
保守的スタックスキャン
Oilpanでは、スタックを保守的にスキャンしてヒープへのポインタを見つけます。圧縮ポインタを使用する場合、スタック上のすべてのハーフワードを潜在的なポインタとして扱う必要があります。さらに、圧縮の過程で、コンパイラが中間値をスタックに退避させることを選択する場合があり、このためスキャナーはすべての可能な中間値（圧縮スキームでは唯一の可能な中間値は切り捨てられたがまだシフトされていない値）を考慮する必要があります。中間値のスキャンが誤検出の数（圧縮されたポインタに見えるハーフワード）を増加させ、結果としてメモリ改善が約3%減少しました（本来の推定メモリ改善は24%でした）。
その他の圧縮
これまでに、V8 JavaScriptやOilpanに圧縮を適用することで大きな改善が見られました。このパラダイムは、Chromeの他のスマートポインタ（例: base::scoped_refptr）にも適用できると考えています。これらのポインタも他のヒープケージを指しています。初期の実験では有望な結果が得られました。
調査により、大量のメモリが実際には仮想テーブル（vtables）を介して保持されていることも判明しました。同様の考えで、Android64上で相対vtable ABIを有効化し、仮想テーブルを圧縮することで、より多くのメモリを節約しつつ、同時に起動時間を改善しています。
Footnotes
-
興味のある読者は、異なるモードでのTLSアクセスのコンパイル結果を確認するために、Blinkの
ThreadStorage::Current()を参照してください。 ↩