2007-11-09

32ビット整数の絶対値を返すabs関数は，条件分岐を使って

int abs1(int x)
{
  if(0<x)return x;
  else return -x;
}

と書くより

int abs2(int x)
{
  int y = x>>31;
  return (x^y)-y;
}

とした方が格段に速い！とコルンさん(id:colun)から聞いたとき，正直私は「そんな速いんカナー」と思ってしまったわけですが，VC++の最適化を用いてランダム(正負がちゃんと混じっている)な値を上記の関数に渡してやると，確かに後者の方が結構(2倍弱)速いのです．ActionScriptで，もの凄く速くなるという記事(http://actionscript.g.hatena.ne.jp/ConquestArrow/20070621/1182359767)もありますし，試しにC#で実験してみたところ4倍くらい速くなりましたので，これは重要なてくにーくなわけです．これは紛れも無い事実なのですが，Cでショートコーディングばっかりやってた私にとってはどうも腑に落ちない．

で，納得いくまで調べたいと思ったのですが，なんかどんどんわからなくなってきました．何がわからんのかというと，私が愛用しているマシンのCPUはAMDのSempron(3000+)で，Intelのプロセッサでないからなのだろうけど，VC++(Express2005)よりもGCC(cygwin gcc 3.4.4)でコンパイルした方が数段速いわけです．しかもGCCの場合は-O2で最適化した場合，abs1とabs2にほとんど差がでなくて，-O0つまり最適化なしだとabs1の方が明らかに速いわけです．

もっと言えば，テスト用のデータを生成するためのrand()関数を-O2と-O0とで試したら，-O0の方が明らかに速いのですよ．何ですかそれはと．

VC++のIntelガチガチ最適化もどんなシュゴー(゜□゜)な技術で行われているのかワカランし，GCCの最適化もよーワカランし，わからんことだらけですよ!っちゅうか，GCCは4.xで実験しないとイケナイのではないかという気もしてきたし．うきーーー(｀ω´)

…とりあえず，もうちょっと調べてみます．

追記:
とりあえず，自宅にあったPentium4(2.8GHz)のマシンで調べてみました．10^7個の乱数を予め配列に格納しておき，abs関数の呼び出しにかかる時間をclock()関数で取得しました．誤差が結構あるような気がするので，これを1000回繰り返した場合の時間にしています．

VC++2005 Express
オプション	abs2	abs1
/Od	107.8s	206.1s
/O2	47.8s	47.8s

VC++6.0(Release)
オプション	abs2	abs1
/O2	107.9s	205.3s

cygwin gcc 3.4.4
オプション	abs2	abs1
-O0	111.8s	111.4s
-O2	50.3s	50.3s

mingw gcc 3.4.2
オプション	abs2	abs1
-O0	112.1s	226.7s
-O2	50.5s	50.5s

cygwin gcc 3.4.4の場合だけ，最適化無しなのにabs2とabs1が同じ速度(;´д｀)
どうやら混乱はコイツのせいみたいです．しかしなんで同じなのかがワカラン…

カメヲラボ

主にプログラミングとお勉強全般について書いてます

どんな最適化やねん(1)