Cにおける加算と除算のコストの比較

C++

後輩とCの加算・除算のコスト差について意見が食い違ったので, 実際にプログラムを書いて比較してみた.
マシンスペックはIntel® Core™2 Duo CPU T9300 @ 2.50GHz × 2 Ubuntu11.10 64bit. コンパイラはgccバージョン4.6.1, またコンパイルオプションは常に-O0をつけている.

比較開始

次のようなソースコードを用いて, 加算と除算のコスト比較を行なった. 

#define OP /

int main(){
  int a=1,b=1;
  const long n = 50000000l;
  int c = 0;
  
  for(long i = 0;i < n;i++){
    c = a OP b;
    c = a OP b;
    中略
    c = a OP b;
    c = a OP b;
    c = a OP b;
  }
}

先頭のdefineを書き換えることで加算と除算を切り替えている. なお, わざわざcに代入しているのは-O0環境下でも, 代入先が無いと演算命令は省略されてしまうため(アセンブラで確認). 同じ命令を連打してるのは, ループの全体に対するコスト比を下げるためである.

この比較結果は, 加算1.4秒, 除算2.3秒となり, 倍も差が無いねという話になった. 以下は色々副産物としてわかったこと.

その他の実験

c = a OP b

とここまではしてきたが, 代わりに

a = a OP b

と変更してみた, すると加算2.7秒, 除算9.1秒となり先ほどよりも大きな差が生じた.
この差を考えるために"c = a OP b"に相当するアセンブラを見てみる.
加算

movl -8(%rbp), %eax
addl %eax, -12(%rbp)

除算

movl -12(%rbp), %eax
movl %eax, %edx
sarl $31, %edx
idivl -8(%rbp)
movl %eax, -12(%rbp)

正直, アセンブラのことはよく分からないので間違ってたらごめんなさい. -12(%rbp), -8(%rbp)はそれぞれスタックに積まれた変数a, bを意味している. sarlは算術右シフト, idivlは%edxを上位32bit, %eaxを下位32bitとみなし, その64bitの数を引数で割る命令で, 結果は商が%eax, 余りが%edxに格納される. 参考文献

では, このアセンブラをもとに代入先の変更によって差が大きくなった理由を考えよう.
真っ先に目につくのは, 加算の場合にmovl命令が除算よりも少ないことである. これはaddl命令の結果が第２引数に代入されるので, 別途movlを発行する必要が無いためだ. 一方, 除算の場合は左辺の変数が右辺に含まれていようがいまいがmovl命令が必要なため差が広がったものと思われる.

もう一つ推測としてあるのは, a = a + bといった処理を連続して行う場合, 2回目のa = a + bは前回のa+bの結果がストアされるまで行えない. これが除算が大幅に遅くなった原因の一つとして考えられる. 加算の場合はなんで大して遅くならないかよくわからない.

-O0における参照のオーバーヘッド

参照を使う場合

int& c = a;

for(long i = 0;i < n;i++){
c = a OP b;
省略
c = a OP b;
}

参照を使わない場合

int a=1,b=1;

for(long i = 0;i < n;i++){
a = a OP b;
省略
a = a OP b;
}

参照を使う場合は3.1秒, 使わない場合は2.7秒とわずかながら差が出ている. これはアセンブラで確認してみると, 加算１回につき

movl -8(%rbp), %eax
movl %eax, %edx
addl -4(%rbp), %edx
movq -16(%rbp), %rax
movl %edx, (%rax)

という命令が発行されている. これは恐らく-16(%rbp)にあるaのアドレスを毎回%raxに代入し, そのうえでそのアドレスが示す先に, 演算結果の%edxを代入している. これがいくらかのオーバーヘッドを産んでいるのだろう.

まとめ

今回は-O0という非現実的な設定でコンパイルしているため, 実践的な状況下において以上の知識が使えるかは疑わしい(特に参照). ただ, この実験より除算は加算の数十倍のコストということは無さそうだと考えている.