RustがC++より最適化しやすい理由 〜Aliasingルール〜

※2020/4/27 Rustのビルド結果説明に一部誤りが有りましたので修正しました。

# はじめに
産目奈良部というゲームがあります。
神ゲーです。

![samoku.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/277386/4849886f-a670-96c3-efa7-7bb949979141.png)

ググった瞬間出てくるので、皆さんやってください。

# 概要
↓詳しいことはrustドキュメントが解説してくれています↓
[Rustドキュメント(Aliasing)](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=2ahUKEwjBv-rTsf_oAhWb7WEKHSSOAEoQFjAAegQIARAB&url=https%3A%2F%2Fdoc.rust-lang.org%2Fnomicon%2Faliasing.html&usg=AOvVaw3_3EVPPEgRJM9SrHji6yyD)

例に出ているのは以下のようなコードですね。

```rust
fn compute(input: &u32, output: &mut u32) {
    if *input > 10 {
        *output = 1;
    }
    if *input > 5 {
        *output *= 2;
    }
}
```

rustなら以下のように最適化出来ますよと

```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の呼び出しを別ファイルで適当に書いて

```rust
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
```

…何故だか以下のような最適化結果になってしまっていますが…

```rust
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関数呼び出しを例に上げると

```rust
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な参照+αが許されている場合、以下のソースはどうなるでしょうか？

```rust
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++で上記のソースを書いた場合以下のようになりますが

```cpp
void compute(const std::uint32_t & input,std::uint32_t & output) {
    if(input > 10){
        output = 1;
    }
    if(input > 5){
        output *= 2;
    }
}
```

C++ではlvalue referenceの数に制約がありません。

```cpp
int main(){
    std::uint32_t a,b;
    std::cin >> a >> b;
    compute(a,b);
    compute(a,a);   //同じ可能性も有る！
}
```

試しにgcc -O3でビルドすると

```asm
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なエイリアスが実質使えないようなソースにしてみましょう
例えば以下のようなクラスを使って

```cpp
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;
};
```

こんな感じで検証を…

```cpp
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だね。

```cpp
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なんて使ってもしょうがないので
こんな感じでビルドし検証

```asm
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]の超必殺技なのである！

ソースコードは以下のようにし

```cpp
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++にくっついてる場合もあります)

```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やろうな。


調査方法/内容などについての指摘、誤り、マサカリ、憂さ晴らしなど有りましたらコメントもらえると嬉しいです。

[^1]: ※clangもmsvcもrustcも使えます(cargo build --release のデフォルトはlto=falseです。rustは超必殺技レスでいじわるソースコードを倒してます)