ハクソク

世界を動かす技術を、日本語で。

フィルの信じられないゴミ収集機

263日前原文(fil-c.org)

概要

Fil-CのFUGCは、並列・並行動作し、正確かつ非移動型のDijkstraバリア方式GC。 スレッド停止を最小限に抑え、独自のグレイスタックで効率的なマーク＆スイープを実現。 safepointやstore barrierなど、最新のGC技術を多数導入。 C/Java/JavaScript風のメモリ管理機能（free, finalizer, weak ref等）もサポート。 使い勝手と安全性の両立を目指した設計。

FUGC（Fil's Unbelievable Garbage Collector）の特徴

  • 並列処理 ：マークとスイープを複数スレッドで同時実行
  • 並行動作 ：マーク＆スイープはmutator（プログラム）スレッドとは別のスレッドで進行
  • オンザフライ ：グローバルなstop-the-worldは不要、ソフトハンドシェイクで最小限の介入
  • グレイスタック方式 ：スレッドスタックを再スキャンし、fixpoint収束までマーク処理を繰り返す設計
  • Dijkstraバリア ：ストアバリアのみ必要、ヒープへのポインタ格納時に新たな参照オブジェクトをマーク
  • 正確なGC ：スタックやグローバルのルートポインタをLLVMパス（FilPizlonator）で厳密に追跡
  • 非移動型 ：オブジェクト自体は移動せず、解放時のみcapabilityポインタをfree singletonへリポイント
  • アドバンシングウェーブフロント ：mutatorがGCの新たな作業を生まない設計
  • インクリメンタル更新 ：GC中に解放されたオブジェクトも即時回収
  • safepoint活用 ：pollcheckによる周期的な安全点、スレッド同期や信号配信も安全に管理
  • 高速スイープ ：bitvector SIMDによる圧倒的なスイープ速度、Verse heap構成を活用

FUGCのGCサイクル基本フロー

  • GCトリガ待機
  • ストアバリアON→ソフトハンドシェイク（no-opコールバック）
  • ブラックアロケーションON→ソフトハンドシェイク（スレッドローカルキャッシュリセット）
  • グローバルルートマーク
  • ソフトハンドシェイク（スタックスキャン＋キャッシュリセット）
  • 全マークスタック空ならスイープへ、残っていればトレース継続
    • マークスタック内各オブジェクトの参照先をマーク（スタック拡張も）
    • マークスタックが空になるまで繰り返し
  • ストアバリアOFF→スイープ準備→ソフトハンドシェイク（キャッシュリセット）
  • スイープ実行
    • 未スイープページからの割当はブラック、スイープ済みはホワイト
  • 終了→次のGCトリガ待機

safepointインフラとスレッド安全性

  • pollcheck ：コンパイラが頻繁に挿入、速いパスは単なるロード＆分岐
  • ソフトハンドシェイク ：全スレッドでpollcheckコールバック実行を要請
  • enter/exit ：システムコールや長時間ランタイム関数でのスレッドブロック対応
  • stop-the-world ：fork(2)やデバッグ時に利用可能（FUGC_STW環境変数）
  • 信号配信 ：safepointインフラで安全なsignal deliveryを実現
  • スレッド同期 ：GC中にヒープからポインタをロード→使用しても、次のpollcheck/exitまでメモリは削除されない安全設計

メモリ管理機能（Bonus Features）

  • free対応 ：free呼び出しで即座にtrap発生、解放後のアクセスも確実にtrap
    • capabilityポインタをfree singletonへ付け替え、解放済みメモリの再利用も安全
    • 二重freeもtrapで検出
    • freeし忘れはGCで自動回収
  • finalizer ：zgc_finq APIでJava風ファイナライザキューを実装可能
    • 任意のスレッドでファイナライザ処理を選択可能
  • weak reference ：zweak APIでJava同様の弱参照をサポート（reference queueは非対応）
  • weak map ：zweak_map APIでJavaScript WeakMap風の弱マップを実装
    • Fil-Cのweak mapは全要素のイテレーションや要素数取得も可能

FUGCと他GC手法の比較・設計意図

  • DLG（Doligez-Leroy-Gonthier）法との比較
    • Dijkstraバリア＋グレイスタックの採用でバリアコスト低減と直感的なアルゴリズム
    • fixpoint方式だが、実運用では数回のイテレーションで収束
  • bitvector SIMDによる高速スイープ
    • マークよりスイープが圧倒的に高速（通常GC時間の5%未満）
  • 幅広いメモリ管理モデル対応
    • C/Java/JavaScriptスタイルのメモリ管理を柔軟にサポート
  • 安全性と使いやすさの両立
    • free後アクセスや二重freeを確実にtrap
    • malloc/freeからGCへの移行時のリーク防止策も万全

まとめ

  • Fil-CのFUGCは、現代的なスレッドセーフGC設計と多機能メモリ管理APIを両立
  • 高速・安全・直感的なGCサイクルと、C/Java/JavaScript的プログラミング体験を両立
  • freeの誤用検出・自動回収・ファイナライザや弱参照など、実用的な機能を網羅

Hackerたちの意見

既存のCプログラム（すでにfree(...)の呼び出しが「慎重に」配置されている）と連携するのが目的なのに、なぜロック＆キー方式の時間的チェックではなく、フルGCを選んだのか気になるな。後者だとメモリ使用量がもっと予測可能になって、GCのパフォーマンスオーバーヘッドやスケジューリングの悩みを避けられると思うんだけど。もしかして、キーを保存するのにスペースがかかりすぎるとか、チェックに時間がかかりすぎるとか、マルチスレッド環境でレースコンディションの問題が出るとか？

└

ロック＆キー方式には、Fil-Cの一番の特徴である「能力モデルが完全にスレッドセーフで、一般的なケースでは特別なアトミックやロックを必要としない」っていうのがないと思う。

└

また、デリファレンスが発生しない限り、境界外ポインタ算術を許可しているのが面白いね。これはコンパイラが悪用することが知られているUBの一種だよね（https://stackoverflow.com/questions/23683029/is-gccs-option-...）。LLVMの中でそういった最適化を無効にしているのか、それともFil-Cがポインタをポインタベース + 整数オフセットに分けることで完全に回避しているのか？（その場合、ポインタに特化した最適化を逃しているんじゃないかと思うんだけど）。

自分は使えないけど、エンジニアリングオタクの視点からこのデザインスペースに本気で取り組んでいる人がいるのは本当にクールだと思う。

Fil-Cが存在するのは素晴らしいことだね。これは実際のプログラムに非常に効果的な技術だけど、開発者たちはそれがうまくいかないと信じている。存在証明が長い循環議論を打破するんだ。

└

ベンチマークはどんな感じ？このアプローチの一番の懸念は、パフォーマンスの範囲がC/C++がまだ人気のユースケースでは使えなくなることだと思う。スループットやレイテンシ、フットプリントがGoとかとあまり変わらないなら、使う場面がかなり減っちゃうよね。

└

プログラミングの悩みはアセンブリの頃から続いてるけど、残念ながらほとんどの開発者はアイバン・サザーランドやアラン・ケイ、スティーブ・ジョブズ、ブレット・ビクターみたいなビジョナリーじゃないんだよね。多くの人は、悲しいかな、貨物カルトの都市伝説に囚われて、目の前で動いてるものだけを信じている。だから、何か新しいものを作る代わりに、UNIXやCのクローンがたくさん生まれるんだ。正直言って、あの二人も1970年代にはビジョナリーだったけど、いくつかの欠点もあった。

これ、本当にクールだね！「ポールチェックのファストパスは単なるロード＆ブランチだ」というのに気づいたよ。これらのブランチを避けるために使われる面白い技術が、https://android-developers.googleblog.com/2023/11/the-secret... の「暗黙のサスペンドチェック」の下で文書化されているのを見たよ。

└

そうだね、ポールチェックのための一般的な最適化だよね。ほとんどのプロダクションJVMはそうしてると思う。自分はまだ非常に高レベルで基本的な最適化がたくさん残ってるから、そういう低レベルの最適化にはまだ遠いね！

「セーフポイント」ロジックは、参照カウントに必要なフィールドを原子的に置き換えるのと全く同じことだってことに注意してね。この記事は、私が最も難しいと考える部分—ネイティブ関数の周りのエンター/イグジット機能がブロックするかもしれない（でもアロケーターには触れなきゃいけない）っていうのを軽く流してる。

└

「"safepointing"のロジックは、参照カウントに必要なフィールドのアトミック置換と全く同じものだよ。」いや、全然違うし、近くもない。 > 「この記事は、私が最も難しいと思う部分を軽く流している。ネイティブ関数の周りのenter/exit機能はブロックするかもしれないけど、アロケーターには触れなきゃいけない。」うん、その部分は難しいね。別の投稿で説明するかも。filc_enterとfilc_exitを探してみて。

ガベージコレクターの設計と実装が大好き！新しい言語を学ぶときにやるべき「お決まり」のことの一つだよね。これについては初めて聞いたから、今週末にじっくり見てみるのが楽しみ。

「スレッドが経験する唯一の「ポーズ」は、ソフトハンドシェイクに応じて実行されるコールバックで、そのスレッドのスタックの高さに制約されている。」だから、これは関数型や深い再帰のコードにはあまり良くないかもね？

└

うーん、スタックスキャンはめっちゃ速いよ。あまりロジックが入ってないし。スタックの高さ制限を最大にすると（スタックがメガバイト単位？）、スタックをスキャンするのにミリ秒単位の作業が必要になるかも。それでも悪くはないよ。

超クールなプロジェクトだね。もしもう説明してたらごめん、「Dijkstra accurate」って何か分からないんだけど、ポインタが整数に変換できるときに、どうやってオブジェクトが本当に再利用可能かを知るの？

└

「ポインタが整数に変換できるときに？」ポインタが整数に変換されてヒープに保存されると、その能力を失うからだよ。だから、それにアクセスするとトラップが発生して、GCはそれを気にしなくて済む。あと、「Dijkstra accurate」ではないよ。Dijkstraバリアを使っているからDijkstraコレクターなんだけど、正確なコレクターでもある。これらは独立したものなんだ。

うーん、Fil-Cは本当に重要そうだね。Cコードの形でしか存在しないソフトウェアがたくさんあって、それにアクセスを保つことが重要なんだ。従来のCコンパイラが行うトレードオフ（セキュリティ問題のリスクを大きく受け入れて、シングルコアのパフォーマンスを少し改善するためのもの）がほぼ時代遅れになっているとしても。サポートされているソフトウェアのリストは驚くべきものだよ：CPython、SQLite、OpenSSH、ICU、CMake、Perl5、Bashなど。あのリストにあるものは、誰もRustで書き直すことはないだろうな。MMUのないコンピュータで、相互に信頼できないプロセス間でマルチタスクを行うためにFil-Cを使うのは現実的なのかな？彼らは能力セキュリティやノンブロッキング同期について正しいことを言っているみたいだけど。実際に使ったことがある人いる？ https://news.ycombinator.com/item?id=45134852 では4倍の遅延が報告されているみたいだね。名前が面白い。Feelthay! Feelthay!

└

「MMUなしのコンピュータで、相互に信頼できないプロセス間でマルチタスクを行うためにFil-Cを使うのは実現可能かな？」できると思うよ。ただ、FUGCの中身はMMUに依存してるOSの機能に頼ってるから、そういう依存がないFUGCのバージョンを作ることはできる。パフォーマンスについては、最悪でも4倍って感じで、その数字は俺が報告したから出てるんだ。俺は最悪のパフォーマンスを報告するのが好きで、現実的に測定して、パフォーマンスの問題を徹底的に解決することにこだわってるからね。実際、俺はお気に入りのソフトのFil-Cバージョンで生活できるし、違いを感じないよ。

└

「MMUなしのコンピュータで、相互に信頼できないプロセス間でマルチタスクを行うためにFil-Cを使うのは実現可能かな？」普通のデータフローで動くとしても、そういうのは隠れたチャネルを引き起こす可能性があると思うんだけど。まず、プロセスを切り替えるときにメルトダウンやスペクターの対策が無効になってしまうんじゃないかな？

これは、研究に近いプロジェクトでありながら、産業的に有用な結果を生み出している珍しい例の一つだね。大好きだ！普通は、こういうのは大手テック企業から出てくると思うんだけど、広告費があれば小さなチームがこういうプロジェクトに取り組むことができるからね（ビジネスケースを作れる人がいればだけど…）。それで気になるんだけど、このプロジェクトの最初の動機は何だったの？情熱的なプロジェクトじゃないとしたら、誰が資金を提供してるの？どれくらいの人月がかかってるの？最終的な目標は何？

└

「最終的な目標は何？」 * Copyright (c) 2024-2025 Epic Games, Inc. All Rights Reserved.