JavaScript:float32による小数演算最適化

また翻訳です!


コンピュータ上で浮動小数点を表現する方法はいくつか存在する。だいたいのアーキテクチャではIEEE754標準を使っている。この標準では、倍精度浮動小数点(a.k.a. double or float64)を64bitで表し、単精度浮動小数点(a.k.a. float or float32)を32bitで表している。名前が示す通り、float64はfloat32よりもっと正確なんだ。だからパフォーマンスがあんまり重要視されないときは大体こっちを使おうねってアドバイスされる。

でもね、float32を使うことにもこんな利点がある:

  • float32は計算操作をするのにfloat64よりCPUサイクルがしばしば少ない。精度が低いからだ。
  • float64の計算をfloat32に対して行うには、いくらかオーバーヘッドが存在する。なぜなら、一旦float64に変換しないといけないから。これは、Float32arrayを使ってデータを格納しているときにしばしば発生する。WebGLを使ったコードや、EmscriptenでコンパイルされてC++のfloatがfloat32として格納されいるけど計算はJavaScriptのfloat64として行っている場合ではよくあることだ。
  • float32は半分のメモリしか使わない。プログラムのメモリ総使用量を減らすし、メモリーがボトルネックになるような(memory-bound)計算では速度も速くなるだろう。
  • float32に特化した標準C関数は、我々の調査したいくつかのライブラリではfloat64のバージョンより速かった。

JavaScriptにおいて、Number値はfloat64として定義されていて、すべての計算もfloat64として行うことが定義されている。さて、JS処理系がいままで長い間高速化のために利用していたfloat64の特性が、float64の値が十分小さい整数のとき、float64での計算結果は整数での計算結果と全くおなじ、ということだ(桁溢れが発生しなければ!)。JS処理系は、この特性を、整数の値を(floatでなく)生の整数として保持しておいて、整数演算で計算することで(そして桁溢れをチェックすることで)利用してきた。実際、次の少なくとも3種類の表現が実際に使われている:31bit整数、int32_t、uint32_t(くわしくはAndy Wingoの書いたこの値の表現に関する記事を見てみてね!)。

これらを全部踏まえると、一ついい感じの疑問が湧いてくる:似たような事を、float32で出来ないかな!?

答えは「しばしば可能」で、ES6で追加される新しいMath.fround関数を使うとプログラマ側がいつfloat32演算を使うかをコントロールすることが出来る。

いつ安全にfloat64演算の代わりにfloat32演算が使える?

Samuel A. Figueroaが“When is double rounding innocuous?” (SIGNUM Newsl. 30, 3, July 1995, 21-26)で書いているんだけど、float32とfloat64で交換がなりたつ恒等式がいくつかある。入力がfloat32であるかぎり、float32での演算とfloat64での演算、どちらを使ってもよくて、同じ結果を得られるんだ。もっと正確に言うなら、{+,-,*,/}のそれぞれの演算について、float32版の演算を行う関数であるop_f32と、float64版の演算を行う関数であるop_f64があったとすると、次の恒等式が成り立つんだ。C++で表現すると、こんな感じ:

  float op_f32(float x, float y);
  double op_f32(double x, double y);
  assert(op_f32(x,y) == (float) op_f64( (double)x, (double)y ));

似たような恒等式が、sqrtとかその他の数学関数のような単項演算にも成り立つ。

ただし、この性質は、それぞれの演算の前後でfloat32にcastした場合に成り立っている。たとえば、x=1024でy=0.0001で、さらにz=1024であるときに、(x+y)+zはfloat32の二回の足し算として見た時とfloat64の二回の足し算とみた場合では、もはや同じ結果にはならない。

この恒等式は、コンパイラがfloat64の演算のかわりにfloat32の演算を使って最適化を行うための、前提条件を与える。実際に、gccはこの恒等式を利用していて、さっきの恒等式の右辺のような式(float64のコード)があったら、左辺のような式(float32の式)を生成する。

でも、いつJavaScriptはfloat32の値を持ちうるんだろう?WebGLとそれに付随するTypedArray APIが使えるHTML5では、答えはこうなる:Float32Arrayから読む時と、書く時、だ。

たとえば、このコードを見てみよう:

  var f32 = new Float32Array(1000);
  for(var i = 0; i < 1000; ++i)
    f32[i] = f32[i] + 1;

ループの中の足し算のコードは、たしかにさっきの恒等式と一致してる:f32配列からfloat32の値を持ってきて、float641に変換され、float64同士の足し算演算が行われ、そしてf32に書き戻すためにfloat32に再度キャストされる。(足している”1″というリテラルも、float32からfloat64にキャストしていると考えた。なぜなら、float32で1は正確に表現できるからだ)

でも、もっと複雑な式を書きたいときはどうしよう?不要なFloat32Arrayへの出し入れを式のそれぞれの式の一部分に追加して、計算した式の一部分の結果がつねにfloat32にキャストされるようにすることも出来る。でも、これらの追加の(不要な)出し入れはプログラムを遅くするし、我々の目標はプログラムを速くすることなので、それでは意味がない。

うん、十分に頭のいいコンパイラーさんなら確かに不要なこの手の出し入れを除去することができる。でも、性能の予測可能性は重要だから、もっとこの最適化が行われることを確実にしたい。かわりに、わたしたちは小さな組み込み関数を提案し、Ecma Script 6規格で取り入れられた:Math.froundだ。

Math.fround

Math.froundは来るべきES6標準で提案されている、新しい数学関数だ。この関数は入力された値をいちばん近いfloat32の値にまるめて、そのfloat32をNumber値として返す。つまり、Math.froundは意味としては2つぎのplyfill3と同値だ:

  if (!Math.fround) {
    Math.fround = (function() {
      var temp = new Float32Array(1);
      return function fround(x) {
        temp[0] = +x;
        return temp[0];
      }
    })();
  }

いくつかのブラウザではTypedArraysに対応していないけど、そういう時はまた別の複雑なpolyfillがあるよ。でも、TypedArraysを使わなくても、SpiderMonkey(FirefoxのJSエンジン)とJavaScriptCore(SafariのJSエンジン)の両方ですでにMath.froundが実装されているよ。V8(ChromeのJSエンジン)でも実装する計画があって、このissueでその状況が確認できる(訳注 すでに実装されてるっぽい)。

結果として、float32の演算として演算を行い続けるには、単に途中の結果をMath.froundで包めばいい:

  var f32 = new Float32Array(1000);
  for(var i = 0; i < 999; ++i)
    f32[i] = Math.fround(f32[i] + f32[i+1]) + 1;

プログラマに速いコードを書くのを許すだけではなく、EmscriptenみたいなJSコンパイラにも、float32のコードをよりbetterにすることを許す。たとえば、Emscriptenは現在C++のfloat演算をJSのNumberを用いたコードにコンパイルする。技術的には、Emscriptenは原理的にはFloat32Arrayへの出し入れを全ての演算ごとに行うことで余計なfloat64精度を取り除くことは出来るけど、とても遅くなってしまうだろう。だから、忠実性はパフォーマンスのために犠牲にされた。

この違いが何かを壊すことは非常にレアなんだけど(もし壊れてしまうなら、そのプログラムは「未定義動作」に依存してるということだ)、この違いがバグを起こした所を実際に見たことがあって、しかもそういうバグを追跡するのは全く楽しくない。Math.froundを使えば、Emscriptenはもっと効率的で、もっと元のC++コードに忠実なコードを生成できるんだ!

Float32 in IonMonkey

わたしのインターンシップでのプロジェクトは、Firefoxにこれらの最適化を組み込むことだった。まず最初のステップとして、一般的なFloat32の演算のサポートをIonMonkey JITバックエンドに追加した。つぎに、Math.froundを一般的な(最適化されていない)ビルトインとしてJavaScriptエンジンに追加した。最後に、Float32Array/Math.froundを使っているのを認識してfloat32演算を出来る限り使うように最適化する最適化パスをコンパイラに追加した。これらの最適化は、Firefox27から使うことが出来る(今はAuroraリリースチャンネルに入ってるよ→訳注 もうStableでもVersion30ですね)

で、どれくらい早くなるんだろう?ちいさなベンチマークでは(C++とJavaScript両方で)、50%くらいの大きなスピードアップを示した。でもこういうちいさなベンチマークはしばしばミスリーディングを引き起こすから、わたしは次のようなもっと現実的なベンチマークを書いて、float32の大量の演算がどれくらい速くなるか、実際にありそうな問題で調べた:

  • 逆行列計算:このベンチマークでは、いくつか行列を作って、その逆行列を計算し、float64とfloat32でどれくらい精度が失われるかを比べるために、もとの行列と掛け算した。このベンチマークには、gl-matrixの改造したバージョンを利用した。gl-matrixは、WebGLの行列計算を使ったフレームワークで、実世界のアプリケーションでも使われている。float32バージョンを作るためには、Math.froundの呼び出しだけを追加した。
  • 画像処理行列計算:このベンチマークでも行列をいくつか生成して、画像処理でよく使われる行列の計算を行う。移動・回転・スケーリング、などなど。このベンチではたくさんの基本操作や複雑な操作(例えばMath.cosやMath.sinを回転操作で呼び出す)をおこなう。で、 float32の演算を最適化したとき、このベンチではすごい改善が見られた。このベンチマークも、gl-matrixの改造したバージョンを使っている。
  • 指数関数:このベンチマークでは、大きなFloat32Arrayを予測可能な値で埋めて、つぎにそれぞれの要素の指数関数を、テイラー展開をつかって求めた。このベンチマークの主な目的は、足し算と掛け算の重さを測ることだ。
  • 高速離散フーリエ変換:このベンチマークでは、適当なニセのバッファを作って、高速離散フーリエ変換(FFT)を行った。このベンチマークには、他にも基本操作と数回のMath.sqrtへの呼び出しが含まれている。FFTのコードは、既存のライブラリ、dsp.jsから取ってきた。

次の表が違うデバイスで最新のFirefox Nightlyを実行したときの結果を示している。それぞれの数値が、Math.froundの呼び出しを追加してfloat32最適化を許すことで得られたスピードアップを示している(だから、高大きい方がより良いことを示している)。

使っているデスクトップマシンは、「ThinkPad Lenovo W530 (Intel(R) Core(TM) i7-3820QM CPU @ 2.70GHz, 8 cores, 16 GB RAM)」だ。電話もしくはタブレットと書いてあるときは、Firefox NightlyのAndroidバージョンの事をしめしている。

この結果をひと目みたら、自分でもベンチマークを取ってみたいって思うんじゃない?ここで自分で実行できるよ!(あ、でも忘れないで。Firefox 27かそれ以降を使うんだ)

ベンチマークのソースコードはgithubで見れるよ(gh-pagesブランチにある)

Device Matrix Inversions Matrix Graphics Exponential FFT
Desktop (x86) 33% 60% 30% 16%
Google Nexus 10 (ARM) 12% 38% 33% 25%
Google Nexus 4 (ARM) 42% 26% 38% 5%
Samsung Galaxy S3 (ARM) 38% 38% 24% 33%

Polyfilling Math.fround

すべてのJSエンジンでMath.froundが使えて最適化されるようになるまで、どうすればいいんだろう?上で紹介した忠実な方法ではなくて、こんな単純な恒等関数を使えばいい:

  var fround = Math.fround || function(x) { return x }

これがさっきのベンチマークが使っていて、かつ、上で示したように、殆どのコードで((訳註 一度他の関数に代入することによる?))違いをうまない。

すべてのモダンなJS処理系はだいたい小さな関数をハイエンドなJITでインライン化するので、このplyfillはパフォーマンス上のペナルティになることはない。それを確かめるために、例えばChromeの開発版で実行することもできる。しかしながら、いくつかの巨大なソースコードではインライン化が実行されず、plyfillのせいでパフォーマンスが悪くなったこともあった(たぶん、インライン化の深さ制限か、関数が何かしらの理由でJITコンパイルされなかったんだろう)。

まぁ簡単に言うと、「試してみる価値はある。そしてテストしよう」。

結論

結果は私達を元気づけてくれるものだった。Math.froundはES6の標準にはいるから、ほかのJS処理系も同じ最適化を行うようになってくれることが期待される。Webをゲームプラットフォームにしたいという観点からすると、低レイヤの今回のような最適化はより重要性を増してきていて、Webをよりネイティブ性能に近づけてくれると言えるだろう。ぜひFirefoxのNightlyAurolaでこの最適化をテストして、何かバグを見つけたらぜひ教えてね4

今回のことに参加してくれたすべての人に感謝したい:Jon CoppeardとDouglas CrosherにはARMバージョンを実装してくれたことを、Luke Wagner、 Alon ZakaiとDave Herman には校正とフィードバックを、そして、JavaScriptチームのみんなにヘルプとサポートを。


 

感想

JSの最適化もここまで来たかーって感じがします。今後はこういう「プログラマと処理系が手を組んで行う最適化」が増えてくるのでしょうかね。そういう最適化はたぶんまだ沢山できて効果がありそうな一方、プログラムを書いている人が知ってるか知ってないかでかなり速度が変わってくるわけで、JSを書くのがどんどん大変になっていきそうな…。やっぱJSはアセンブリなんや…(何)。

  1. 訳注 JavaScriptのNumberはfloat64と定義されているのでした []
  2. 訳註 速度を除いて []
  3. なんとWeb時代に生まれた単語で、古いブラウザで新しいブラウザと同じ機能を提供するための方法のこと []
  4. 訳註 もう30なので、製品版コードに入っています []