トップ «前の日記(2007-09-22) 最新 次の日記(2007-10-01)» 編集

U-memo

2006|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|08|
2009|08|10|
2010|02|03|
2011|11|12|
2012|04|
2016|02|
All= / Today= / Yesterday=

2007-09-26

_ [雑記] アルゴリズム以外の最適化

ループの内側が最もたくさん実行されるからそこを最適化するのは一般常識だと思っていましたが、違ったのでしょうか。

結果的にそうなるのは多いでしょうが、いまどきは 「まずプロファイラかけろよ」という話のような気がします。

(突っ込まれたようなので補足 9/27) Intel VTune(tm) はふつーに知ってますが使ったことはありません。文脈からは VTune 使うのが一般常識ではなく「ループの内側最適化万歳」:というように読めました。

その最内ループが本当に実行時間にクリティカルならば、 そこを最適化すればよいけど、 見当外れの場合もあるわけです。

コードの20%の部分が80%の実行時間を担当する

これは今でもよほど考えて作らないこうなるわけですが、 「最もたくさん実行される」「もっとも時間食っている」 のがどこなのか、想定している場所で本当に正しいのかどうか 確認するのが最初、ですね。 どーでもいいと思っていたところで時間を食っていることもままあるわけで。

あー、あと、 最内ループは unrolling せよ、とかいう人はいるかもしれない (これは必ずしも正しくはないけれど)。したがって、

 1.  分岐の数を減らせ
 2. ループを短くしろ

短いループは展開したほうがいい、が追加されたりする。

-O5 したら unrolling するだろうからある意味「-O5 せよ」は 正しいかもしれない。

「ループを短くする」ことそのものが本質ではなくって、 (動的)実行命令数を減らすのに直球ど真ん中だという話なんだから。

#命令数が多少減ったって実行時間が減るとは限らないから過激な一般化は難しいけれど。

r=0;
for(i=1;i<n;i++)r+=i;
r=(n+1)*n/2;

しかしこれは最適化の罠でもある。nが1の場合、計算量は乗除算が入っているからどっちが速いかはわからない。

後者は整数の掛け算は 5clock 程度、/2 はシフトだから 1clock、足し算とあわせても 10clock でお釣りがくる。

前者は、初期化で1clock(rとiは独立変数なので並列実行可能)、 1 を足すのに 1clock、i<n の条件判定が謎(っていうかバグってませんか)だけど、 (i<=n だとして) n = 1 で常に呼ばれたとしても、この条件判定は true, false 交互に変わるわけです。 最近のプロセッサは規則性があれば当ててくれますから予測100%正解とかして 1clock 実行になって高速ですが(!)、 教科書的な 2bit predict なら 1/2 の確率で分岐予測が外れるので、 パイプラインフラッシュのペナルティをくらって(10clockとか)、 後者よりも遅くなるとかいう罠。

中途半端な知識はむしろ足を引っ張るとかいう。

  • できるだけキャッシュに乗るように、データの局所性を意識
  • 分岐予測ミスができるだけおきないように

そんなもん?あれ、命令セット関係ないな。いや他にもあるはず。

マイクロアーキテクチャの領域ですね。

あとまぁ、Pentium 4 の分岐予測ミスのペナルティがでかすぎ。ランダムなデータと逆順に整列されたデータに対して bubble sort をすると逆順にソートされたデータのほうが倍以上速いとか、なんだそれ。

条件 move のほうが高速だろうなぁ、これは。 おお、これはマシン語の領域かも。(μarchの領域でもあるけれど)