Cozy Ozy このページをアンテナに追加 RSSフィード

2007-11-09 どんな最適化やねん(1)

[][]どんな最適化やねん(1) どんな最適化やねん(1)を含むブックマーク

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はAMDSempron(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
オプションabs2abs1
/Od107.8s206.1s
/O2 47.8s 47.8s
VC++6.0(Release)
オプションabs2abs1
/O2107.9s205.3s
cygwin gcc 3.4.4
オプションabs2abs1
-O0111.8s111.4s
-O2 50.3s 50.3s
mingw gcc 3.4.2
オプションabs2abs1
-O0112.1s226.7s
-O2 50.5s 50.5s

cygwin gcc 3.4.4の場合だけ,最適化無しなのにabs2とabs1が同じ速度(;´д`)

どうやら混乱はコイツのせいみたいです.しかしなんで同じなのかがワカラン…

m.ukaim.ukai 2007/11/09 23:35 手元のgcc(3.4.6と4.1.1)でやったら、-O2 (-Oでも) は abs1もabs2も同じコード(abs2相当の内容)を吐きましたから同じ速度なのは当然という。
このケースでのVC++の最適化がアレということではないかと。

m.ukaim.ukai 2007/11/09 23:57 手元の Pentium4 で gcc -O0 は abs2 のほうが速いという当たり前の結果でした。
abs1 のほうが速くなるのはちょっと理由が思いつかないですね。

OzyOzy 2007/11/10 13:34 自宅のPentium4で最適化なしの実行速度を調べたら,mingw gcc 3.4.2ではabs1よりabs2が2倍速いという期待通りの結果になったのですが,cygwin gcc 3.4.4だと同じ速さなのです…-Sオプションでアセンブリコードを見ると明らかにabs2の方が速いはずなのですが(´ω`)
gccがおかしいんやろか…

herumiherumi 2007/11/10 15:01 VCもgccも10年近く前からANSIのabs()を使うとabs2()相当の最適化をします.その場合は(ごくわずかですが)VCの方がよいコードを生成します.
一般の条件分岐絡みの最適化に関してはgccがVCよりよいことは多いですね.

OzyOzy 2007/11/10 16:32 なるほどー.abs1とabs2を最適化したコードでも(同じはずなのに)差が出たという話を聞いちゃったりしたもんで,ちょっと気になっていろいろと調べているところであります.Core2はもしかしたらとてつもない分岐予測をしているのかも!という淡い期待を込めて…

トラックバック - http://d.hatena.ne.jp/Ozy/20071109/p1