[Programming] 私の peephole 最適化

私は以前、vsOthaというオセロプログラムをかなりがしがしと最適化したことがあります。
その時の記憶が、某氏のプログラムを高速化すべくいじってる時によみがえってきたので記しておきます。

注意: 「主観に基づく記事」 ここに書かれていることは、「私ならこうする」であり、「あなたもこうすると速くなるよ」というものでは決してありません。中には速くなる根拠を具体的に示せないもの、私の思い込み、コンパイラがやってくれるものもあります。施す最適化も好みの問題もあります。また、このリストは網羅的であることを目指してはいません。また、非常に泥くさいです。

注意: 「変態向け」 ここで書かれているうちのいくつかは、最適化最終段階で、しかもプログラムの読みやすさを犠牲にし、大量の時間資源を投入して極限まで最適化する場合に使ったものです。百の下手な鉄砲を撃つ状況でした。遅くなる場合もあったので、1箇所改変→時間測定→悪化したら戻す、というサイクルでした。

注意: 「peephole中毒注意」 当たり前の話ですが、peephole最適化のみにこだわるのは微妙です。この文書はpeephole最適化に関する事項だけを抜き出したものです。
一般的には: コード全体を考えましょう。そもそもアルゴリズムが悪くはありませんか? アルゴリズムの改善の方が劇的に利いたりします。大域的な最適化、データ構造の全体的な再編は? 等。あと、もともと実行時間の短い部分を最適化しても無意味であることを意識しましょう。

補足: 「根拠に乏しい項目の意義」たぶん速くならない、私の思い込み系の項目もあります。そういう項目は、(私に)考えられる可能性を全てつぶしていく、という意味でやります/やりました。思いつくけどぶっちゃけ利くか分からない/たぶん利かない、というのも全てつぶして、その上でどこが速くなるかを考えることで、思考のノイズを軽減します。速くなるかもしれないけどたぶん違うよなぁ、と50回思うよりは1回さくっと書き換えて駄目確定させる方が速いということです。

一般

• ソースを読みながら、どのような機械語に落ちるか、実行時に何がCPUの中で起こるかを考えます。
• やることを全てマージして最適化すると良いこともあります。
• コードの各部分で必ず成立する条件(ここの変数は必ず1である、この関数のこの引数は0〜63である、など)を利用すると、その条件下に特化した最適化が利くことがあります。
  • 大抵は××が成立して最適化できる、なら、if(××){最適化ver;}else{普通ver;}にすることができます。

メモリ系(一般)

メモリの確保、コピーや初期化を特に意識します。
無駄な確保→解放の繰り返し、無駄なコピーや複数回の初期化は削れる無駄な処理の代表例。
最適化していくと、ボトルネックはメモリコピーです、ということはありがちでした。

• コンストラクタ、代入演算子, 暗黙の初期化などを意識します。
• 何バイトのメモリ領域をコピーするかを意識します。
• コンストラクタ等をループの外側、あるいはifの内側に移動します。
• 不要なメモリ/オブジェクトは確保しない。削除可能なオブジェクトを洗いなおす。
  • 中間バッファ等を削除する。vector<int> s; for(i){ if( fuga(i) ){ s.push_back(f(i)); } } foreach(j<s.size()) { hoge(s[j]); } は for(i){ if( fuga(i) ){ hoge(f(i)); } }にしてsを消す。

メモリ系(キャッシュ)

甘く見るとひどい目にあいます。

• working setはキャッシュに収まるか考える。
• キャッシュにヒットするようなアクセスパターンであるか考える。

分岐関係

分岐を少なくします。
分岐のコストは、分岐予測があるとはいえ大きい。

• && 演算子等も分岐のようなものなので排除します
  • (i == 0) && (j == 0) は (i|j) == 0 にできる、とか。
• if(case1){ ... } else if(case2){ ... } else ... のような場合(各caseはdisjoint)、成立する可能性の高いcaseから順に並べます
  • case1 || case2 || case3 || ... でも同様(但し各caseの計算量も考慮する、各caseはdisjointでなくてもよい)
  • 分岐の動的実行数は減るはず
  • 実はかなり利く場合もあった(全体10%減とか)
• ノーコストで可能ならgotoをbreak等に書き換えます
  • コンパイラの最適化が利く気がする。たぶん気がするだけ。
• 番兵を置くと、領域内か否かを調べるif文を省けます

ループ関係

• マージ(fusion)できるループはマージします
• 繰り返し回数が既知の小さい定数の場合unrollします
  • 特に、int dx\[\]={0,1,0,-1}, dy[]={1,0,-1,0}; for(int d=0;d<4;d++){ ... dx[d],dy[d] ... } みたいな場合だと、dx,dyも削れて定数伝播も利いて有効。
• 可能ならループ順を逆にして for(int i=0;i<n;i++) を for(int i=n-1;i>=0;--i) にします
  • 変数との比較より0比較の方が速いかも
• それ以上繰り返しても無駄と分かった時点でbreakします

関数関係

関数呼び出しにはオーバーヘッドがかかります。
また、関数をまたがった最適化が利かない場合もあります。

• int f(int i,...) を、iの範囲が限定(例:0〜63)されている場合、int f0(...) から int f63(...) を全部別関数で用意する(fnは、i==nの時用の関数)ことが有効なことがあります。
  • iを定数にすると定数伝播がものすごい勢いで利く場合に有利。オセロの石を返す関数(iは石を置く場所)の場合、iが定数だと配列アクセス位置やループ回数等が全て定数に置換されるのでかなり利いた。
• 小さい関数が多いと最適化が面倒になるのでインライン化することもあります

その他(宗教系多し)

• x++ を ++x にします
  • intとかならコンパイラが最適化してくれるだろうが、xがiteratorの場合とかは有効かもしれない
• 掛け算を排除します
• 割り算を排除します
• count()とかsize()とかも排除します
• setやmapも消したくなります
• 配列アクセスは可能なら一時変数にバインドしてアクセスします
• 構造体をばらしたくなります
• 要素数が少ない(4以下など)vector/set/map/sort等は自分で書き換えたりします
  • オーダーが大きくても定数の小さい挿入ソートなどにすると速くなることも