Mathは本当に遅いのか
色の距離(色差)を計算するときにちょっとだけ試してみたので,実際によくある(小手先)高速化手法でMathが速くなるのか検証してみた.
検証方法
JavaとAndroidで検証.
単純に実行時間をSystem.nanoTime
で取得し,比較している.
検証順や検証タイミングで最適化がかかったりするので,何回か実行して落ち着いた値で比較している.
Javaの検証はIntel Xeon E5 3.5GHzのMac Pro,Androidの検証はQualcomm Snapdragon 800 MSM8974 2.2GHzのSO-02Fで試している.
従来のMathクラスと,実装したDMathクラスで比較した.
10万回実行して1回あたりの実行時間をnano秒で表示している.詳しい方法は一番下を参照.
べき乗の高速化
べき乗を計算するMath.pow()
は小数のべき乗もサポートしているせいもあってかやたら遅い.最近のJavaやAndroidでも遅いかどうか検証.
public static final double pow(double v, int n){
double vv = v;
for (int i = 1; i < n; i++) {
vv *= v;
}
return vv;
}
まずは2乗,n=2の場合から.
Math : 48.35398
DMath : 49.00398
Math : 1174.02609
DMath : 850.5849
となり,Androidの場合に効果有り.
n=5の場合は,
Math : 119.70004
DMath : 49.93871
Math : 1812.45263
DMath : 1155.4152
となり,両方で効果有り.
2乗の場合は最適化してるんでしょうかね.n=3でも両方で効果有りでした.
関数はfor文で書いているが,要は掛け算した方が速いということなので,nの2乗を計算するときにわざわざMath.pow()
を引っ張り出さずにn*n
と書く方が速いし文字も少なくて済む.
5乗とかはn*n*n*n*n
って書くと何乗してるのか分からないからfor文にする方がいいと思う.試してみたけど性能は変わらない.
後,当然だけど小数を何回も掛け算すると誤差が大きくなる.精度を求める場合はMath.pow()
を使いましょう.
hypotの高速化
ピタゴラスの定理で出てくる$\sqrt{a^2+b^2}$を計算するのがMath.hypot()
.高速化してみた.
public static final double hypot(double a, double b){
return Math.sqrt(a*a + b*b);
}
高速化っていいながら単に書き換えただけです.まぁ,べき乗の部分を展開してはいますが.
で,結果.
Math : 598.20226
DMath : 67.31029
Math : 1586.08674
DMath : 1303.91898
という感じで両方で効果有り.
で,実はそれもそのはずでこの方法だと2乗したり足し算したりしたときにバッファオーバーフローすると計算できないし,そのときに丸め誤差が発生しちゃうので精度が落ちます.
まぁ,大きな値は使わないとか,そんな精密な値は必要無いとか,実用上問題無い場面で使ってください.
toDegreeの高速化
よくラジアンを角度に変えるtoDegreeは自分で書いた方が速いっていうのを見るんだけどホントか?っていうことでやってみた.
private static final double toD = 180.0 / Math.PI;
public static final double toDegrees(double rad){
return rad * toD;
}
で,ぶっちゃけMath.javaを読むとほぼ同じことが書いてあるのでやる意味無いと思うんだけど,staticに変数計算してるからワンチャンあるかも・・・!?(最適化されてるはずだけど)
Math : 52.03437
DMath : 52.4816
Math : 1065.92847
DMath : 1057.95507
はい,効果ありませんでした.Androidが勝ってるように見えるけれど,場合によっては逆転してるのでただの計測誤差です.
三角関数の高速化(近似)
三角関数は非常に遅いので,あらかじめメモリに計算結果を展開しておいて,メモリアクセスさせる方が速いっていうのは割と昔から知られている手法なんだけど,Cでベタに書くならまだしもJavaでそんなことやって速くなるのかな?っていうことでやってみました.
private static final int NUM = 1000;
private static final double[] sinMap;
static {
sinMap = new double[NUM];
for (int i = 0; i < NUM; i++) {
sinMap[i] = Math.sin((double) i / NUM * Math.PI * 2);
}
}
public static final double sin(double t){
t = t / (Math.PI * 2) * NUM;
return sinMap[ ((int) t ) % NUM];
}
NUMが粒度で値を大きくするほど誤差が小さくなります.で,結果.
Math : 104.53175
DMath : 60.14656
Math : 1016.11446
DMath : 1028.96237
ということで意外にもJavaでは効果あり,Androidで効果無し.昔この手のことをAndroidでやったら無茶苦茶速くなったんだけど,実装が変わったんでしょうね.cosとかtanは省略,atanはちょっと方法が思いつかなかったです.
sqrtの高速化(近似)
sqrtは1から近い領域でほとんど線形なので近似できます.まぁ,使用範囲が限られちゃいますが.
public static final double sqrt(double v){
return 1d * ( v - 1d) / 2d;
}
で,結果.
Math : 50.19401
DMath : 50.36254
Math : 1009.85237
DMath : 999.24091
はい,効果無し.
roundの高速化
四捨五入するときに使うMath.round()
ですがMath.javaを見ると精度を出すために結構面倒くさい作りになってます.てことで簡単に作り直してみたのが以下の実装.
public static final long round(double v){
long l = (long) (v * 2);
return (l >> 1) + (l & 0x1);
}
要は2倍して奇数になるんだったら繰り上げときゃいいよね,という感じです.doubleを2倍するとこは工夫するともうちょい速く出来そうですが大した効果なさそうなのでこのままで.で,結果.
Math : 50.90829
DMath : 49.94111
Math : 1396.44914
DMath : 1016.95906
てことで,Javaは効果なし,Android効果有り・・・としたいんですが,Javaは何回やっても僅差で勝つので,効果あり・・・!ということにしといてください.
当然,2倍したりしてるので使える値はLong.MAXVALUEの半分までです.まぁ,足りますよね.
ceilとfloorは使用用途によってはintにキャストしたりするだけで事が足りそうなので省略.精度を出すにはやっぱりちゃんとMathを使ってください.
おわり
ネタ切れにつき終わり.
全ての方法について言えることですが,例えばNaNとかInfinityが突っ込まれたときの処理は無視しています.if文が増えるぐらいなので性能に影響は無さそうですが,使う側はその辺を理解して使ってください.
後,「JNIした方が速いんじゃないの?」という突っ込みは無しの方向でお願いします.
おまけ
検証用のソースは下記の通り.
public static final void task(String name, int num, MathTask math, MathTask dmath){
long start;
long mathTime = 0;
long dmathTime = 0;
for(int i = 0; i < num; i++){
start = System.nanoTime();
math.task(rand);
mathTime += (System.nanoTime() - start);
start = System.nanoTime();
dmath.task(rand);
dmathTime += (System.nanoTime() - start);
}
double mathResult = ((double) mathTime) / num;
double dmathResult = ((double) dmathTime) / num;
System.out.println("Math : " + mathResult);
System.out.println("DMath : " + dmathResult);
}
MathTaskクラスは引数にRandomを受け取るメソッドが1つだけのインタフェースでlambda的に書くために定義した.task(... (r)->Math.abs(r.nextInt()), ...)
みたいにして使用する.一応確認したが,こういった抽象化による実行時間への影響は見られなかった.
numに10万を指定して10万回の平均値を取っている.また,Androidでは10回同じ事を繰り返して落ち着いてきた値(3回ぐらい同じ結果が出てきたあたり)を掲載した.
JavaもAndroidも一番最初が一番遅く,何回も試行すると速くなってくるので何かしらの最適化が効いているんだと思う.(GCは動いてないっぽい)