※2020/4/27 Rustのビルド結果説明に一部誤りが有りましたので修正しました。
はじめに
産目奈良部というゲームがあります。
神ゲーです。
ググった瞬間出てくるので、皆さんやってください。
概要
↓詳しいことはrustドキュメントが解説してくれています↓
Rustドキュメント(Aliasing)
例に出ているのは以下のようなコードですね。
fn compute(input: &u32, output: &mut u32) {
if *input > 10 {
*output = 1;
}
if *input > 5 {
*output *= 2;
}
}
rustなら以下のように最適化出来ますよと
fn compute(input: &u32, output: &mut u32) {
let cached_input = *input; // keep *input in a register
if cached_input > 10 {
*output = 2; // x > 10 implies x > 5, so double and exit immediately
} else if cached_input > 5 {
*output *= 2;
}
}
試しにcomputeの呼び出しを別ファイルで適当に書いて
fn main(){
let mut sin = String::new();
io::stdin().read_line(&mut sin).expect("read line failed");
let ipt:u32 = sin.trim().parse().expect("input line is no number");
io::stdin().read_line(&mut sin).expect("read line failed");
let mut out:u32 = sin.trim().parse().expect("input line is no number");
compute(&ipt,&mut out);
println!("{}",out);
}
cargo build --releaseした結果を逆アセンブルすると…
0000000000004b60 <_ZN4t1_t4t1_17compute17h17eab9469a9c984cE>:
4b60: 8b 07 mov (%rdi),%eax
4b62: 83 f8 0b cmp $0xb,%eax
4b65: 72 0d jb 4b74 <_ZN4t1_t4t1_17compute17h17eab9469a9c984cE+0x14>
4b67: c7 06 01 00 00 00 movl $0x1,(%rsi)
4b6d: b8 02 00 00 00 mov $0x2,%eax
4b72: eb 09 jmp 4b7d <_ZN4t1_t4t1_17compute17h17eab9469a9c984cE+0x1d>
4b74: 83 f8 06 cmp $0x6,%eax
4b77: 72 06 jb 4b7f <_ZN4t1_t4t1_17compute17h17eab9469a9c984cE+0x1f>
4b79: 8b 06 mov (%rsi),%eax
4b7b: 01 c0 add %eax,%eax
4b7d: 89 06 mov %eax,(%rsi)
4b7f: c3 retq
…何故だか以下のような最適化結果になってしまっていますが…
fn compute(input: &u32, output: &mut u32) {
let cached_input = *input;
if cached_input > 10 {
*output = 1;
*output = 2;
} else if cached_input > 5 {
*output *= 2;
}
}
一応if部分の最適化は行えているようですね。
何故最適化出来るのか
rustがif部分の最適化を実行できるのは、以下のようなルールが存在するからです
- rustの参照(借用)は以下どちらか一方のみしか所有することが出来ない
- 変数に対する任意個のimmutableな参照(&T)
- 変数に対する唯一のmutableな参照(&mut T)
上のcompute関数呼び出しを例に上げると
fn main(){
let mut sin = String::new();
io::stdin().read_line(&mut sin).expect("read line failed");
let mut out:u32 = sin.trim().parse().expect("input line is no number");
compute(&out,&mut out); //mutable/imutableな参照は同時に2個作成できない！
//compute(&mut out,&mut out); //mutableな参照は2個以上作成できない！(そもそも型変数が違うのであくまで例)
println!("{}",out);
}
mutableな参照+αが発生することは無いため
inputが常に固定値であることを保証出来るわけですね。
仮にmutableな参照+αが許されている場合、以下のソースはどうなるでしょうか？
fn compute(input: &u32, output: &mut u32) {
if *input > 10 {
*output = 1; //1.output==inputの可能性が有るので…
}
if *input > 5 { //2.inputの値が最初の値から書き換わっているかもしれない→if文を最大2回実行する必要が有る！
*output *= 2;
}
}
outputとinputが同一の参照先で指定された場合、2回目のif文ではinputの値が書き換わっている可能性が有ります。
なので冒頭に上げたような最適化は実行できないという理屈になります。
C++の場合
C++で上記のソースを書いた場合以下のようになりますが
void compute(const std::uint32_t & input,std::uint32_t & output) {
if(input > 10){
output = 1;
}
if(input > 5){
output *= 2;
}
}
C++ではlvalue referenceの数に制約がありません。
int main(){
std::uint32_t a,b;
std::cin >> a >> b;
compute(a,b);
compute(a,a); //同じ可能性も有る！
}
試しにgcc -O3でビルドすると
00000000000008f0 <_Z7computeRKjRj>:
8f0: 8b 07 mov (%rdi),%eax
8f2: 83 f8 0a cmp $0xa,%eax
8f5: 76 08 jbe 8ff <_Z7computeRKjRj+0xf>
8f7: c7 06 01 00 00 00 movl $0x1,(%rsi)
8fd: 8b 07 mov (%rdi),%eax
8ff: 83 f8 05 cmp $0x5,%eax
902: 76 02 jbe 906 <_Z7computeRKjRj+0x16>
904: d1 26 shll (%rsi)
906: c3 retq
907: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1)
90e: 00 00
最適化出来ずcmpを2回行ってしまっていますね
このような点から、rustはC++より高速化が見込める可能性も有ると言えます。
C++でもう少し頑張ってみる
疑問の種を潰すために、もうちょっとC++で頑張ってみましょう。
ポインタを保持し、かつコピーが発生しないクラスで代用する
mutableなエイリアスが実質使えないようなソースにしてみましょう
例えば以下のようなクラスを使って
template<typename T>
struct wrap_ptr{
T * ptr;
wrap_ptr():ptr(nullptr){}
wrap_ptr(T * ptr) : ptr(ptr){}
~wrap_ptr(){delete ptr;} //1.デストラクタでポインタが破棄され(つまり同じポインタを指し合うことが出来ない)
wrap_ptr(const wrap_ptr &) = delete;//2.コピー禁止のクラス
wrap_ptr(wrap_ptr && ) = default;
};
こんな感じで検証を…
void compute(wrap_ptr<int> input,wrap_ptr<int> output);
int main(){
wrap_ptr<int> a(new int),b(new int);
std::cin >> (*a.ptr) >> (*b.ptr);
compute(std::move(a),std::move(b)); //同じポインタを指す可能性はない(有ったとしてもダブルdeleteの未定義マジック期待)
}
とその前に、なんかこんなクラス見たこと有りますね
そうだねunique_ptrだね。
void compute(std::unique_ptr<int> input,std::unique_ptr<int> output);
int main(){
auto a = std::make_unique<int>();
auto b = std::make_unique<int>();
std::cin >> (*a) >> (*b);
compute(std::move(a),std::move(b));
}
劣化unique_ptrなんて使ってもしょうがないので
こんな感じでビルドし検証
0000000000000ab0 <_Z7computeSt10unique_ptrIiSt14default_deleteIiEES2_>:
ab0: 48 8b 17 mov (%rdi),%rdx
ab3: 8b 02 mov (%rdx),%eax
ab5: 83 f8 0a cmp $0xa,%eax
ab8: 7e 0b jle ac5 <_Z7computeSt10unique_ptrIiSt14default_deleteIiEES2_+0x15>
aba: 48 8b 06 mov (%rsi),%rax
abd: c7 00 01 00 00 00 movl $0x1,(%rax)
ac3: 8b 02 mov (%rdx),%eax
ac5: 83 f8 05 cmp $0x5,%eax
ac8: 7e 05 jle acf <_Z7computeSt10unique_ptrIiSt14default_deleteIiEES2_+0x1f>
aca: 48 8b 06 mov (%rsi),%rax
acd: d1 20 shll (%rax)
acf: f3 c3 repz retq
ad1: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
ad8: 00 00 00
adb: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
…してみた物の上手く行きませんでした…
gccちゃん敗北…
リンク時最適化する
しかし、gccちゃんはこんな所でくじける玉ではないのです
超必殺魔法「Link Time Optimization(リンク時最適化)」をいじわるなソースコードにぶつけてやりましょう！
説明しよう！
Link Time Optimizationとはその名の通り、リンクのタイミングで最適化を実行する
gccちゃん秘蔵1の超必殺技なのである！
ソースコードは以下のようにし
void compute(const std::uint32_t & input,std::uint32_t & output);
int main(){
std::uint32_t a,b;
std::cin >> a >> b;
compute(a,b);
compute(a,a); //同じ可能性も有る！
std::printf("%d,%d\n",a,b); //最適化防止
}
オプションは「-O3 -flto」でビルドしてみます。
# inline化されcomputeが消滅したので、mainから該当する部分を抜き出し
843: 83 fa 0a cmp $0xa,%edx
846: 76 49 jbe 891 <main+0x91> #a <= 10ならjump
848: b9 02 00 00 00 mov $0x2,%ecx #bに2を代入
84d: c7 44 24 10 02 00 00 movl $0x2,0x10(%rsp)
854: 00
855: ba 01 00 00 00 mov $0x1,%edx #compute(a,a)の結果がa=1である事が分かりきってる為代入
85a: c7 44 24 14 01 00 00 movl $0x1,0x14(%rsp)
861: 00
862: 44 8b 44 24 0c mov 0xc(%rsp),%r8d
867: 48 8d 35 d6 01 00 00 lea 0x1d6(%rip),%rsi # a44 <_IO_stdin_used+0x4>
86e: bf 01 00 00 00 mov $0x1,%edi
873: 31 c0 xor %eax,%eax
875: e8 f6 fe ff ff callq 770 <__printf_chk@plt>
87a: 31 c0 xor %eax,%eax
87c: 48 8b 7c 24 18 mov 0x18(%rsp),%rdi
881: 64 48 33 3c 25 28 00 xor %fs:0x28,%rdi
888: 00 00
88a: 75 1c jne 8a8 <main+0xa8>
88c: 48 83 c4 28 add $0x28,%rsp
890: c3 retq
891: 83 fa 05 cmp $0x5,%edx
894: 8b 4c 24 10 mov 0x10(%rsp),%ecx
898: 76 c8 jbe 862 <main+0x62> #a <= 5なら何もせずjump
89a: 01 c9 add %ecx,%ecx #a > 5ならb *= 2
89c: 01 d2 add %edx,%edx #compute(a,a)の結果がa*=2である事が分かりきってる為代入
89e: 89 4c 24 10 mov %ecx,0x10(%rsp)
8a2: 89 54 24 14 mov %edx,0x14(%rsp)
8a6: eb ba jmp 862 <main+0x62>
最適化できてますね！
gccちゃん逆転勝利！ばんざーい！
おわりに
とまあ、やりようによってはC++もRustと同様の最適化が出来なくもないですが。
Rustのルールは最適化に優れているという話でした。
(rust側に謎のオーバーヘッドが有ったりもしますが…)
あくまで一部界面を削り取って解説しただけなので
Rust vs C++で悩んだときは、プロジェクト特性やレガシーソース流用度、言語選択による人的リソース計算等々
色々なことを考慮しながら選択いただければ幸いと思います
(そもそもそのプロジェクトに低レイヤー言語を使う意味は有るのか？などなどについても)
[補足]C言語の場合
「restrict」という便利なキーワードがあります
memcpyにくっついてたり、#ifdef __cplusplusでわざわざ切り替えるあのめんどい奴です
(コンパイラ拡張でC++にくっついてる場合もあります)
void compute(const uint32_t * restrict input,uint32_t * restrict output);
int main(){
uint32_t a,b,c;
int ret = scanf("%d %d",&a,&b);
compute(&a,&b);
//compute(&a,&a); //同じ物渡したら未定義(当然ながらrustのようにコンパイル時検出はしてくれない)
}
ポインタの参照先が被らない事を言語仕様で保証できるので、gccちゃん@がんばらないでも
普通に最適化されます
720: 8b 07 mov (%rdi),%eax
722: 83 f8 0a cmp $0xa,%eax
725: 77 09 ja 730 <compute+0x10>
727: 83 f8 05 cmp $0x5,%eax
72a: 77 0c ja 738 <compute+0x18>
72c: c3 retq
72d: 0f 1f 00 nopl (%rax)
730: b8 02 00 00 00 mov $0x2,%eax
735: 89 06 mov %eax,(%rsi)
737: c3 retq
738: 8b 06 mov (%rsi),%eax
73a: 01 c0 add %eax,%eax
73c: 89 06 mov %eax,(%rsi)
73e: eb f7 jmp 737 <compute+0x17>
C++全然わからないんですけど
契約プログラミングで[[expects:is_same_reference(obj1,obj2)]]とか書いて似たような事出来るようになったりするんですかね
そもそもそういう物なんですかね？
環境
- CPU:core i7-6850k
- OS:ubuntu18.04
- Rustc:1.41.0
- Cargo:1.41.0
- GCC:10.0.1.20200416
clangとmsvcは調べなかったので
誰か調べて記事書いてくれるとうれしーなー
おまけ
javascriptで産目奈良部作りました。
外部ライブラリレスの超純粋古典実装です。
https://kizul1254.github.io/marubatu/main.html
申し訳程度にモンテカルロもどきAI用意しました。
皆もjavascriptやろうな。
調査方法/内容などについての指摘、誤り、マサカリ、憂さ晴らしなど有りましたらコメントもらえると嬉しいです。
-
※clangもmsvcもrustcも使えます(cargo build --release のデフォルトはlto=falseです。rustは超必殺技レスでいじわるソースコードを倒してます) ↩