Plushガベージコレクタの高速化

Pointers Gone Wild Plushガベージコレクタの高速化 2026年8月17日 このブログを読んでいる方や、Xで私をフォローしている方は、私がサイドプロジェクトを転々としていることをご存知でしょう。 しばらく前に、私は自分のモチベーションに従い、新しいアイデアを探求することを意図的に許可しました。なぜなら、サイドプロジェクトは楽しく、決して面倒なものになってはならないと考えるからです。 とはいえ、時折、しばらく前に棚上げにしたプロジェクトのことを考え、それをさらに推し進める方法を考えます。 昨年、私はPlushという、私が作成したおもちゃのLox風言語に関する一連のブログ記事を書きました。 私は、さまざまなインタープリタや仮想マシンの設計アイデアを試すために、それをまとめました。特に、アクターベースの並列処理を備えており、グローバルなVMロックがクリティカルパスに存在せず、VM全体が何らかのために一時停止する必要がある状況がないように設計されています。 その後、Plushインタープリタにいくつかの基本的な最適化を実装し、次にVM用のコピー型ガベージコレクタ（GC）を記述しました。 GC自体は特別なものではありませんが、クールな点は、各アクターが独自の完全に独立したGCを持っていることです。 各アクターは、同期を一切行わずにコレクションサイクルを実行できます。 しかし、残念なのは、このGCのパフォーマンスがかなり期待外れだったことです。 Plush GCには個人的な目標がありました。 100万個のライブオブジェクトを20ミリ秒未満で収集できるようにしたかったのです。これにより、GCの一時停止が気にならない3DゲームエンジンをPlushで構築できるほど高速になるという考えです。 私は小さなgc_many_objs.pshマイクロベンチマークを作成し、100万ノードの連結リストを割り当ててからGCをループでトリガーしましたが、パフォーマンスは目標に全く達しませんでした。 私のMacBook Air M5では、この実装の収集時間は約117ミリ秒になり、目標を数倍上回る遅さでした。 理由は、コピー型GCの実装で便利なショートカットを使用したことです。 従来のCheneyコピーコレクタは、オブジェクトをあるメモリブロック（from-space）から別のブロック（to-space）にコピーし、各オブジェクトのヘッダーにあるフォワーディングポインタを使用します。同時に、コピープロセス中にライブオブジェクトのグラフを推移的に走査するためのワークリストとしてto-spaceを使用します。 Plushでは、各アクターはオブジェクトを割り当てるための独自のプライベートアロケータと、他のアクターからメッセージを受信するためのバッファとして使用されるメッセージアロケータを持っています。 オブジェクトがメッセージとして送信されると、送信者はそれを受信者のメッセージアロケータにコピーします。 これは、送信者と受信者を分離するために存在します。これにより、メッセージ交換のために送信者と受信者がロックや同期を行う必要がなくなります。 GCと、メッセージを受信者のメッセージアロケータにコピーするために、同じコピーアルゴリズムを再利用できるようにしたかったのです。 そのため、送信者のヒープにあるフォワーディングポインタを使用しませんでした。これは送信者のオブジェクトを変更してしまうためです。 代わりに、オブジェクトとそのコピーの対応関係を追跡するハッシュマップを使用しました。 ポインタのハッシュ化は高速なので、パフォーマンスにそれほど影響はないだろうと思いましたが、それは間違いでした。 アクターの2つのアロケータ、およびメッセージが通過する2つのコピー。 私の友人であり同僚のLaurent Huberdeauは、私がその時点まで知らなかった基本的なことを指摘しました。それは、デフォルトのRust HashMapが、HashDoSから保護するために特別に設計された安全なハッシュ関数を使用しているということです。 これはその機能には影響しませんが、パフォーマンスには影響します。 幸いなことに、rustc_hashクレートにはFxHashMapという同等のものがあり、これはrust-langプロジェクトによって保守されており、ドロップイン交換可能です。 Laurentはまた、回避できた冗長なハッシュテーブルルックアップも見つけました。 これらの簡単な変更により、コピー型GCの実行速度は2倍以上になり、私のM5ラップトップでは43ミリ秒にまで低下しました。 はるかに高速になりましたが、それでも当初の20ミリ秒という目標にはほど遠いものでした。 プロファイリングによると、オーバーヘッドの大部分は依然としてハッシュテーブルから来ています。 しかし、さらに悪いニュースがあります。フォワーディングポインタのハッシュテーブル自体が、収集中にコピーされるライブデータよりも多くのスペースを占有します。 考えてみれば理にかなっています。 連結リストをコピーしています。リストノードはかなり小さく、各ノードには次のポインタと値フィールドしかありません。 ハッシュテーブルエントリ自体はポインタのペアですが、それだけでなく、ハッシュマップはパフォーマンスを維持するためにある程度の追加容量（空のスロット）を必要とします。そうしないと、ハッシュ衝突やパフォーマンスの低下につながる可能性があります。 それに加えて、ハッシュ関数は予測不可能であるように設計されています。出力は準ランダムな分布を持つように見えます。 考えてみれば、これはキャッシュパフォーマンスの観点からは実際にはひどいことです。 GC中に、コピーするデータよりも、予測不能なパターンで、あらゆる場所のメモリに触れることになることを意味します。 あまり良くありません。 同じコピーが2つの方法で行われます。ハッシュテーブルを介した方法と、フォワーディングアドレスを使用した方法。 このGCには他にも非効率な点があります。 従来のCheney GCでは、to-spaceは線形に走査され、ワークリストとして機能します。 私たちはto-space自体を使用して、どのオブジェクトをコピーしたかを追跡し、これらのオブジェクト内のポインタを走査して、他のライブオブジェクトもコピーします。 それができない場合、別のワークリストを保持する必要があります。 これは、スタックとして機能する単純な動的配列になる可能性があります。 それは世界の終わりではありませんが、追加の割り当て、追加のメモリ使用量、メモリアクセスなどを追加する可能性があります。 しかし、私の実装の最も悪い点は、オブジェクトが転送された後、転送されたオブジェクトを通過し、from-spaceオブジェクトへのポインタを受信者のコピーへのポインタに置き換えるために、ハッシュマップを2回走査したことです。 しかし、前述のように、ハッシュマップは準ランダムな順序でポインタを格納するため、from-spaceとto-spaceにも予測不能な順序でアクセスすることになります。 まあ。 私は、どこかで、ハッシュマップは効率的なデータ構造であるという仮定に慣れてしまったのだと思います。 入門的なCSクラスでは、平均してO(1)の時間計算量が得られると教えられます。 それらは多くの用途でうまく機能します。 しかし、メモリ使用量とキャッシュフレンドリーさを最大のスループットのために最適化しようとしている場合、それらはそうではないかもしれません。 当初、フォワーディングポインタを使用したくなかった理由として、メッセージ送信時にオブジェクトをコピーするためにも同じコピーアルゴリズムを使用しており、そのプロセス中に送信者のヒープにあるオブジェクト（またはオブジェクトヘッダー）を上書きしたくなかったことを述べました。 しかし、その問題には簡単な解決策があります。この特別なケースでは、転送されたオブジェクトのリストを保持し、コピー後にフォワーディングポインタの書き込みを元に戻すために戻ることができます。 これは非効率に聞こえますが、実際には、他のアクターに送信されるメッセージは、ほとんどの場合、オブジェクトの巨大なグラフではない可能性が高く、通常のGC使用はこのステップをスキップできます。 この時点で、私はPlush GCを単純に従来のCheneyコピーアルゴリズムに従うように書き直すことにしました。トグルにより、フォワーディングポインタを削除し、メッセージ送信の特殊ケースのためにオブジェクトヘッダーを復元するためのundo-listを格納できます。 これにより、100万個のライブオブジェクトのGC時間が7ミリ秒まで大幅に短縮され、当初の単純な実装と比較して約16.7倍高速になりました。 これは驚異的なパフォーマンス向上であり、私の20ミリ秒の目標をはるかに下回っています。 実際、約2200ポリゴンの回転する都市景観を描画する例プログラムがあります。 3Dベクトルおよび行列演算を行い、大量の一時オブジェクトを割り当てるため、GCが定期的にトリガーされます。 このプログラムに特に、GC時間は1ミリ秒未満です。 歴史的な文脈として、Cheneyは1970年に現在Cheneyアルゴリズムとして知られているものに関する論文を発表しました。 当時、彼はFerranti Atlas 2コンピューターで作業していました。 これは1960年代初頭のトランジスタ化されたスーパーコンピューターでした。 それは大きな部屋全体を占め、コアメモリを使用し、驚くべきことに、すでに初期のキャッシュ形式を持っていました。