mattak's blog

人生を1ミリ進める

GeoHexの最適化

GeoHex v0.0.1をリリースした. ただロジック的にはgeohex4jのコピーに過ぎず、いくつかパフォーマンスチューニングの必要性があると思ってた。 その最適化した時のメモ。

計測

まずは各関数の実行時間を正確に計測する。 実行時間を計測するためのクラスを作成した。

gist.github.com

計測結果

10回ほど計測して平均値をとった。

function original (ms) optimized (ms) shrink time percentage (%)
AdjustXY 1.184e-05 1.1345454545454545e-05 95%
GetXYByLocation 0.0001939 0.0001600909090909091 82.5%
GetZoneByCode 0.008047 0.005785454545454546 71.9 %
GetZoneByLocation 1.872 0.0033481818181818183 0.18%
GetZoneByXY 0.003157 0.0028772727272727274 91.1%
Pow3 3.8473684210526316e-06 4.564593301435407e-06 118%
Math.Pow3 3.6705263157894735e-05 3.489952153110048e-05 95.1%
GetHexCoords 0.0006748 0.00052 77.1%
GetHexSize 9.73e-06 4.9e-06 50.4%

比較のために同じ計算値のMath.Pow3を表示している. 絶対時間が小さく、相対値が10%以内のものは誤差と考えてもよさそうだ。

3の累乗を計算する Pow3,Math.Pow3。AdjustXYなどがそれに該当する。

やったこと

全体のコミット差分はこちら

1. Debug.AssertをException throwに変更

一番効果があったのはこれだった。

Debug.Assert => throw ArgumentExpcetionに変更することでGetZoneByLocationが500倍近く高速化した。 一つDebug.Assertするだけで0.5msほどくってのがまるまるなくなった感じだ。

なぜこんなに重いのかが疑問だったが、とにかくこれが一番効果があった。

2. 計算式の削減

数値計算の基本で演算回数を減らすと高速化するので、式を変形してできるだけ演算回数を減らした。

3. 決まった数の定数化

GeoHexのレベルは予め範囲が決まっておりそのlevel値をもとに3の累乗を計算するので、これを事前計算して配列に突っ込んでおいた。

Math.Powをつかわず計算済みの値をつかうことでかなり高速になる。 GetHexSizeはこれにより2倍程度高速になった。 ただし配列へのアクセスが演算速度を下回っている場合に限るので、環境によっては対して変わらないかもしれない。

4. 割り算の削除

数値計算でもっとも重いのは割り算であるので、これを掛け算になおすように調整した。

5. Math.Floor Math.Ceilingの展開

正の整数であることがわかっているにもかかわらず、Math.Floorをしてしまっていたので普通にキャスト。 また正の整数をMath.Ceilingするさいに、shift演算と加算とAND演算に展開することで高速にした。

Performanceをとってみてもこれは確実に高速化に寄与していた。

6. 比較演算の&&の順序を交換

AND条件で左辺と右辺を交換しても意味的な変化がないものは、はじめの条件が高速なように変換した。 数値の場合、一致比較より順序比較のほうが一般的には高速なはずなのでこれに直す。

7. ループ内変数の外出し

正直あまり効果は計測できなかったが、ループ内の変数は外出ししておいた。 もしかしたらコンパイラがよしなに最適化してくれる部分かもしれない。

結論

パフォーマンスが必要な場面では、Debug.Assertは使わないようにしよう。