除算の最適化については除数が定数でないまたは2の乗数でないときは逆数に変換しての除算が有効というのは書いたと思いますが、
それ以外、つまり定数かつ2の乗数であるときについての話です。最適化の話ですので可読性は横に置いておきます。
今やっている作業ではサウンドのサンプリングビット数の変換作業(32bit,24bit整数=>16bit整数)で出てきました。
今の条件で被除数が「符号なし整数」なら何も考えることなくビットシフトにすればいいですね。
問題は「符号あり整数」、つまり負数が相手になる場合です。
ビットシフトを算術シフトとして扱うとしても、算術シフトと除算命令とでは負数の丸めに違いあり、
div(-7,4) = -1
sar(-7,2) = -2
となります。これは算術シフトは負方向丸め(=(除算により余りが出るとき、余りを正にするように演算する。上記の例では-7 / 4 = -2 … 1とする。こうすると商は負方向に向かう)=)に対して除算命令では零方向丸め(=(除算により余りが出るとき、余りを負にするように演算する。上記の例では-7 / 4 = -1 … -3とする。こうすると商は零方向に向かう)=)だからです。
ということで、これを補正する必要があり、負数に対しては(除数-1)を被除数にあらかじめ足してから算術シフトをすることでこの問題を解決でき、
sar(-7 + (4 – 1),2) = -1
とすることで除算を使わないで処理を行うことができます。
ここで問題です。以下の関数のうち「コンパイラに最適化を行わせた時」もっとも高速なのはどれでしょうか？
int f1(int n) { return n / 65536; }
int f2(int n) { return (n >= 0 ? n : n + 0xffff) >> 16; }
int f3(int n) { return (n + (n >= 0 ? 0 : 0xffff)) >> 16; }
皆さんも試してみるといいと思います。私がVisualStudio2005で試した結果、このような結果になりました。
f1のアセンブラ命令
cdq and edx, 65535 ; 0000ffffH add eax, edx sar eax, 16 ; 00000010H ret 0f2のアセンブラ命令
test eax, eax jge SHORT $LN4@f2 add eax, 65535 ; 0000ffffH $LN4@f2: sar eax, 16 ; 00000010H ret 0f3のアセンブラ命令
xor ecx, ecx test eax, eax setge cl sub ecx, 1 and ecx, 65535 ; 0000ffffH add ecx, eax sar ecx, 16 ; 00000010H mov eax, ecx ret 0
ちょっと難しいですね。
速度が速いほうを小さい方とするならf1 < f3であるのは間違いないと思います。
問題はf1とf2ですが、分岐命令のペナルティがある場合を考えるとf1 < f2となることが多いと思います。
つまり、「コンパイラに最適化を行わせた時」の2の乗数での除算は普通に直値を書いて除算を行わせた方が早い訳ですね。
一応私の参考にしている本にも同じようなことが書いてありますが、この結果を見て納得しました。
私としては直値を書いておくと除算が行われているようで遅いのでは？と思ってしまうので、コメントで何とか納得しようと思いました。
似たようなことから、ビット数=>バイト数変換時にもビットシフトで書くよりも除算式で書いた方が最適化時に効率よく最適化してくれる、という結論も得られました。
ちなみに、「2の乗数ではない定数の除算」の場合もそのまま書いた方が早いです。無理に逆数乗算を使わなくてもいいです。
コンパイラに最適化を任せればだいたいの場合は逆数の乗算を使ったコードに書き換えてくれます。(乗算にかかる時間＜除算にかかる時間のため)
一定水準以上であればコンパイラの最適化は十分に有効である、ということですね・・・。
非定数(変数を使う)除算であればその変数を何回も使う、もしくは範囲が限られる(レイヤー合成などの)場合は逆数乗算が早く、回数が少ないときは素直に除算に任せるのが簡単で早いです。