c++コンパイラの頭の良さの比較
はじめに
windows10は、bash on ubuntu on windows なるものが登場し簡単にgccが導入できます。
visual studio で使用しているマイクロソフトのコンパイラ(以下vc++と呼称)とどちらが高速なコードを生成できるのか調べてみたくなりました。
簡単なコードを比較し、どちらが高速か比較してみましょう
計算させるもの
次のような計算をさせたいと思います。（大体一秒程度で終わるように調整しました）
auto start = chrono::system_clock::now(); /*unsigned */long long x=0; for(/*unsigned */long long i=0;i< 1+(1ll<<28);i++){ x+=i; x%=13; } auto end = chrono::system_clock::now(); cout<<x<<endl;
| コンパイラ | かかった時間(10回平均)(signed) | かかった時間(10回平均)(unsigned) |
|---|---|---|
| g++ on bash | 914 ms | 811 ms |
| vc++ | 1089 ms | 896 ms |
符号付きの場合2割近く符号なしの場合一割ほどvc++が遅いです。また、符号なしの場合が符号付きの場合に比べて早くなっています。なぜこのような差が生まれたのかアセンブリを出力させて調べてみます。
vc++とg++の違い
g++では -S オプションで、vc++では /FA オプションでアセンブリを出力させることができます。
アセンブリにはAT&T構文とintel構文があるようですが、個人的にはintel構文の方が読みやすいです。g++では-masm=intelでintel構文のアセンブリを出力させることができます。
上記の計算部分に対応しているところだけを抜き出します。
vc++(unsigned)のアセンブリ
ループの内部のアセンブリを抜き出すと以下のようになります（レジスタを0に初期化したりしているところは省略）
mov r8, 5675921253449092805 ; 謎の数字 $LL64@main: ; Line 11 add rsi, rcx ; rcxはiに対応 rsiはxに対応 この行は x+=i ; Line 12 mov rax, r8 ; r8に入っている謎の数字をraxに格納 mul rsi ; mulはraxとの積を上位64bitをrdx、下位64bitをraxに格納 inc rcx ; iをインクリメント shr rdx, 2 ; 上位64bitを右に2ビットシフトし、掛け算の結果の上位66bitを求める imul rax, rdx, 13 ; 掛け算の結果の上位66bitを13倍 sub rsi, rax ; xから上で計算した数字を引いている cmp rcx, 268435457 ; for文の条件文 jb SHORT $LL64@main
謎の数字 5675921253449092805があります。これは何なのでしょうか。
以下のような関係式が成り立ちます
つまり
2のべき乗での割り算はビットシフトで行うことが出来るため、時間のかかるdiv命令を使わなくて済むという高速化です。
上のアセンブリは以上のテクニックを生かして13で割った商を高速に求め、
その商を13倍して元の数から引くという方法であまりを計算していることがわかります。
頭いい…
g++(unsigned)のアセンブリ
ではそのvc++のコードより一割早いg++の生成したコードは何が違うのでしょうか
movabs rdi, 5675921253449092805 ; 同じ .L2: lea rsi, [r12+rcx] ; r12+rcxをrsiに格納 x+=i add rcx, 1 ;インクリメント mov rax, rsi ; xをraxに移して mul rdi ; 謎の数をかける shr rdx, 2 ; 上位66bitをとる lea rax, [rdx+rdx*2] ; raxにrdxの3倍を格納 lea rax, [rdx+rax*4] ; raxにrdx+rax*4を格納 つまり13倍している sub rsi, rax ; xから商の13倍を引いて cmp rcx, 268435457 ; 1+(1<<28)と比較する mov r12, rsi jne .L2
13倍するコードを素直にmul命令を使わずlea命令に置き換えています。
lea命令はもともとアドレス計算用の命令ですが、算術演算にも使用でき、
フラグを立てず、使用する演算ユニットが違うため、*1もろもろ良いみたいです。
1，2，4倍にしかできないため
といううまい変形をすることでlea命令で計算できるようにしています。
めっちゃ頭いい…
なおjumpする命令が違ったりしますが、それはcmp命令が建てたフラグのうちどれを使っているかが違うだけです。
結論
どちらも頭が良いが、gccの方が頭がいい
unsignedとsignedの違い
なぜ符号付きにすると大幅に遅くなってしまうのでしょうか。
符号付き整数を表現するために2の補数表現を用いているということ、ビットシフトには論理シフトと算術シフトがあることを思い出します。
vc++の出力アセンブリ
mov r8, -5675921253449092805 $LL64@main: ; Line 11 add rsi, rcx ; Line 12 mov rax, r8 imul rsi inc rcx sar rdx, 2 mov rax, rdx ;rdxをrdaにコピー shr rax, 63 ;63ビットシフトするという謎の処理が挟み込まれている add rdx, rax ;63ずらしたものを足している imul rax, rdx, 13 add rsi, rax cmp rcx, 268435457 jl SHORT $LL64@main
63右に論理シフトすると、もともとの数の最上位のビットが1つまり負であれば1、正であれば0です。
商が負であるときに1足すという処理をしています。
g++の出力したアセンブリ
movabs rdi, 5675921253449092805 .L2: lea rsi, [r12+rcx] add rcx, 1 mov rax, rsi imul rdi mov rax, rsi sar rax, 63 ;同じく63右にビットシフトしている sar rdx, 2 sub rdx, rax lea rax, [rdx+rdx*2] lea rax, [rdx+rax*4] sub rsi, rax cmp rcx, 268435457 mov r12, rsi jne .L2
sarは算術シフトです。(shift arithmetic right)最上位ビットが1のとき、63ビットシフトすると全部1のビットが立った数字になり、2の補数表現では-1です。
つまり割られる数xが負ならば-1を引くという処理です
これらの計算はc++の余りの計算の仕様が数学的に不自然なため生じた処理です。c++で商が負のときは0に近い方に切り捨て、余りは負になると定められています（c++03までは処理系依存でした）これは余りが正になったり負になったりして不自然です。
割り算を掛け算に変更するテクニックを用いると、商が負のときも数学的に自然な商を超えない最大の整数が求まり、c++の求める答えと1ずれます。
そこのずれを修正するために無駄な計算をしているようです。
結論
人間の定めた仕様は頭悪い
Appendix
コード全文
#include<iostream> #include<chrono> using namespace std; int main(){ auto start = chrono::system_clock::now(); long long x=0; for(long long i=0;i<1 + (1ll<<28);i++){ x+=i; x%=13; } auto end = chrono::system_clock::now(); cout<<x+2<<endl; auto diff = end - start; std::cout << "elapsed time = " <<chrono::duration_cast<std::chrono::milliseconds>(diff).count() << " msec." << endl; return 0; }
