君のRustは20倍遅い
Rustはデフォルトでは本来の力を発揮しない。試しに手頃なベンチマークを3個くらい試したらだいたい20~100倍程度遅かった。
「Rustで ○○ を高速にする方法」が知りたい人は、まず、Rustコンパイラが本来の力を発揮しているか確認したほうがよい。
Cargoの場合
Cargoでは --release
をつけると本来の力を発揮してコンパイルする。
$ cargo build --release $ cargo run --release
rustcを直接実行する場合
$ rustc -C opt-level=3 -C debug_assertions=no
上記のオプションを設定しない理由
逆に、上記のオプションを使わない理由としては、デバッグモードのほうが諸々のチェックが実行されてよいというのが挙げられる。
例えば、整数演算のオーバーフローはデバッグモードでは捕捉される。なお、オーバーフローせずに巡回するような計算をしたい場合は wrapped_add
などの専用関数を使うべきである。
より詳しくは
rustcは以下のオプションを受けつける。
- 最適化オプション
-C opt-level=0
最適化しない (デフォルト)-C opt-level=1
少し最適化する-C opt-level=2
最適化する (略記:-O
)-C opt-level=3
積極的に最適化する-C opt-level=s
プログラムサイズを最適化する (nightlyのみ)-C opt-level=z
積極的にプログラムサイズを最適化する (nightlyのみ)
- デバッグ情報
- デバッグアサート
- リンク時最適化
-C lto
LTO(リンク時最適化)を有効化する (デフォルトは無効)
- パニック戦略
-C panic=unwind
パニック時にdropを呼びながらスレッドのスタックフレームを遡る (デフォルト)-C panic=abort
パニック時にプログラムを即時終了する
cargoはオプションに基いてプロファイルを1つ選択する。 Cargo.toml
からプロファイルの情報を取り出し、上記のオプションを設定する。Cargo.toml
のプロファイルのデフォルト設定はcargoのマニュアルページに書いてある。
Rust構文解析器のトークン分割戦略
他の多くの言語と同様、Rustの字句解析器は貪欲にトークンを分割する。しかし構文解析の途中で必要に迫られて、さらに細かくトークンを分割する場合がある。
先にまとめ
以下の場合は、構文解析のタイミングで字句がさらに細かく分割される。
- 式の位置に、前置の
||
が出現した場合。 - 型・式・パターンの位置に、前置の
&&
が出現した場合。 - ジェネリクス引数や、修飾パスが期待される位置に、
<<
が出現した場合。 - ジェネリクス引数や修飾パスの内部の
>
が期待される位置に、>>
,>=
,>>=
が出現した場合。
本編
他の多くの言語と同様、Rustの字句解析器は貪欲にトークンを分割する。
これは例えば次のようなコードを実行するとわかる。
macro_rules! stringify_each { ($($x:tt)*) => { stringify!($($x)/ *) } } fn main() { println!("{}", stringify_each!(abc a b c)); println!("{}", stringify_each!(1.1.1.1.1)); println!("{}", stringify_each!(&&&&&)); println!("{}", stringify_each!(|||||)); println!("{}", stringify_each!(<<<<<)); println!("{}", stringify_each!(>>>>>)); println!("{}", stringify_each!(=====)); }
abc / a / b / c 1.1 / . / 1.1 / . / 1 && / && / & || / || / | << / << / < >> / >> / > == / == / =
ときには、この分割戦略が直感に反した挙動をすることがある。スペースで明示すれば対処できる話だが、いくつかのパターンでは構文解析時にリカバリーする戦略が取られている。
||
の処理
|
を含む字句は |
, ||
, |=
の3つであり、以下の場面で使われている。
これらの組み合わせで問題になるのは、クロージャの引数が0個の場合 | | { .. }
である。
Rustではこれを || { .. }
とも書けるようになっている。この実装はシンプルで、クロージャの予期される位置に ||
が出現したら引数なしと判断するだけでよい。
&&
の処理
&
を含む字句は &
, &&
, &=
の3つであり、以下の場面で使われている。
- ビットごとの論理積
&
とその複合代入&=
- 短絡回路論理積
&&
- 参照型
&
,&mut
およびそのselfショートカット&self
,&mut self
- 参照をとる操作
&
,&mut
- 参照外しパターン
&
,&mut
これらの組み合わせではいくつかの問題が発生しうる。最も考えやすいのは、二重参照の場合 & & x
である。
fn f(x: &&u32) {}
Rustでは上記のようなソースコードも正しくパースする。これはexpect_and
という関数で実現されている。この関数は以下のような動作をする。
つまり、参照型・参照操作・参照外しパターンのいずれかが期待される場所に &&
が現れたら、そのトークンは動的に2つの &
に分割される。これにより上記のようなソースコードが正しくパースされるようになっている。Rustパーサーは深いバックトラックは行わないように設計されているため、復元処理は必要ない。
なお、A && B
と A & &B
はどちらも構文的にありえるため、この位置に &&
が来ても分割は行われない。
fn main() { println!("{}", &1 & &2); // println!("{}", &1&&2); // Error }
<<
と >>
の処理
<
, >
を含む字句は <
, >
, <=
, >=
, <<
, >>
, <<=
, >>=
, <-
, ->
, =>
である。 (<-
はplacementと呼ばれるunstable機能のためのトークン)
- 比較の二項演算
<
,>
、<=
、>=
- 左/右シフト
<<
,>>
とそれらの複合代入 - placement
X <- Y
fn
やFn*
系トレイト、トレイト定義における戻り値型->
match
の腕=>
- ジェネリクス引数の開始と終了
< .. >
,::< .. >
- 修飾パスの開始
<SomeType>::
,<SomeType as SomeTrait>::
なお、ジェネリクス引数の <
, >
と二項演算子としての <
, >
は、構文レベルで注意深く区別されている。
この中でトークン分割が問題になるのは、 <<
, >>
がジェネリクスの文脈で出てくる場合である。例えば、
fn main() { let x:Vec<u32>=Vec::<<u32 as ::std::ops::Add<u32>>::Output>::new(); let x:Vec<Vec<u32>>=vec![]; }
は >=
, >>=
, >>
, <<
が分割され、正しくコンパイルされる。
二項演算子の位置では <<
を分割することはできないから、以下のような場合はパースできない。
fn main() { println!("{}", 0 < <u32 as ::std::ops::Add<u32>>::add(1, 2)); // println!("{}", 0 <<u32 as ::std::ops::Add<u32>>::add(1, 2)); // Error }
0.0
の処理
次のような場合はエラーになる。
fn main() { println!("{}", ((0, 1), (2, 3)).0.0); // Error }
ドットの直後に浮動小数点数が来る場合は、このように2つのフィールドの組み合わせを意図していると考えられる。コンパイラは、曖昧性をなくすために括弧をつけることを提案してくれるが、そのまま解釈はしてくれないようだ(1.16.0時点)。
括弧をつけるのではなく、スペースをつけることで回避することもできる。
fn main() { println!("{}", (((0, 1), (2, 3)).0).0); println!("{}", ((0, 1), (2, 3)).0 .0); }
このパースが通るようにするのは原理的には可能であるように思えるが、少なくとも現在は実行されていない。
Rustでグラフを表現するにはTyped Arenaが便利
概要: Rustでグラフのように相互参照を含むデータ構造を表現するには、Typed Arenaという方法が適している。これについて説明する
整数による表現
グラフの表現方法で、最も簡単なのは、ノードを整数で表し、グラフのデータを別に持つ方法である。
fn main() { let mut edges = vec![vec![]]; edges[0].push(0); edges.push(vec![]); edges[1].push(0); }
これは大抵どんな言語でも同じように使えるし、場合によってはこちらで済ませてしまったほうが簡単かもしれない。特に競技プログラミングではノードに付与されている情報が少なかったり、ノードに明示的に整数が付番されていたりするため、ほとんどの場合整数で表現するほうが扱いやすい。
しかしこの方法では、整数とグラフデータとの対応関係を見失いやすいと考えられる。整数を別の構造体で包んだり、indexingというライブラリを使うなどして、マーカーをつける手はあるが、それにしてもやや面倒なことが多い。
参照による表現の問題点
そこで、ノードを構造体で表し、その参照を持ち回すことを考える。
ノードは複数の別のノードから参照されるから、 &mut
は使えない。しかしグラフを途中で変更する必要が出るかもしれない。そのような場合、つまり &
をimmutable referenceではなくshared mutable referenceとして使いたいときは、 RefCell
を使うのであった。
例えば、グラフのノードは以下のように表現できる。
use std::cell::RefCell; struct NodeData<'a> { references: RefCell<Vec<Node<'a>>> } type Node<'a> = &'a NodeData<'a>;
この定義自体は問題ない、しかしグラフを次のように構築しようとすると問題が発生する。
fn main() { let node0 = NodeData { references: RefCell::new(vec![]) }; node0.references.borrow_mut().push(&node0); let node1 = NodeData { references: RefCell::new(vec![]) }; node0.references.borrow_mut().push(&node1); }
rustc 1.16.0 (30cf806ef 2017-03-10) error: `node1` does not live long enough --> <anon>:13:1 | 12 | node0.references.borrow_mut().push(&node1); | ----- borrow occurs here 13 | } | ^ `node1` dropped here while still borrowed | = note: values in a scope are dropped in the opposite order they are created error: aborting due to previous error
要するに、ノードは相互に参照しあうため、きっかり同一の生存期間を持たなければならない。
ノードの個数が決まっていれば、次のように Vec
で確保するといった方法をとることができる。
use std::cell::RefCell; struct NodeData<'a> { references: RefCell<Vec<Node<'a>>> } type Node<'a> = &'a NodeData<'a>; fn main() { let mut nodes = vec![]; nodes.push(NodeData { references: RefCell::new(vec![]) }); nodes.push(NodeData { references: RefCell::new(vec![]) }); let node0 = &nodes[0]; let node1 = &nodes[1]; node0.references.borrow_mut().push(node0); node0.references.borrow_mut().push(node1); }
しかし、この方法では、動的にノードを追加することはできない。
Typed Arena を使ったメモリ確保
Typed Arenaと呼ばれるライブラリを使うと、同一生存期間を持ったメモリを複数回に分けて確保することができる。
Typed Arenaは、 arena
crateの arena::TypedArena
と typed_arena
crateの typed_arena::Arena
がある。これらはほぼ同じ内容だが、 arena
はコンパイラ内部で使うためにあり、通常はnightlyでしか使えない。通常の用途では typed_arena
を使う。
[dependencies] typed-arena = "1.2.0"
extern crate typed_arena; use std::cell::RefCell; use typed_arena::Arena; struct NodeData<'a> { references: RefCell<Vec<Node<'a>>> } type Node<'a> = &'a NodeData<'a>; fn main() { let nodes = Arena::new(); // mut は不要 let node0 = nodes.alloc(NodeData { references: RefCell::new(vec![]) }); node0.references.borrow_mut().push(node0); let node1 = nodes.alloc(NodeData { references: RefCell::new(vec![]) }); node0.references.borrow_mut().push(node1); }
まとめ
相互参照を含むデータ構造では2つの問題があり、それぞれに解決策がある。
- 複数の参照を保持しつつ、データを書き換えたい場合がある。→
RefCell
を使う。 - 相互に参照するため、同一生存期間をもつデータを複数用意したい。→ 最初に一括で確保するなら
Vec
等でよい。動的に確保したければtyped_arena::Arena
(またはarena::TypedArena
) を使う。
TypedArena
はRustコンパイラでも使われている。例えばインポート解決はグラフを扱うため TypedArena
を用いる。
Rustの基本型の名前解決
Rustの基本型の名前はキーワードではない。したがって基本型の名前は名前解決と同時に処理されることになる。ところがややこしい点として、基本型と同名のモジュールに解決される場合もある。この挙動について調べた。
基本型の名前は PrimitiveTypeTable::new
で列挙されており、以下の名前を含んでいる。
bool
char
i8
,i16
,i32
,i64
,i128
,isize
u8
,u16
,u32
,u64
,u128
,usize
f32
,f64
str
なお、これらに含まれない(記号で表される)基本型としては、&'a T
, &mut 'a T
, *const T
, *mut T
, [T; n]
, [T]
がある。処理系が特別扱いする Box<T>
, PhantomData<T>
, NonZero<T>
, UnsafeCell<T>
なども基本型に準じると考える場合があるかもしれない。
基本型の名前の処理は resolve_qpath
の中 で行われている。QPathは式や型などに出てくるものであり、例えば use
のパスはこの処理の対象外であり、常に通常の名前として解決されるということになる。
このコードによると、パスの最初の要素が基本型として処理される条件は
- パスはQSelf (
<A as Foo>::
のような部分) を含まない。 - パスの最初の要素が、上記の基本型の名前のいずれかである。
- パスの最初の要素が、型名前空間で解決されようとしている。
- 通常の方法でのパスの解決に失敗したか、またはパス全体が正規モジュール(ルートモジュールまたは
mod
)に解決された。
である。
これにより、例えば
use std::f64; fn main() { let x : f64 = 0.0f64; println!("{}", f64::sin(f64::consts::PI + x)); }
というコードがうまく動作することになる。ここで、 x
の型と、 f64::sin
の f64
は、基本型に解決される。一方、 f64::consts::PI
の f64
は、 ::std::f64
モジュールとして解決される。
ソースコードには、この挙動は「後方互換性のため」と書いてあるが、これが将来のサポート廃止を意図しているのか、そうではないのかは、判断がつかない。(少なくともサポート廃止という話を聞いたことはない)
なお、以下の2つは別の場所で解決される。
Rustのモジュールの復習
以前名前解決についてまとめたが、やはり調べ損ねている部分があるので、もう一度まとめてみた。
DefとModuleとNameBindingKind
DefId
はRust中に出現する定義(enum
, enum
のバリアント、 fn
, let
, macro_rules! foo
など)を指している。これはcrateのID + crate内の識別番号で表される。 Def
は大雑把に言うと DefId
に追加の情報を加えたものである。
Rustの(広義の)モジュールはModuleData
で表されている。広義のモジュールは以下からなる。
- 各crateのルートモジュール
mod
enum
trait
- ブロック
ブロック以外は Def
でありしかも名前をもつため ModuleKind::Def(Def, Name)
で定義される。一方ブロックは ModuleKind::Block(NodeId)
で定義される。
モジュールには様々な名前を束縛することができる。束縛される値は NameBindingKind
で列挙されている。
NameBindingKind::Def
:Def
NameBindingKind::Module
: 狭義のモジュール (ルートモジュールとmod
)NameBindingKind::Import
:use
親モジュール
広義のモジュールは高々1つの親モジュールを持つ。これによりモジュールは森構造をなす。根となるのは各crateのルートモジュールのみである。
モジュールの親子関係はASTの祖先/子孫関係と対応していると考えてよい。
親子関係は、次に述べる正規祖先と組み合わせて super
の解決に用いられるほか、可視性の基準に用いられる。
正規祖先
親リンクとは別に、各モジュールは正規祖先へのリンクを持つ。正規祖先は以下のように定義される。
- 狭義のモジュール (ルートモジュールと
mod
) の正規祖先はそれ自身である。 - それ以外 (
enum
とtrait
とブロック) の正規祖先は、その親モジュールの正規祖先である。- 現行のソースを見る限り、内部的には、非ローカルcrateの
enum
の正規祖先はそれ自身であるように見えるが、これはよくわからない……
- 現行のソースを見る限り、内部的には、非ローカルcrateの
正規祖先へのリンクは DefId
で保持しているが、利用するときは Module
を取り出す。
正規祖先は super
/self
の解決に用いられる。
解決
各モジュールは解決の一覧を持つ。解決は以下のような辞書エントリである。
- キー: 識別子と名前空間(型、値、マクロのいずれか)の組。識別子は非衛生化された状態で保存される。
- 値:
NameBindingKind
と衛生性マークと可視性の組。
パスの種類
パスは以下の3形式のいずれかからなる。
- 相対パス:
self
またはsuper
と、追加の0個以上のsuper
から始まるもの。- ただし、
self
のみからなり、型またはモジュール以外の文脈の場合は、レキシカルスコープのパスとして扱われる。
- ただし、
- 絶対パス:
::
または$crate
から始まるもの。 - レキシカルスコープのパス: 通常の識別子のみ(1個以上)からなるもの。
相対パスの場合、 self
と super
は以下のように解決される。
self
は、現在のモジュールの正規祖先である。super
1個につき、「親モジュールの正規祖先」を辿る操作が1回行われる。
絶対パスの場合、解決の開始位置は以下のように決定される。
::
の場合、ローカルcrate (現在コンパイル中のcrate) のルートモジュールから解決が開始される。$crate
は、該当マクロ定義のあったcrateのルートモジュールから解決が開始される。詳しくは過去の記事を参照。
レキシカルスコープのパスの場合、最初の識別子はレキシカルスコープで解決される(後述)。
レキシカルスコープからの解決
レキシカルスコープはコンパイラ内ではRibという単位で管理されている。Ribは以下の地点で発生する。
- ルートモジュールと
mod
:ModuleRibKind
(値と型) - 関数:
ItemRibKind
(値とラベル) enum
,type
,struct
,union
,fn
:ItemRibKind
(型)- メソッド(
trait
,impl
内のfn
):MethodRibKind
(値とラベルと型) - クロージャ:
ClosureRibKind
(値とラベル) trait
,impl
:ItemRibKind
(型)- ラベルつきブロック: NormalRibKind (ラベル)
- 配列型の長さ、バリアントの判別子、
const
,trait
のconst
: ConstantItemRibKind (値と型) trait
とimpl
: NormalRibKind (型)- matchの各節: NormalRibKind (値)
- ブロック (匿名モジュールの場合):
ModuleRibKind
(値と型) - ブロック (匿名モジュールでない場合):
NormalRibKind
(値) - block / macros_at_scope:
MacroDefinition
(値とラベル) - with_module_lexical_scope:
ModuleRibKind
(値と型) - if let, while let, for in:
NormalRibKind
(値)
各 Rib
は識別子と解決先の一覧を保持している。ただしこれらの更新のタイミングはRibの種類によって異なる。例えば、
ModuleRibKind
は、モジュールに入った時点で全ての一覧が完成した状態になる。構文上の位置は関係ない。NormalRibKind
は、モジュールに入った時点では一覧は存在せず、パス解決と同時に更新されていく。例えばlet
の前後で名前解決の挙動が違うのはこの仕様により実現されている。
resolve_ident_in_lexical_scope
は、このRibを内側から外側に順番に調べ、ローカル定義またはアイテムがあれば終了する。ただし、探索途中で、ブロック(匿名モジュール)以外の ModuleRibKind
に遭遇した場合は、この探索を打ち切る。この規則により、上位モジュールでの use
が下位モジュールに影響を与えるのを防いでいる。
なお、レキシカルスコープからの解決では、値名前空間は構文文脈を含めた状態で解決されるが、型名前空間は識別子を非衛生化した状態で解決される。
use
のレキシカルスコープ解決
use
に出現するパスは、他のパス解決よりも前に行われる。このときはRibはルートモジュールのみ存在するため、レキシカルスコープのパスは絶対パスとほぼ同じ意味になる。
パスの途中の要素の解決
パスの要素について、名前空間は以下のように決定される。
パスの途中の要素の解決は、だいたい想像される通りのことが起こっている。ただし識別子は非衛生化される。
また、パス解決が途中で失敗した場合(直前がモジュールでなかった or モジュールだったが、名前を検索しても見つからなかった場合)も、この時点ではエラーにはならない。残りの部分は関連型やメソッドなどの名前かもしれないからである。この時点では、パスのどの要素まで解決されたかを含めて返し、残りはloweringや型検査の途中で処理することになる。
まとめ
とりわけ注意が必要なのは以下の点
Rustの文でセミコロンを省略してよい条件
Rustの文でセミコロンを省略してよい条件を説明する。
意味論的な原則
Rustのセミコロンは意味と構文からそれぞれ説明できる。意味論的には、以下の原則を覚えておけば十分である。
- セミコロンで終端された文は強制的に
()
型となる。 - ブロックの途中の文は
()
型でなければならない。ブロックの型はブロックの最後の文の型と等しい。(文がひとつもない場合は()
)
fn main() { let x = { let x = 10; x + 1 }; // x + 1 を返したいので、セミコロンをつけてはいけない if true { 1 } else { 0 }; // 構文上は省略できるが、 () 型にするためにセミコロンをつける println!("Hello!\n"); // 値を返したいわけではないので、セミコロンをつける }
構文上の大原則
大原則は、「文同士はセミコロンで区切らなければならない。ただし }
で終わる文のセミコロンは省略できる」である。
しかし実際には以下の例外を考慮する必要がある。
例外1: }
で終わる式文の場合
文は式文、let文、文マクロ、アイテム文 にわかれている。式文は、式をそのまま文とみなすという規則のことである。
if
, if let
(else
を含む), while
, while let
, loop
, for in
, match
およびブロック式は }
で終わる(これらはC/C++では文だが、Rustでは式であることに注意)。これらの式のパースは、特定条件下で打ち切られる。具体的には、以下の2つの条件を満たしている必要があるようだ。
- これらの式の直前に別のトークンがパースされていない。例えば、
let x = if ..
,(if ..
,1 + if ..
は対象外となる。 - これらの式の直後に
?
や.some_method(..)
が後続しない。例えば、{ }?
や{ }.f()
は対象外となる。
例えば以下の例で、最初の if
文は }
でパースが打ち切られている。しかし、次の if
文は ( 10 )
まででひとつの文となる。つまりこの main
関数には3つの文があることになる。
fn f(x: u32) -> u32 { println!("f({})", x); 10 } fn main() { if true { () } else { () } ( 10 ); 1 + if true { f } else { f } ( 10 ); }
(なお、この打ち切り規則はRESTRICTION_STMT_EXPRと呼ばれ、式文のほかに match
の各節の右辺にも適用される。)
例外2: let
文の場合
let
文ではセミコロンの省略はできない。これはブロックの末尾でも同様である。
fn main() { let x = if true { 0 } else { 0 }; // セミコロンが必要 let x = 0; // セミコロンが必要 }
例外3: }
で終わる文マクロの場合
マクロは {}
, ()
, []
のいずれの括弧でも呼び出せるが、括弧の種類によって構文上の挙動が変わる。文の位置に出現するマクロについては、 {}
で呼び出すとセミコロンを省略できる。
fn main() { println!{"Hello!"} println!{"World!"} }
ただし、書いたマクロが文マクロとして認識されるか、式マクロとして認識されるかには注意が必要である。具体的には以下の条件でマクロが文マクロと認識される。
- 文の位置で始まっている。例えば
1 + foo!{ }
ではfoo!{ }
は式マクロとして認識される。 {}
で呼び出されているか、または;
で終端されている。例えばfoo!{} - 1;
やfoo!(); - 1;
は2つの文として解釈されるが、foo!() - 1;
は1つの文として解釈される。
例外4: }
で終わるアイテム文の場合
アイテムのうちセミコロンを必要としないものは、アイテム文でも同様にセミコロンを必要としない。
fn main() { struct A {} // セミコロン不要 let x = A {}; }
まとめ
Rustの文におけるセミコロンは、意味論的には「型を ()
に強制するために必要」、構文的には「区切り文字として必要。ただし }
の直後では不要」という原則を理解すればそれほど難しくはなさそうだ。しかし、実際には構文解析の一貫性等の問題から、この原則に対する例外があることは、記憶の片隅に留めておいてもいいかもしれない。