Plushガベージコレクタの高速化
Speeding Up the Plush Garbage Collector (pointersgonewild.com)
要約
著者は、自身が開発したLox風言語「Plush」のガベージコレクタ(GC)のパフォーマンスに不満を持っていました。当初の目標は100万個のライブオブジェクトを20ミリ秒未満で収集することでしたが、実装上のショートカット(ハッシュマップの使用)が原因で、117ミリ秒かかっていました。Rustの安全なハッシュ関数や冗長なルックアップの修正により43ミリ秒に改善しましたが、まだ目標には届きませんでした。最終的に、著者は従来のCheneyコピーGCアルゴリズムを採用し、メッセージ送信時のオブジェクトコピーのためにフォワーディングポインタを一時的に元に戻すオプションを追加しました。これにより、GC時間は7ミリ秒まで大幅に短縮され、当初の目標を達成しました。
全文翻訳
Plush ガベージコレクタの高速化
2026年8月17日
[画像]
このブログを読んでいる方や、X(旧Twitter)で私をフォローしている方は、私がサイドプロジェクトの間を飛び回る傾向があることをご存知でしょう。しばらく前に、サイドプロジェクトは楽しく、決して義務にならないようにすることが重要だと考え、自分のモチベーションに従い、新しいアイデアを探求することを意図的に許可しました。とはいえ、時折、以前は脇に置いていたプロジェクトのことを考え、それをさらに推し進める方法を思いつくことがあります。
昨年、私はPlushに関する一連のブログ記事を書きました。Plushは私が作成したアクターベースの並列処理を備えたトイ言語です。様々なインタプリタや仮想マシン(VM)の設計アイデアを試すためにこれをまとめました。特に、アクターベースの並列処理を備えており、クリティカルパス上のグローバルVMロックがなく、VM全体が何らかのために一時停止する必要がある状況もありません。その後、Plushインタプリタに基本的な最適化をいくつか実装し、次にVM用のコピー型ガベージコレクタ(GC)を書きました。GC自体は特別なものではありませんが、クールな点は、各アクターが独自の完全に独立したGCを持っていることです。各アクターは、同期を一切必要とせずにコレクションサイクルを実行できます。しかし、残念なことに、このGCのパフォーマンスは期待外れでした。
Plush GCには個人的な目標がありました。100万個のライブオブジェクトを20ミリ秒未満で収集できるようにしたかったのです。これは、GCの一時停止が全く気にならない3DゲームエンジンをPlushで構築するのに十分な速度だと考えました。私は、100万ノードの連結リストを割り当て、GCをループでトリガーする小さなgc_many_objs.pshマイクロベンチマークを作成しましたが、パフォーマンスは目標に全く届きませんでした。私のMacBook Air M5では、この実装の収集時間は約117ミリ秒で、目標の数倍遅すぎます。その理由は、コピーGCの実装で便利なショートカットを取ったことです。従来のCheneyコピーコレクタは、オブジェクトをあるメモリブロック(from-space)から別のブロック(to-space)にコピーします。これは、各オブジェクトのヘッダにある転送ポインタを使用し、コピープロセス中にライブオブジェクトのグラフを推移的に走査するためにto-spaceをワークリストとして使用します。
Plushでは、各アクターはオブジェクトを割り当てるための独自のプライベートアロケータと、他のアクターからのメッセージを受信するためのバッファとして使用されるメッセージアロケータを持っています。オブジェクトがメッセージとして送信されると、送信者はそれを受信者のメッセージアロケータにコピーします。これは、送信者と受信者を分離するためです。これにより、メッセージ交換のために送信者と受信者がロックや同期を行う必要がなくなります。私は、GCと、メッセージを受信者のメッセージアロケータにコピーするために、同じコピーアルゴリズムを再利用できるようにしたかったのです。そのため、送信者のヒープ上のオブジェクトを変更したくないため、送信者のヒープから転送ポインタを使用しませんでした。代わりに、オブジェクトとそのコピーの対応関係を追跡するハッシュマップを使用しました。ポインタのハッシュ化は高速なので、パフォーマンスにそれほど影響はないだろうと思いましたが、それは間違いでした。
[画像: アクターの2つのアロケータと、メッセージが通過する2つのコピー。]
アクターの2つのアロケータと、メッセージが通過する2つのコピー。
友人であり同僚でもあるLaurent Huberdeauは、私がその時点まで知らなかった基本的なことを指摘しました。それは、デフォルトのRust HashMapが、HashDoSから保護するために特別に設計されたセキュアなハッシュ関数を使用しているということです。これは機能には影響しませんが、パフォーマンスには影響します。幸いなことに、rustc_hashクレートには同等のFxHashMapがあり、これはrust-langプロジェクトによって保守されており、ドロップインリプレイスメントです。Laurentはまた、回避できる冗長なハッシュテーブルルックアップも見つけました。これらの簡単な変更により、コピーGCの実行速度は2倍以上になり、私のM5ラップトップでは43ミリ秒まで低下しました。はるかに高速になりましたが、元の目標である20ミリ秒にはまだ遠いです。
プロファイリングによると、オーバーヘッドの大部分は依然としてハッシュテーブルに起因しています。しかし、さらに悪いニュースがあります。転送ポインタハッシュテーブル自体が、収集中にコピーされるライブデータよりも多くのスペースを占有します。考えてみれば理にかなっています。連結リストをコピーしています。リストノードはかなり小さく、各ノードには次のポインタと値フィールドしかありません。ハッシュエントリ自体はポインタのペアですが、さらに、ハッシュマップはパフォーマンスを維持するためにある程度の追加容量(空のスロット)を必要とします。そうしないと、ハッシュ衝突が発生し、パフォーマンスが低下する可能性があります。それに加えて、ハッシュ関数は予測不可能であるように設計されています。出力は準ランダムな分布を持つように見えます。考えてみると、これはキャッシュパフォーマンスの観点からは実際にはひどいことです。GC中に、コピーするデータよりも多くのメモリを、予測不可能なパターンで、いたるところでタッチすることになります。良くありません。
[画像: 同じコピーを2つの方法で行ったもの:ハッシュテーブル経由と転送アドレスを使用した場合。]
同じコピーを2つの方法で行ったもの:ハッシュテーブル経由と転送アドレスを使用した場合。
このGCには他にも非効率な点があります。従来のCheney GCでは、to-spaceは線形に走査され、ワークリストとして機能します。to-space自体を使用して、どのオブジェクトがコピーされたかを追跡し、これらのオブジェクト内のポインタを走査して、ライブである他のオブジェクトをコピーします。それができない場合、別のワークリストを保持する必要があります。これはスタックとして機能する単純な動的配列で済みます。それは世界の終わりではありませんが、追加の割り当て、追加のメモリ使用量、メモリアクセスなどを引き起こす可能性もあります。しかし、私の実装の最も悪い点は、オブジェクトが転送された後、転送されたオブジェクトを通過して、from-spaceオブジェクトへのポインタをto-spaceのコピーへのポインタに置き換えるために、ハッシュマップを2回目に走査したことです。しかし、前述のように、ハッシュマップは準ランダムな順序でポインタを格納するため、from-spaceとto-spaceに予測不可能な順序でアクセスすることになります。やれやれ。
私の頭の中では、ハッシュマップは効率的なデータ構造であるという仮定に慣れてしまっていたようです。入門的なCSクラスでは、平均してO(1)の時間計算量が得られると教えられます。それらは多くの用途でうまく機能します。しかし、スループットを最大化するためにメモリ使用量とキャッシュフレンドリーさを最適化しようとする場合、それらはそうではないことが判明しました。私が当初、転送ポインタを使用したくなかった理由として、メッセージ送信時にオブジェクトをコピーするために同じコピーアルゴリズムを使用しており、そのプロセス中に送信者のヒープ上のオブジェクト(またはオブジェクトヘッダ)を上書きしたくなかったことを挙げました。しかし、その問題には簡単な解決策があります。この特別なケースでは、転送されたオブジェクトのリストを保持し、コピー後に転送ポインタの書き込みを元に戻してオブジェクトヘッダを復元するために戻ることができます。非効率に聞こえますが、実際には、他のアクターに送信されるメッセージは、ほとんどの場合、オブジェクトの巨大なグラフではないでしょうし、通常のGC使用はこのステップをスキップできます。
この時点で、Plush GCを伝統的なCheneyコピーアルゴリズムに単純に従うように書き直すことにしました。メッセージ送信の特別なケースのために転送ポインタを削除し、オブジェクトヘッダを復元するためのundoリストを格納できるトグルを付けました。これにより、100万個のライブオブジェクトのGC時間が7ミリ秒まで大幅に低下しました。これは、最初にあった単純な実装と比較して約16.7倍高速です。これは驚異的なパフォーマンス向上であり、私の20ミリ秒の目標をはるかに下回っています。実際、約2200ポリゴンの回転する都市景観を描画する例プログラムがあります。3Dベクトルおよび行列演算を行い、大量の一時オブジェクトを割り当てるため、定期的にGCをトリガーします。このプログラムでは、GC時間は1ミリ秒未満です。
歴史的な文脈として、Cheneyは、現在Cheneyアルゴリズムとして知られているものに関する論文を1970年に発表しました。当時、彼はFerranti Atlas 2コンピュータで作業していました。これは1960年代初頭のトランジスタ化されたスーパーコンピュータでした。それは大きな部屋全体を占め、コアメモリを使用し、驚くべきことに、すでに初期のキャッシュを備えていました。しかし、キャッシュ効率に関係なく、当時のメモリは貴重なリソースであり、転送ポインタを使用することは、補助データ構造を使用するよりもはるかにメモリ効率が良いです。この結論があまりにも拍子抜けするものでないことを願っています。なぜなら、私たちは元のCheney GCアルゴリズムと転送ポインタがはるかに効率的であるという結論に、ある意味で一周してきたからです。それでも、何が正確に効率的であるか、そしてキャッシュ効率や予測可能なメモリアクセスパターンがどれほどの影響を与えることができるかを理解することは良いことだと思います。また、RustのHashMapがセキュリティの落とし穴と引き換えにパフォーマンスの落とし穴をある程度犠牲にしたことを知っておくことも良いことです。
[画像: Ferranti Computer Systems brochureより、典型的なAtlas 2設置風景。]
Ferranti Computer Systems brochureより、典型的なAtlas 2設置風景。
GCを高速化したことに加えて、もう1つの改善を行いました。これは、Plushの制限を解除し、メモリ使用量を削減するのに役立ちます。以前は、アクターのメッセージアロケータを拡張するためのロジックがありませんでした。これは、メッセージサイズが16MBというハードコードされた定数に制限されていたことを意味します。メッセージアロケータは通常のGCヒープのようにバンプポインタ割り当てを使用しており、バックストレージを再割り当てするとキューに入れられたメッセージへのポインタが無効になるため、リサイズするのは少しトリッキーです。これは、キューが空になり、すべてのメッセージが受信者によって消費された場合にのみバックストレージを再割り当てできることを意味します。それは、送信者と受信者の調整を必要とします。1つのアクターが大きなメッセージを送信しようとしている場合、メッセージアロケータをサイズ変更する必要があることを受信者に伝える必要があり、その間、他のすべての送信者は待機する必要があります。しかし、より簡単な解決策があります。
Alan Wuから学んだと思われるクールなmmapトリックがあります。これはYJIT、私のUVMプロジェクト、そして多くの他のランタイムでも使用されています。MAP_PRIVATE | MAP_ANONYMOUSフラグとPROT_NONE保護を使用して、mmapで大きな連続した仮想アドレス空間のチャンクを事前に予約できます。これは基本的にOSにこの仮想アドレス空間のチャンクに他のメモリやリソースをマッピングしないように指示しますが、メモリは物理RAMにバックアップされていないため、RSS(Resident Set Size)を使用しません。後で、このスペースのページをPROT_READ | PROT_WRITEとしてmprotectに戻り、プログラムからアクセスできるようにすることができます。これにより、ゼロ埋めされたメモリが得られ、読み書きできますが、OSはそこにデータを書き込むまでこれらのページを物理RAMにマッピングしません。
知っておくべきことは、仮想アドレス空間は非常に大きいということです。現在、macOSとLinuxでは128TB(テラバイト)(48ビットアドレス指定に基づく)です。そのため、初期予約のサイズは非常に寛大にすることができます。512GBでさえ、利用可能な128TBのわずかな割合にすぎません。これは、C++のstd::vectorやRustのVecに相当するものを、必要に応じて動的にリサイズできるが、常にこの動的にサイズ変更されるベクター内のポインタを取得できることを意味します。ベクターをリサイズして容量を増やしても、古いポインタは無効になりません。アドレスを変更せずに、そのベクターを縮小してページをOSに返すことさえできます。クールですよね?Plushの文脈では、これは送信者が受信者や他の送信者との調整なしに、受信者のメッセージアロケータを簡単に拡張できることを意味します。受信者は後で、大きくなりすぎたメッセージアロケータを縮小して、OSにメモリを返すことができます。
[画像: 安定したアドレスを持つ予約済み範囲の増加に対して、Vecを増加させる。]
安定したアドレスを持つ予約済み範囲の増加に対して、Vecを増加させる。
書き直されたGCとmmapトリックにより、Plushははるかに高速なGC(リアルタイムゲームでも十分なパフォーマンスが期待できる)だけでなく、メモリ使用量も削減しました。コレクション自体はかさばるハッシュマップを使用せず、ベースラインのRSSもはるかに小さくなりました。アクターがいない単純なプログラムは、ピークRSSが9.6MBで、起動時間は10ミリ秒未満です。2000個のアクターを持つ単純なプログラムは、ピークRSSが224MBで、起動時間は0.23秒です。悪くありません。
次のステップとしては、Plushのパフォーマンスを改善したり、「実際の」プログラミング言語に近づけたりするためのアイデアがいくつかあります。PlushがValue型(「ファットバリュー」表現とも呼ばれる)を表すためにRustのタグ付きユニオンを使用している点が際立っています。これにより、読みやすいコードになりますが、アライメントを考慮すると、値あたり16バイトを使用することになります。ほとんどの動的言語はタグ付けスキームを使用しています。これにはいくつかの妥協点がありますが、メモリ使用量を大幅に削減できる可能性があります。Plushはスタックベースのインタプリタを使用していますが、レジスタベースのインタプリタははるかに高速になる可能性があります。また、LLMがPlushの単純なJITコンパイラを作成することがどれほど現実的かについても考えています。
ちなみに、なぜPlushにコピーGCを選んだのか疑問に思っているかもしれません。マークアンドスイープGCの方が実際には速いかもしれません。私の動機は、コピーGCは非常に高速なバンプ割り当て(多くの割り当てを行う動的言語に最適)を実行でき、コレクション時間がヒープ全体のサイズではなくコピーされるライブデータに比例するという便利な特性を持っていることです。メモリ内で関連データが近くに配置されることによる理論的なキャッシュ上の利点もあります。これらの仮定が間違っており、マークアンドスイープが勝つ可能性があるかもしれません。もし興味があり、試してみたい場合は、Plushリポジトリにbenchmarks/gc_many_objs.pshとbenchmarks/gc_alloc_speed.pshを追加しました。お気に入りのコーディングエージェントが30分未満でPlushをマークアンドスイープGCを使用するようにリファクタリングできるかもしれません。もし誰かがその実験を試すなら、結果を知りたいです。ベンチマークは必ずcargo run --releaseで実行し、cargo testも実行してテストがまだパスすることを確認してください。
追記: 上記で言及したタグ付けスキームの実装を進め、Value enumを64ビットワードに置き換えることに関するフォローアップ投稿を書き、インタプリタを17%高速化しました!
メーリングリストを購読し、このブログをフォローしてください:
Copyright © 2011–2026 Maxime Chevalier-Boisvert. All rights reserved.