【プログラム高速化】整数演算による浮動小数点演算の近似

　こんにちは。ディマージシェアの技術担当です。以前の記事で計算量削減によるプログラムの高速化を紹介しました。今回は使用する演算命令を変えることで更に高速化してみます。

整数演算による浮動小数点演算の近似

　計算結果の小数部分を切り捨ててよい計算は、浮動小数点の計算の代わりに、整数の掛け算にしても結果が概ね一致します。

       c = cos(t);
       s = sin(t);
       for (i = 0; i < dot_ct; i++) {
           int32_t y = s * (dots[i].x - ox) + c * (dots[i].y - oy) + ooy;
           horizontal_sum[x][y] += 1;
       }

この部分を、

       c = cos(t);
       s = sin(t);
       int32_t cc = c * 65536;
       int32_t ss = s * 65536;
       for (i = 0; i < dot_ct; i++) {
           int32_t y = ((ss * (dots[i].x - ox)) >> 16) + ((cc * (dots[i].y - oy)) >> 16) + ooy;
           horizontal_sum[x][y] += 1;
       }

と書き換えることで、浮動小数点数の掛け算を整数同士の掛け算に書き換えることができます。このソースでパフォーマンスを確認してみます。

ベンチマーク

浮動小数点の掛け算の場合

time = 1.701961 sec

整数演算に書き換えた場合

time = 0.864623 sec

使う演算命令を浮動小数点演算から整数演算に書き換えたことにより、2.0倍のパフォーマンス向上が実現できました。初版のプログラムが375秒もの実行時間だったことを考えるとかなりの改善です。

まとめ

　普段のプログラミングではほとんど意識しない命令レベルのパフォーマンス差ですが、
・アルゴリズム最適化
・メモリアクセス最適化
あたりの性能向上手段を試した後だと目に見えるパフォーマンス差として現れます。ここから更に、インラインアセンブラやSIMD化など、より高度な細工をすることで更にパフォーマンスを改善することができます。

　愚直に実装すると絶望的なパフォーマンスになるプログラムでも、ちょっとした工夫や制約を加えることで劇的にパフォーマンスを改善できることは珍しくありません。また、採りうる工夫も多岐に渡ります。試してみましょう。