Tree Borrows: Rust unsafeコードのエイリアシング規則モデル
(plf.inf.ethz.ch)- Rustコンパイラがポインタのエイリアシング保証を最適化に活用するには、unsafeコードがどこで規則に違反するのかを明確に定義する必要がある
- 既存のStacked Borrowsはその基準を提示したが、実際のunsafe Rustコードでよく見られるパターンや最新のborrow checker機能を十分に取り込めていない
- Tree BorrowsはStacked Borrowsの中核構造をスタックからツリーへと置き換えることで、より多くの有効なパターンを表現できるようにする
- 最も広く使われているRust crate 30,000件の評価で、Stacked Borrowsより拒否したテストケースが54%少ない
- Rocqによる証明で、既存の最適化の大半を維持しつつ、read-read再順序化のような新しい最適化も可能であることを確認した
unsafe Rustで必要なエイリアシング規則
- Rustは所有権ベースの型システムにより、メモリ安全性やデータレース防止といった強力な保証を提供する
- ただしunsafeコード領域では安全性は自動では保証されず、プログラマが守るべき別の規則が必要になる
- コンパイラは型システムの保証、特にポインタの**エイリアシング(aliasing)**に関する情報を活用して、関数内部の最適化を強化しようとする
- 誤って書かれたunsafeコードはこうした最適化を壊す可能性があるため、どのコードを「badly behaved」とみなすのかについて明確な基準が重要である
- 既存研究のStacked Borrowsはこの基準を定義したが、限界がある
- 実際のunsafe Rustコードで一般的なさまざまなパターンを拒否する
- 最近導入されたRust borrow checkerの高度な機能を反映できていない
Tree Borrowsのアプローチと評価結果
- Tree Borrowsは、Stacked Borrowsの中心構造であるスタックをツリーに置き換えて定義されている
- この構造変更により、既存モデルの制約を緩和する
- 最も広く使われているRust crate 30,000件の評価で、Stacked Borrowsより拒否したテストケースが54%減少した
- Rocqによる証明で、最適化に関する性質も確認された
- Stacked Borrowsが許していた最適化の大半を維持する
- 重要な新しい最適化であるread-read reorderingsも可能である
- Tree BorrowsはPLDI'25 Distinguished Paper Awardを受賞した
- 関連資料
1件のコメント
Hacker News のコメント
おまけに、Rust 方言で Rust の実行時意味論を実行可能な形で厳密に仕様化しようとする Ralf Jung のグループの最近の発表もある: https://youtube.com/watch?v=yoeuW_dSe0o
Torvalds は昔から、C の厳格なエイリアシング規則は利益より害のほうが大きいと主張してきたし、説得力があるように聞こえる。例はこちら: https://lore.kernel.org/all/CAHk-=wgq1DvgNVoodk7JKc6BuU1m9Un... この話題に関心があるなら、スレッド全体も読む価値がある
Rust が根本的に違うかというと、限られた経験ではそうは見えない。少なくとも unsafe が絡むとなおさら
コンパイラにはより有用で、プログラマには負担が少ないと思う。また、言語内に実際に逃げ道もある: 生ポインタを使えばよい。そしてコードを検査するツールもある
結局、言語設計のあらゆることと同じくトレードオフであり、Rust ではこうした最適化について新しい sweet spot を見つけたのかもしれないと思う。正しいかどうかは時間が教えてくれる
C には
restrictという核兵器のような仕組みがあるが、経験上 clang と gcc では関数引数に付けたときだけ何らかの効果があった。型ベースのエイリアス解析は一般に使いにくく、int64_t型の複製を無限に作ることもできないし、そうしたいとも思わないはずだ。別の型として再解釈するにはmemcpyを強制される点も厄介一方で Rust の参照は ライフタイム・スコープ・可変性が細かく境界付けられており、「物理的な」型そのものにはあまりこだわらない。そのため同じメモリを
&mut i32/&i32と&mut i64/&i64として再解釈しながら切り替えることも可能。unsafe な抽象化が同時に重なる&mut参照を渡さない、または 1 つの&mutを重ならない複数の&mutに分割する限り、普通の安全な Rust の読み書きで半分の値や複数の値を読み書きできるエイリアス解析は、今どき良い性能を得るうえで非常に重要。ただし最大の利益は最も単純なヒューリスティックから来ることも覚えておくべき。たとえば同じ SSA 値をポインタとして使う 2 つのロードは、必ず互いにエイリアスする、というようなもの
LLVM の観点では BasicAA がその役割を担う。「オブジェクトの割り当て地点を追跡できればエイリアス問い合わせを確定的に解き、できなければ分からない」に近い単純なヒューリスティック群だ
本当の問いは、基本的で明白な検査を超えるエイリアス解析の価値だ。エイリアス問い合わせがもはや自明に解けない段階になると、その結果としてできることも概して大きく減り、ほとんどコード移動の危険を見つける程度になる。その利益はずっと小さい
やってみたい実験の 1 つは、理論上完璧なエイリアス解析がもたらす総速度向上を測定すること。推測では、Linux カーネルのような非 HPC コードでも 20% 程度だと思う
[1] ここには、高品質なエイリアス解析なしには試みないようなデータ配置変換といった英雄的な最適化は含めていない。実際にはそのようなエイリアス解析は存在しないことをすでに知っているので、そうした最適化も試みないはずで、予想される速度向上に入れる価値はないと思う
C のエイリアシングは型だけに基づいており、そのため別名も 型ベースエイリアス解析または TBAA である
noaliasが実行時間ベースで約 5% の性能向上に寄与するという主張を見つけたが、資料がかなり古いのは確かだhttps://github.com/rust-lang/rust/issues/54878#issuecomment-...
https://news.ycombinator.com/item?id=22281205
https://news.ycombinator.com/item?id=17715399
&mutから*mut i32を作り、write(x)の代わりに*x = 10とすると暗黙の 2 段階借用を使わないため、コンパイラが拒否すべきだという説明に見えたが、実際には通る*x = 10;版ではエラーが報告され、write(x);版では報告されないエラーは “Undefined Behavior: attempting a write access using [...] but that tag does not exist in the borrow stack for this location” という形
rustc 自体がこのどちらかを拒否する理由はありません。
yは*mutであり、コンパイル時の型システムの観点ではxである&mutと借用・ライフタイムの関係がないためです現在の借用チェッカーはより制限的な解析を使っているため、生ポインタと可変参照の間のこの特定の衝突を検出できません
実際の経験でも [1] [2] で、Stacked Borrows では不正だが妥当なコードを許容してくれました
[1] https://github.com/Voultapher/sort-research-rs/blob/main/wri... Miri 列
[2] https://github.com/rust-lang/rust/blob/6b3ae3f6e45a33c2d95fa...
スコープベースの借用チェッカーから 非字句的ライフタイム借用チェッカーへ移行してきましたし、次の実験的な Polonius 実装もオプションとしてあります。ただし新しい実装がプロダクション対応になると、古い実装は捨てられます。選ぶ理由がないからです
借用検査は高速で、新しい実装はより多くの正しいプログラムを厳密に受け入れます
また
RcとRefCell型があり、ランタイム検査のコストを払ってより大きな柔軟性を得られますいずれも実装、性能、開発者体験の面でコストと能力が異なります
そして Rust 以外の大半が実際に目指しているのは、自動リソース管理による生産性です。方式が何であれ自動リソース管理を使い、性能が重要な経路にだけ上記の型システムのいずれかを組み合わせる形です
この文脈では「Rust」は、「人々が通常望む不変条件」と「その通常の不変条件を仮定するが、それ以上でも以下でもない最適化の集合」にすぎないと見なせます
コンパイル時間の大半はトレイト解決、単相化、LLVM 最適化パス、リンクに使われます
もしかすると馬鹿げた質問かもしれませんが、複数の実装を並列スレッドで走らせ、先に肯定的な結果を出したほうを勝ちにできないのか気になります
ポインタを使って同じ変数への複数の可変参照を同時に存在させるのは未定義動作です。論文の意図を誤解していなければ、そう見えます
上のコードは Rust コンパイラが受け入れますが、規則を破っています。どの規則を破っているのかが問題です
本質的に、借用チェッカーが受け入れるものは合法であり、unsafe は不正または未定義動作も表現できます。そして借用チェッカーが確認できるものより広いが、それでも合法で定義された動作である規則集合が存在します
この研究の目的は、その規則集合を精密に仕様化することです。大まかな輪郭は「書き込み可能なポインタは別名であってはならない」に近いですが、内部ポインタ、イテレータの無効化、悪いポインタを作ることが問題なのか使うことが問題なのか、といった細部は非常に難しいです
以前の Stacked Borrows 論文はより単純でしたが、より制限的だったため、現実の unsafe コードが規則を通過できないことがよくありました。Tree Borrows はより広く、より多くのコードを許容しながらも、証明可能に安全です
Tree Borrows はまさにそのような定義を提案するものです
ここで「コードがこのようなことをできる」という意味は、「このコードを書き、コンパイルし、実行でき、Tree Borrows のようなものがなければこのコードに問題があると主張する根拠がない」という意味です
すでにこのコードは未定義動作だと言うべきだという点、つまり Tree Borrows のようなものが必要だという点は受け入れているわけです。論文のこの部分は、なぜそのようなものが必要なのかを論じる箇所です
https://play.rust-lang.org/?version=stable&mode=debug&editio...
Rust コンパイラ開発者が別名最適化をサポートしたいのは明らかなので、上のような反例を検討対象から「除外」する方法が必要だ、という内容です
unsafe は、Rust のライフタイム解析ではコードの妥当性を証明するのが難しい場合のためのものだが、それよりはるかに多くのことをさせるために濫用されることもある