ハクソク

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

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

2025年9月5日原文(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を探してみて。

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

Hacker Newsで議論の続きを見る