OCamlのGCでRustのGCを実現：Soteria Rustが10倍高速化
Meta Garbage Collection: Using OCaml's GC to GC Rust
Soteria RustはRustプログラムのシンボリック実行ツールで、未定義動作やエイリアシングエラーを検出します。最近、単純なループがNの2乗時間かかる問題に遭遇しました。原因はTree Borrowsの実装にあり、各反復でツリーに9ノード追加され、10回アクセスされるため、合計で45N²回のノードアクセスが発生していました。しかし、SoteriaはOCamlで書かれているため、OCamlのガベージコレクタを利用して不要になったツリーノードを回収する「メタGC」を約40行で実装。これにより、実行時間を2次から線形に改善し、最大10倍の高速化を達成しました。
SoteriaはOCamlで書かれているため、Tree Borrowsの状態のガベージコレクションをOCamlのガベージコレクタに委任できます。約40行のコードで、2次時間から線形時間へと改善し、最大10倍の高速化を実現しました。