Fil の信じがたいガベージコレクタ
(fil-c.org)- Fil-C 言語の FUGC は、並列および並行処理をサポートする先進的なガベージコレクタ
- プログラム全体を停止せず、on-the-fly（即時実行） と grey-stack Dijkstra 方式を使用
- 正確なメモリ追跡とオブジェクトを移動させない処理の設計を実装
- Safepoint の活用により、マルチスレッド環境でも安全かつ効率的なメモリ管理が可能
- 解放済みオブジェクトへのアクセス／二重解放時の例外処理など、C/Java/JavaScript スタイルの多様なメモリ管理機能を提供
Fil の FUGC（信じがたいガベージコレクタ）の概要
Fil-C は、並列・並行 on-the-fly grey-stack Dijkstra 正確非移動 ガベージコレクタである FUGC（Fil's Unbelievable Garbage Collector）を使用する
FUGC のソースコードは fugc.c で確認できるが、ランタイムおよびコンパイラのさまざまな支援ロジックなしでは動作しない
FUGC の主な特徴
- 並列処理: マーキングおよびスイープ処理を複数スレッドで同時に実行し、CPU コアが多いほど収集速度が向上
- 並行性対応: ガベージコレクタスレッドは mutator（つまりユーザープログラムのスレッド）とは別に動作し、アプリケーションスレッドは停止せず実行可能
- on-the-fly（即時実行）: グローバルな stop-the-world なしに「ソフトハンドシェイク（=ragged safepoint）」で各スレッドが非同期にスタックスキャンなどの特定処理を行う
- grey-stack 方式: スレッドスタックを何度も固定点に達するまで再検査してマーキングを繰り返し、この過程で追加オブジェクトが見つかれば再度マーキング処理を進める
- 単純な store barrierを活用し、load barrier は不要
- Dijkstra barrier: マーキング中にヒープやグローバル変数へポインタを保存すると、同時に対象オブジェクトもマーキング
- 正確収集: すべてのポインタ位置をランタイムが正確に追跡し、GC は実際のオブジェクトのみを探索
- オブジェクト非移動処理: オブジェクトのメモリ位置が変わらないため、マルチスレッドでの並行収集と同期化が容易
- advancing wavefront 設計: mutator がコレクタの作業量を増やすことができず、マーキング済みオブジェクトはその収集サイクル中ずっと維持される
- 増分収集: 一部のオブジェクトは収集開始時には生存していても、サイクルの途中で解放されうる
Safepoint（安全地点）およびスレッド管理
- Pollcheck: コンパイラが定期的に pollcheck を挿入し、高速経路では単純な分岐、低速経路では GC 関連コールバックを実行
- ソフトハンドシェイク: すべてのスレッドに pollcheck コールバックの実行を要求し、完了まで待機
- enter/exit 状態管理: 長時間ブロッキングする関数やシステムコールなどで pollcheck を省略する場合、collector が直接そのコールバックを実行
- マルチスレッド対応環境で競合状態の防止と安全なポインタアクセスを保証
- stop-the-world モードを用いて、デバッグや fork など特殊作業を支援し、signal 処理も安定して実装
FUGC コレクタループ
- GC トリガーを待機
- store barrier を有効化した後、ソフトハンドシェイク（no-op コールバック）
- black allocation（新規オブジェクトの事前マーキング）を有効化し、キャッシュリセットコールバックを実行
- グローバルルートをマーキング
- ソフトハンドシェイク（スタックスキャンおよびキャッシュリセットコールバック）を行い、マークスタックが空なら 7 へ移動
- トレーシング（マークスタック上の各オブジェクトについて参照をマーキングし、マークスタックが空になるまで繰り返した後 5 に戻る）
- store barrier を解除し、スイープ準備を行い、キャッシュ再リセットのソフトハンドシェイク
- スイープ（まだスイープされていないページには black、既に完了した場所には white として割り当て）
- ループに再突入
既存研究との差別化および最適化
- FUGC は DLG（Doligez-Leroy-Gonthier）collector に類似しているが、単純な Dijkstra barrier と grey stack の活用により、store barrier の実装が直感的で高性能
- 固定点方式により高速に収束し、コストも低い
- bitvector SIMD ベースのスイープにより非常に高速な解放処理を実現し、GC 全体時間の 5% 未満しか消費しない
- Verse heap config の活用などによる性能最適化
ボーナス機能（メモリ管理の拡張性）
オブジェクト解放
- C の
free呼び出し時、オブジェクトを即座に free としてフラグ付けし、その後のアクセス時にトラップを発生 - dangling pointer による GC の誤動作を防止
- 解放済みオブジェクトへの参照は singleton free object にリダイレクトされ、メモリ再割り当て後でも確実に検出可能
- 使用されないポインタによって GC が誘発するメモリリークを防止
ファイナライザ
- Java スタイルの finalizer queue をユーザー指定キューおよびスレッド処理によって柔軟に実装可能
弱参照
- Java の
weak referenceと同様に動作し、別個の reference queue はない（phantom, soft reference は未対応）
WeakMap
- JavaScript の WeakMap に似ているが、すべての要素の反復および要素数の確認が可能
結論と意義
FUGC により、Fil-C は free の誤用に対して強力な安全性と直感的な例外処理を提供する
- 解放済みオブジェクトへのアクセス、または二重解放時には必ずトラップが発生するよう設計
- オブジェクトを解放しなければ GC が責任を持って適切に回収する
- 多様なメモリ管理パターンをサポートし、既存の C/Java/JavaScript 開発者にも親しみやすい環境を提供
1件のコメント
Hacker Newsの意見
うーん、Fil-C は本当に大きな意味を持ち得る気がする。C コードとしてしか存在しないソフトウェアがたくさんあるので、それを保守するためのアプローチが必要だと思う。既存の C コンパイラは単一コア性能を最大化するために大きなセキュリティリスクを受け入れているが、そうしたトレードオフはもう時代遅れに感じる。CPython、SQLite、OpenSSH、ICU、CMake、Perl5、Bash など、サポート一覧は本当にすごい。あのソフトウェア群のどれも Rust で書き直される可能性は低いと思う。Fil-C を MMU のない環境で、相互に信頼できないプロセス間のマルチタスクにも活用できるのか気になる。権限ベースのセキュリティ、ノンブロッキング同期など、正しい方向を向いているように見える。実際に使ったことのある人がいるのか知りたい。実際には最悪の場合でも 4 倍程度遅くなるという報告だが、名前が本当に面白い。フィルズウェイ！ フィルズウェイ！
Fil-C で MMU のないコンピュータ上で信頼できないプロセス間のマルチタスクが可能か、という質問については、基本的に FUGC は OS の MMU 依存機能に基づいているものの、そうした依存を除いた版も作れると思う。性能については、4 倍遅くなるのは最悪のケースで、その数値は自分で報告した。常に現実的に性能を測定し、しつこく性能問題を改善していく性格だ。実際、Fil-C 版のソフトウェアでも普段よく使うプログラムを無理なく使えている
サポートソフトウェア一覧が印象的とのことだが、一般論には同意しつつ、挙げられていた例については少し違う見方をしている。CPython や Perl5 などは、もともと GC が遅いことで有名な言語のランタイムなので、そこに GC をもう 1 つ載せるのはあまり美しい設計ではなく、むしろ速度低下が大きいかもしれない。また、Rust や Go などで再実装または置き換えようとする試みはすでに一部あり、たとえば SQLite には Turso がある。さらに、こうしたソフトウェアは非常に活発に保守されている本流プロジェクトなので、いずれ自前でリファクタリングや Rust への移植を行う可能性もあると思う。むしろ Fil-C がより適しているのは、保守が手薄で、性能への感度が低い一方で使われ続けている、50 年前の C プログラムのように誰かがときどき引っ張り出して使うようなコードだと思う
SQLite が C で書かれている利点は、非標準 OS への移植性が高いことだ。たとえば組み込み向け RTOS の μC/OS-II で直接使ったことがある。組み込み環境の設計は PC/サーバーとはかなり異なり、性能とメモリ断片化防止のため、メモリを解放せずオブジェクトや構造体を再利用するように設計することがある。カスタムヒープ割り当てやプーリングのような概念だ。SQLite の VFS ドキュメント、Micro-Controller OS の紹介
例として挙げた C ソフトウェア群が Rust で書き直されることはないと言っていたが、AI ベースの静的解析ツールが発展して C コードの問題点を正確に見つけ、「ここはエラーになる、こう直せばよい」というフィードバックを返せるようになるまで、あとどれくらいかかるのか気になる。そういうツールが本当に出てくれば、C をそのまま使い続けてもよくなるかもしれない
Fil-C はまだ 32 ビット（あるいはそれ以下）のシステムをサポートしていない点に注意してほしいという意見。Fil-C の Invisicaps 関連文書
こういうプロジェクトは、研究と実用を同時に追っている珍しい例に感じる。こういうことは普通、大手 IT 企業がチームを置いて広告収益で回していることが多いが、Fil-C はどんな背景から始まったのか気になる。単なる個人の情熱プロジェクトでないなら、誰が資金を出し、何年分の人的投入があり、最終目標は何なのか知りたい
個人的には、これは情熱プロジェクトのように見える
最終目標は何か、という質問に対しては、プロジェクトの著作権表示が 2024-2025 Epic Games, Inc. になっている
Fil-C の存在自体がうれしい。こういう技術は実際のプログラムに有効なのに、開発者が「そんなの無理だ」と信じていることが多いが、実装可能だという事実だけでも数多くの議論を一気に終わらせる力がある
ベンチマーク結果が気になる。このアプローチに対する最大の懸念は、C/C++ が今なお人気のある特定用途で性能がとてつもなく落ちるのではないかという点だ。スループットやレイテンシ、メモリ使用量が Go のような言語とあまり変わらなくなってしまうと、結局それを選ぶ理由があまり残らない気がする
プログラミング言語では、アセンブリ時代から性能をめぐる言説が常に存在してきた。ただ、ほとんどの開発者は Ivan Suntherland、Alan Kay、Steve Jobs、Bret Victor のような並外れたビジョンを持つ人ではなく、目の前で実際に動くものを見て信じる普通の人だ。だから今でも UNIX と C の複製があふれ、新しいものを創造するより過去のビジョンをそのまま踏襲して生きている場合が多いように思う。もちろん 1970 年代当時に UNIX と C を作った 2 人も偉大なビジョナリーだった
なぜ advancing wavefront 方式ではなく retreating wavefront 戦略を使わなかったのか気になる
既存の C プログラムに free(...) 呼び出しがすでに適切に入っていて、すべてのポインタについて個別の範囲情報まで管理しているなら、なぜフル GC を選んだのか気になる。代わりに lock-and-key 方式の temporal checking 手法（参考: 論文リンク）のほうが、メモリ使用量の予測可能性や性能、スケジューリングの面で優れているかもしれないと思う。おそらく key の保存領域が大きすぎるとか、確認に時間がかかるとか、マルチスレッド環境でレースコンディションが起きるといった問題があるのではと推測している
lock and key 方式には Fil-C 独自の賢い特徴がない。Fil-C の capability モデルは完全にスレッドセーフで、多くの場合に特殊な atomics や locking を必要としないのが強みだ
さらに、ポインタ逆参照を伴わない範囲外ポインタ演算を許可している点が興味深い。コンパイラはしばしばこの種の UB を利用して最適化を行うが（Stack Overflow の関連質問）、Fil-C 内部の LLVM ではそうした最適化を無効にしているのか、それともポインタを「ベース + オフセット」の組で管理してそもそもそうした可能性を断っているのか気になる。もしそうなら、通常のポインタに適用される特定の最適化を取り逃がすことにならないのかも気になる
本当にすばらしいプロジェクトに見える。pollcheck の fast path が単なる load-and-branch である点に注目した。こうしたブランチの代わりに使う興味深い技術があり、Android 公式ブログの "暗黙の suspend チェック" に関する記事 によくまとまっている
GC 付きで並行性をサポートする C、それも non-moving GC だという点が本当に驚きだ。もし中規模の C プロジェクトで、実行時性能を 2〜3 倍犠牲にする代わりにメモリバグを減らせるなら、十分受け入れる気がある。段階的導入がどれだけ容易なのか気になる。ターゲットごとに可能なのか、それともツールチェイン全体を置き換える必要があるのか知りたい
私は C と性能、そしてセキュリティのすべてを重視している。この GC と capability 構造は魅力的だ。「より安全な C」がどんな姿になるか何度も考えたことがあり、capability の概念も何度か検討したが、私はコンパイラコードはあまり扱えない。Windows 対応が難しいのか気になる
GC でルートオブジェクトをどう追跡するのか気になる。GC が走査するルートをあらかじめ印づけるコンパイル段階でもあるのか、誰かわかる人が説明してほしい
このプロジェクトには本当に驚かされる。これまで聞いたことがなかったのが不思議なくらいだ。一度実際に使ってみるのが楽しみだ。性能上の制約で本番サービスには厳しいかもしれないが、一部プログラムの安全性を自分で検証する手段としては本当に有用そうだ。普段使っている sanitizer より包括的に感じる