tomabouの日記

Haskellなどで勉強したことなどを書いていきます

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=intelintel構文のアセンブリを出力させることができます。
上記の計算部分に対応しているところだけを抜き出します。

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があります。これは何なのでしょうか。
以下のような関係式が成り立ちます
5675921253449092805 * 13 = 2^{66} + 1
つまり
\displaystyle \frac{5675921253449092805}{2^{66}}  \approx \frac{1}{13}
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倍にしかできないため
13 = 1+ 4*(1+2*1)
といううまい変形をすることで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

環境
CPU core i7-4510U
memory 8GB
OS windows 10
コード全文
#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;
}