アカウント名:
パスワード:
数値演算の精度を端折って高速化したと。
浮動小数点演算で、64ビットのdouble型演算の代わりに、可能な限り32ビットのfloat型の演算を使用することで、大幅にその演算速度が向上したという。
数値演算の精度が問題になる場面で、不具合が起きなければいいが・・・Officeスウィート系のWebアプリは怖くて使えんなあ。
インテル系のCPUなら倍精度もハードウェアで処理するから単精度に置き換えたところで速度がそれほど変わるとは思えないのですが。
確か前見たデータでは数％から数百％まで差があったけど下回ってるのは無かったな
floatだとデータ量がdoubleの半分になる。今どきのCPUだとメモリアクセスが一番遅い。加算も減算も分岐も数クロックで終わる、だがメモリーアクセスは数十クロック以上かかる。なんで今どきの最適化はメモリーアクセスを減らす以外対して効かない。
JSの数値型はdoubleだから、今まではfloatをエミュレートするのにコストがかかってたのよ
例えばA:float = B:float + 1.0は普通のJSだと本来A = ToFloat(ToDouble(B) + 1.0:double)とすることになる
実はこれなら今まででもA = B:float + 1.0:floatと最適化できてたんけど
A:float = B:float + C:float + 1.0みたいに少し違うパターンだと途端に最適化していいのかどうかの判断が難しくなってくるので、本当は結果が変わらないのでしていい場合もできてなかった
なのでこの度は、ネイティブからの「コード変換時に」floatで演算していい部分を「doubleをfloatの精度を持ったdoubleに丸める」という効果を持ったMath.fround関数で囲むことで明示的に示しfloat演算での無駄を100％無くすことに成功したよって話
擬似コードはこんな感じになるA:float = Math.fround(B:float + C:float) + 1.0これはつまりF:float = B:float + C:floatA:float = F:float + 1.0:floatと同じ意味になるから最初に挙げたパターンの判断のみで最適化可能A = B:float + C:float + 1.0:float
明らかに処理の内容を変えて「高速化」というのは疑問を感じますね。それで、C++に迫ったといわれてもなんか違う。
世の中の最適化を全否定だな。答えが一緒なら処理なんて関係ないでしょ。
型が単精度から倍精度に変わるんだよ？常に答えが一緒になるとは限らないでしょ。
んで、最適化によって値が変わる可能性があるから、Cとかにはvolatileが用意されてるわけで。JavaScriptにvolatileに相当するものは私の知る限りは無いはず。そういう言語で値が変わるかも知れない最適化ってのはちょっと問題ある気がする。
JavaScriptの仕様的にはオーバーフローしたら倍精度に勝手に変換するみたいだけど、そこら辺どうなんだろ。仕様に合わせて内部処理を最適化しただけって話ならいいんだけど。
数値計算の世界では、倍精度なら精度が高くて、単精度なら精度が低い、なんて思ってると違ってる場合もあります。
単純な数値表現の精度より、計算アルゴリズムの方が計算誤差に大きく影響するケースが少なくないためです。 例えば、単純に合計求めるだけでも値に大きさのばらつきがあると倍精度で愚直に加算するより、単精度でもソートしてから加算するアルゴリズムのほうが精度が高くなります。歴史がある数値計算ライブラリなどはそういう考慮が詰まっていて、倍精度で作られた下手なライブラリより単精度のライブラリの方が精度が高くなる、なって状況が簡単に起こります
まあ、数値計算の精度ってのは使いドコロに適したものを正しく使うってのが、このストーリーでも大事ってことですな。
ごめん、*可能な限り*単精度、って書いてあるね。なら問題無いのか。
Mozilla Hacksの元記事確認してみたが、最適化しても大丈夫っぽい。
まず、a,bをfloatとして、(float)((double)a + (double)b) と a + b は、倍精度で加算するか単精度で加算するかの違いがあるが、必ず同じ結果になるらしい。さらにこれと同じようなことが、加減乗除や平方根などで成り立つよう。
（倍精度で計算するとdouble roundingになるので単精度計算よりむしろ悪い結果を返してしまうコーナーケースが考えられるため、非自明な性質な気がするが、入力が単精度の値であることを使ってきちんと見ていけば計算結果にコーナーケースが出ないのと言えるのだと思う。気になるなら参照されてる論文見れば良いかと）
なお、a + b + cについて同じようなことを考えると、これは正しくない。たとえば、(1 + 2^-24) + 2^-24とか。
で、JavaScriptでは倍精度浮動小数点数しか存在しない。そして、浮動小数点数同士の計算は倍精度として行わないといけない。そこで、Math.froundという、倍精度浮動小数点数を単精度相当の値に変換する関数を用意する。これはES6に入るんだそうな（ただしfroundが無くてもFloat32Arrayに入れるというイディオムで一応変換可能）。
a = Math.fround(a); b = Math.fround(b); x = Math.fround(a + b);
とすれば、先の (float)((double)a + (double)b) と同じことなので、安全に単精度数同士の加算として扱える。
なので、emscriptenに、floatへ代入する際にガシガシMath.fround()で囲ってもらえば高速化できると。
# 型とはなんだったのか
普通に入力する値は1.5とか2.0とかが大半なんで、ポインタ算をしなければfloatで最適化した方がいい、ってことなんだろうね。C++だってautofloatみたいな型をでっちあげて、必要な時だけfloatとしてふるまうようにすれば、ずっと高速化できるってことだと思う。やっぱりポインタ算は鬱陶しいだろうけど。
asm.jsは基本的に別の別の型付き言語からの変換するのでfloatを使用されている箇所はそのままfloatの精度で計算できるんだよね。
ただし、JavaScriptを解釈しているときは一応常にdoubleの精度で計算したのと同じ結果を出すことを保障できないとマズイよな。だからコンパイル時にアノテーションがいるのかな。なんというかasm.jsがトランスレータに責任を押し付けただけのようでもあるけど。
Math.froundが適切に使われればdoubleと結果は変わらないし、asm.jsじゃなくてJITでも同等の最適化ができる。
んで、最適化によって値が変わる可能性があるから、Cとかにはvolatileが用意されてるわけで。
違うけど?
ん？冗長性の排除も最適化の一種だよね？それによってはき出す値が一定しないなら「最適化によって値が変わる」って言えると思ってたんだけど、違うかな。特にポインタの排除なんか、Cだと値が不定になるわけでしょ？
実際にvolatileが必要になるケースに出会った事がなくて資料上で把握していた知識なので、認識が間違ってたらその部分を指摘してもらえるととても嬉しい。
それはむしろ例えばgccの-ffloat-storeとか-fexcess-precisionとか-ffast-math-funsafe-math-optimizationsとかのオプションで変えるような動作なんじゃないか？丸めるとか丸めないとか、そんな類の動作の違いで結果として動かす環境によって下の方のビットが違ったり違わなかったりとかするわけだけど。
volatileのは最適化じゃなくて何かのバグだろう。volatileはその有無で計算内容が変わるわけじゃない。
volatileが必要になる典型的パターンて外部とメモリ経由でやりとりする場合じゃないの。フラグの監視とか最適化によってメモリとの値の読み書きがレジスタ上だけで終わっちゃう可能性あるけど、こうなってくるとDMAとかで外部デバイスが値を書き換えたときにレジスタの中身をみちゃうので書き換えられたことが解らない。あるいは別スレッドで書き換えた場合とかね。言語的には自スレッド以外が書き換えるかどうかを指定する手段がないのでvolatileつけて毎回メモリ見に行かせないと困る。
確かに挙動は変わるんだけど、今話題になってる計算精度の問題とはまた違う。
volatileはその有無で計算内容が変わるわけじゃない。
volatileの有無で演算の順序が変わり計算結果に影響がでる可能性は当たり前に考えられるよ。
ちょっと自信ないけど、
volatile double hoge;
ってあったとすると、hogeへのアクセスは必ずメモリを読み書きするんだよね？doubleはメモリ上では64ビットだけど、x86のFPUレジスタは80ビットだから、誤差が出るかもしれないし出ないかもしれない。私もよくわかりませんが、どなたか検証してくれないかな。
ウチの環境(core2duo Cygwin gcc 4.7.3)で試してみた結果が↓
#include <stdio.h>#include <limits.h>
int main(){ const int x = INT_MAX; { double e = 1.0; const double m = 1.0 + 1.0 / x; int i; for (i = 0; i < x; i++) { e *= m; } printf("(1.0 + 1.0 / %d) ** %d = %1.20lf\n", x, x, e); } { volatile double e = 1.0; const double m = 1.0 + 1.0 / x; int i; for (i = 0; i < x; i++) { e *= m; } printf("(1.0 + 1.0 / %d) ** %d = %1.20lf\n", x, x, e); } return 0;}
$ gcc -O2 e.c && ./a.exe(1.0 + 1.0 / 2147483647) ** 2147483647 = 2.71828182656034833542(1.0 + 1.0 / 2147483647) ** 2147483647 = 2.71828182653240091327
お、誤差出ましたか。
http://homepage1.nifty.com/herumi/prog/prog90.html [nifty.com]
↑によると、fnstcwという命令で、演算精度を変更できるらしいです。同じマシンでも、コンパイラによって、設定が異なるとか。
ほうほう。一致してるのが10進で10桁(+一の位が2なので1bit)だから(10/log2)+1でだいたい33bitsとちょっと(？)ってとこか。「オプションを何も付けてなきゃ計算精度も格納精度も一緒だから誤差は出ない」かと思ってた。オプションつけるとまた違うんだろうなー。
バイナリが 32bit だからだろう。32bit版では、浮動小数点計算には x87 を使う。最適化すれば途中結果はx87 のレジスタ上に残っているが、最適化しなければ x87 (80bit)とメモリ(64bit)との間を行ったり来たりする。
対して、64bit 版では SSE などの SIMD レジスタ(64bit)を使う。従って、実行結果は一致する(実際一致した)。
これは、-mfpmath=sse オプションが設定されているかどうかに依存するらしい。32bit版では設定されておらず(明示的に指定する必要があり)、64bit版ではデフォルトで設定されている。
info gcc より：'-mfpmath=UNIT'
$ gcc -O2 -mfpmath=387 e.c && ./a.exe(1.0 + 1.0 / 2147483647) ** 2147483647 = 2.71828182656034833542(1.0 + 1.0 / 2147483647) ** 2147483647 = 2.71828182653240091327
$ gcc -O2 -mfpmath=sse e.c && ./a.exe(1.0 + 1.0 / 2147483647) ** 2147483647 = 2.71828182656008765505(1.0 + 1.0 / 2147483647) ** 2147483647 = 2.71828182656008765505
>あるいは別スレッドで書き換えた場合とかね。言語的には自スレッド以外が書き換えるかどうかを指定する手段がないのでvolatileつけて毎回メモリ見に行かせないと困る。
そのvolatileの使い方は間違ってますよ。C11ではAtomicが追加されたたのでそれを使用しましょう。
それ以前に浮動小数点演算は精度に関係なく答が一緒になる保証などない。
釣り？入力が同じなら出力は同じだよ？
マクロな話してるんでしょ例えばsinとかは同じdoubleでも実装や言語によって全然違うし
同じソースプログラム、同じ動作環境でも、コンパイラの最適化やx87とSSEの違いなんかで簡単に違う結果になるよ。
入力が同じで出力が一緒にならない例
int main(){ const int x = INT_MAX; double e0 = 1.0; double e1 = 1.0; double e2 = 1.0; double e3 = 1.0; double e4 = 1.0; double e5 = 1.0; double e6 = 1.0; double e7 = 1.0;
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
Stay hungry, Stay foolish. -- Steven Paul Jobs
数値演算の精度が問題になることないの？ (スコア:0)
数値演算の精度を端折って高速化したと。
浮動小数点演算で、64ビットのdouble型演算の代わりに、可能な限り32ビットのfloat型の演算を使用することで、大幅にその演算速度が向上したという。
数値演算の精度が問題になる場面で、不具合が起きなければいいが・・・Officeスウィート系のWebアプリは怖くて使えんなあ。
Re:数値演算の精度が問題になることないの？ (スコア:1)
インテル系のCPUなら倍精度もハードウェアで処理するから
単精度に置き換えたところで速度がそれほど変わるとは
思えないのですが。
Re: (スコア:0)
従来のFPUを(というか、FPUとして)使い続けるなら、確かに、むしろ、倍精度の方が速いことの方が多いでしょう。
Re: (スコア:0)
確か前見たデータでは数％から数百％まで差があったけど下回ってるのは無かったな
Re: (スコア:0)
floatだとデータ量がdoubleの半分になる。
今どきのCPUだとメモリアクセスが一番遅い。加算も減算も分岐も数クロックで終わる、だがメモリーアクセスは数十クロック以上かかる。
なんで今どきの最適化はメモリーアクセスを減らす以外対して効かない。
Re:数値演算の精度が問題になることないの？ (スコア:1)
JSの数値型はdoubleだから、今まではfloatをエミュレートするのにコストがかかってたのよ
例えば
A:float = B:float + 1.0
は普通のJSだと本来
A = ToFloat(ToDouble(B) + 1.0:double)
とすることになる
実はこれなら今まででも
A = B:float + 1.0:float
と最適化できてたんけど
A:float = B:float + C:float + 1.0
みたいに少し違うパターンだと途端に最適化していいのかどうかの判断が難しくなってくるので、
本当は結果が変わらないのでしていい場合もできてなかった
なのでこの度は、ネイティブからの「コード変換時に」floatで演算していい部分を
「doubleをfloatの精度を持ったdoubleに丸める」という効果を持ったMath.fround関数で囲むことで明示的に示し
float演算での無駄を100％無くすことに成功したよって話
擬似コードはこんな感じになる
A:float = Math.fround(B:float + C:float) + 1.0
これはつまり
F:float = B:float + C:float
A:float = F:float + 1.0:float
と同じ意味になるから最初に挙げたパターンの判断のみで最適化可能
A = B:float + C:float + 1.0:float
Re: (スコア:0)
明らかに処理の内容を変えて「高速化」というのは疑問を感じますね。
それで、C++に迫ったといわれてもなんか違う。
Re: (スコア:0)
世の中の最適化を全否定だな。答えが一緒なら処理なんて関係ないでしょ。
Re: (スコア:0)
型が単精度から倍精度に変わるんだよ？
常に答えが一緒になるとは限らないでしょ。
んで、最適化によって値が変わる可能性があるから、Cとかにはvolatileが用意されてるわけで。
JavaScriptにvolatileに相当するものは私の知る限りは無いはず。
そういう言語で値が変わるかも知れない最適化ってのはちょっと問題ある気がする。
JavaScriptの仕様的にはオーバーフローしたら倍精度に勝手に変換するみたいだけど、そこら辺どうなんだろ。
仕様に合わせて内部処理を最適化しただけって話ならいいんだけど。
Re:数値演算の精度が問題になることないの？ (スコア:1)
数値計算の世界では、倍精度なら精度が高くて、単精度なら精度が低い、なんて思ってると違ってる場合もあります。
単純な数値表現の精度より、計算アルゴリズムの方が計算誤差に大きく影響するケースが少なくないためです。 例えば、単純に合計求めるだけでも値に大きさのばらつきがあると倍精度で愚直に加算するより、単精度でもソートしてから加算するアルゴリズムのほうが精度が高くなります。歴史がある数値計算ライブラリなどはそういう考慮が詰まっていて、倍精度で作られた下手なライブラリより単精度のライブラリの方が精度が高くなる、なって状況が簡単に起こります
まあ、数値計算の精度ってのは使いドコロに適したものを正しく使うってのが、このストーリーでも大事ってことですな。
の
Re: (スコア:0)
ごめん、*可能な限り*単精度、って書いてあるね。
なら問題無いのか。
Re:数値演算の精度が問題になることないの？ (スコア:3, 参考になる)
Mozilla Hacksの元記事確認してみたが、最適化しても大丈夫っぽい。
まず、a,bをfloatとして、(float)((double)a + (double)b) と a + b は、倍精度で加算するか単精度で加算するかの違いがあるが、必ず同じ結果になるらしい。さらにこれと同じようなことが、加減乗除や平方根などで成り立つよう。
（倍精度で計算するとdouble roundingになるので単精度計算よりむしろ悪い結果を返してしまうコーナーケースが考えられるため、非自明な性質な気がするが、入力が単精度の値であることを使ってきちんと見ていけば計算結果にコーナーケースが出ないのと言えるのだと思う。気になるなら参照されてる論文見れば良いかと）
なお、a + b + cについて同じようなことを考えると、これは正しくない。たとえば、(1 + 2^-24) + 2^-24とか。
で、JavaScriptでは倍精度浮動小数点数しか存在しない。そして、浮動小数点数同士の計算は倍精度として行わないといけない。そこで、Math.froundという、倍精度浮動小数点数を単精度相当の値に変換する関数を用意する。これはES6に入るんだそうな（ただしfroundが無くてもFloat32Arrayに入れるというイディオムで一応変換可能）。
a = Math.fround(a);
b = Math.fround(b);
x = Math.fround(a + b);
とすれば、先の (float)((double)a + (double)b) と同じことなので、安全に単精度数同士の加算として扱える。
なので、emscriptenに、floatへ代入する際にガシガシMath.fround()で囲ってもらえば高速化できると。
# 型とはなんだったのか
Re: (スコア:0)
普通に入力する値は1.5とか2.0とかが大半なんで、ポインタ算をしなければfloatで最適化した方がいい、ってことなんだろうね。C++だってautofloatみたいな型をでっちあげて、必要な時だけfloatとしてふるまうようにすれば、ずっと高速化できるってことだと思う。やっぱりポインタ算は鬱陶しいだろうけど。
Re: (スコア:0)
asm.jsは基本的に別の別の型付き言語からの変換するのでfloatを使用されている箇所はそのままfloatの精度で計算できるんだよね。
Re: (スコア:0)
ただし、JavaScriptを解釈しているときは一応常にdoubleの精度で計算したのと同じ結果を出すことを保障できないとマズイよな。
だからコンパイル時にアノテーションがいるのかな。なんというかasm.jsがトランスレータに責任を押し付けただけのようでもあるけど。
Re: (スコア:0)
Math.froundが適切に使われればdoubleと結果は変わらないし、asm.jsじゃなくてJITでも同等の最適化ができる。
Re: (スコア:0)
んで、最適化によって値が変わる可能性があるから、Cとかにはvolatileが用意されてるわけで。
違うけど?
Re: (スコア:0)
ん？
冗長性の排除も最適化の一種だよね？
それによってはき出す値が一定しないなら「最適化によって値が変わる」って言えると思ってたんだけど、違うかな。
特にポインタの排除なんか、Cだと値が不定になるわけでしょ？
実際にvolatileが必要になるケースに出会った事がなくて資料上で把握していた知識なので、認識が間違ってたらその部分を指摘してもらえるととても嬉しい。
Re:数値演算の精度が問題になることないの？ (スコア:1)
それはむしろ例えばgccの-ffloat-storeとか-fexcess-precisionとか-ffast-math-funsafe-math-optimizationsとかのオプションで変えるような動作なんじゃないか？丸めるとか丸めないとか、そんな類の動作の違いで結果として動かす環境によって下の方のビットが違ったり違わなかったりとかするわけだけど。
volatileのは最適化じゃなくて何かのバグだろう。volatileはその有無で計算内容が変わるわけじゃない。
Re: (スコア:0)
volatileが必要になる典型的パターンて外部とメモリ経由でやりとりする場合じゃないの。
フラグの監視とか最適化によってメモリとの値の読み書きがレジスタ上だけで終わっちゃう可能性あるけど、
こうなってくるとDMAとかで外部デバイスが値を書き換えたときにレジスタの中身をみちゃうので書き換えられたことが解らない。
あるいは別スレッドで書き換えた場合とかね。言語的には自スレッド以外が書き換えるかどうかを指定する手段がないので
volatileつけて毎回メモリ見に行かせないと困る。
確かに挙動は変わるんだけど、今話題になってる計算精度の問題とはまた違う。
Re: (スコア:0)
volatileはその有無で計算内容が変わるわけじゃない。
volatileの有無で演算の順序が変わり計算結果に影響がでる可能性は当たり前に考えられるよ。
Re:数値演算の精度が問題になることないの？ (スコア:1)
ちょっと自信ないけど、
volatile double hoge;
ってあったとすると、hogeへのアクセスは必ずメモリを読み書きするんだよね？
doubleはメモリ上では64ビットだけど、x86のFPUレジスタは80ビットだから、
誤差が出るかもしれないし出ないかもしれない。
私もよくわかりませんが、どなたか検証してくれないかな。
Re:数値演算の精度が問題になることないの？ (スコア:2, 参考になる)
ウチの環境(core2duo Cygwin gcc 4.7.3)で試してみた結果が↓
#include <stdio.h>
#include <limits.h>
int main()
{
const int x = INT_MAX;
{
double e = 1.0;
const double m = 1.0 + 1.0 / x;
int i;
for (i = 0; i < x; i++) {
e *= m;
}
printf("(1.0 + 1.0 / %d) ** %d = %1.20lf\n", x, x, e);
}
{
volatile double e = 1.0;
const double m = 1.0 + 1.0 / x;
int i;
for (i = 0; i < x; i++) {
e *= m;
}
printf("(1.0 + 1.0 / %d) ** %d = %1.20lf\n", x, x, e);
}
return 0;
}
$ gcc -O2 e.c && ./a.exe
(1.0 + 1.0 / 2147483647) ** 2147483647 = 2.71828182656034833542
(1.0 + 1.0 / 2147483647) ** 2147483647 = 2.71828182653240091327
Re:数値演算の精度が問題になることないの？ (スコア:1)
お、誤差出ましたか。
http://homepage1.nifty.com/herumi/prog/prog90.html [nifty.com]
↑によると、fnstcwという命令で、演算精度を変更できるらしいです。
同じマシンでも、コンパイラによって、設定が異なるとか。
Re:数値演算の精度が問題になることないの？ (スコア:1)
ほうほう。
一致してるのが10進で10桁(+一の位が2なので1bit)だから(10/log2)+1でだいたい33bitsとちょっと(？)ってとこか。
「オプションを何も付けてなきゃ計算精度も格納精度も一緒だから誤差は出ない」かと思ってた。
オプションつけるとまた違うんだろうなー。
Re: (スコア:0)
バイナリが 32bit だからだろう。32bit版では、浮動小数点計算には x87 を使う。最適化すれば途中結果はx87 のレジスタ上に残っているが、最適化しなければ x87 (80bit)とメモリ(64bit)との間を行ったり来たりする。
対して、64bit 版では SSE などの SIMD レジスタ(64bit)を使う。従って、実行結果は一致する(実際一致した)。
これは、-mfpmath=sse オプションが設定されているかどうかに依存するらしい。32bit版では設定されておらず(明示的に指定する必要があり)、64bit版ではデフォルトで設定されている。
info gcc より：
'-mfpmath=UNIT'
Re: (スコア:0)
$ gcc -O2 -mfpmath=387 e.c && ./a.exe
(1.0 + 1.0 / 2147483647) ** 2147483647 = 2.71828182656034833542
(1.0 + 1.0 / 2147483647) ** 2147483647 = 2.71828182653240091327
$ gcc -O2 -mfpmath=sse e.c && ./a.exe
(1.0 + 1.0 / 2147483647) ** 2147483647 = 2.71828182656008765505
(1.0 + 1.0 / 2147483647) ** 2147483647 = 2.71828182656008765505
Re: (スコア:0)
>あるいは別スレッドで書き換えた場合とかね。言語的には自スレッド以外が書き換えるかどうかを指定する手段がないのでvolatileつけて毎回メモリ見に行かせないと困る。
そのvolatileの使い方は間違ってますよ。
C11ではAtomicが追加されたたのでそれを使用しましょう。
Re: (スコア:0)
型が単精度から倍精度に変わるんだよ？
常に答えが一緒になるとは限らないでしょ。
それ以前に浮動小数点演算は精度に関係なく答が一緒になる保証などない。
Re: (スコア:0)
釣り？
入力が同じなら出力は同じだよ？
Re: (スコア:0)
マクロな話してるんでしょ
例えばsinとかは同じdoubleでも実装や言語によって全然違うし
Re: (スコア:0)
同じソースプログラム、同じ動作環境でも、コンパイラの最適化やx87とSSEの違いなんかで簡単に違う結果になるよ。
Re: (スコア:0)
入力が同じで出力が一緒にならない例
#include <stdio.h>
#include <limits.h>
int main()
{
const int x = INT_MAX;
double e0 = 1.0;
double e1 = 1.0;
double e2 = 1.0;
double e3 = 1.0;
double e4 = 1.0;
double e5 = 1.0;
double e6 = 1.0;
double e7 = 1.0;