JavaScriptでベクトル、行列計算の高速化 / magicien 

JavaScriptでベクトルや行列の計算を高速化しようとしてやったこと。

WebGLを始めた頃、まだライブラリもさほど世の中に無い状態だったので、ベクトルや行列計算のライブラリを自分で実装しました。
3Dのプログラミングというと、8割方ベクトルと行列の計算なんじゃないかと思うのですが、ということは、ベクトルや行列の計算を高速化することで、プログラム全体の高速化が望めるのではないかと考えました。
で、いろいろと実験した結果、割と効果があったのが、ループアンローリングという手法。
CPUのパイプラインが云々で分岐を無くすことで、コードの先読みを有効活用したりデータの依存関係をコンパイラに分かりやすくしたりとかなんとかでまぁあれなんですけど、JavaScriptみたいなスクリプト言語で効果があるのやら駄目もとでやってみたところ、思いのほか有効でした。
ループアンローリングをしない場合だと、4x4の行列計算は次のような書き方になるかと思います。
// 行列の定義
var matrix1 = [[11, 12, 13, 14], [21, 22, 23, 24], [31, 32, 33, 34], [41, 42, 43, 44]];
var matrix2 = [[11, 12, 13, 14], [21, 22, 23, 24], [31, 32, 33, 34], [41, 42, 43, 44]];
var matrix3 = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]];
// 行列のかけ算
for(var i=0; i<4; i++){
  for(var j=0; j<4; j++){
    for(var k=0; k<4; k++){
      matrix3[i][j] += matrix1[i][k] * matrix2[k][j];
    }
  }
}
ループアンローリングはループを全部展開してしまって、ループ毎に発生する分岐とindexの変数を無くします。
ついでに、配列も無くしてしまって変数を参照するときのオーバーヘッドを少なくしてやります。
すると、
// 行列の定義
var matrix1 = new Object();
matrix1.m11 = 11; matrix1.m12 = 12; matrix1.m13 = 13; matrix1.m14 = 14;
matrix1.m21 = 21; matrix1.m22 = 22; matrix1.m23 = 23; matrix1.m24 = 24;
matrix1.m31 = 31; matrix1.m32 = 32; matrix1.m33 = 33; matrix1.m34 = 34;
matrix1.m41 = 41; matrix1.m42 = 42; matrix1.m43 = 43; matrix1.m44 = 44;
var matrix2 = new Object();
matrix2.m11 = 11; matrix2.m12 = 12; matrix2.m13 = 13; matrix2.m14 = 14;
matrix2.m21 = 21; matrix2.m22 = 22; matrix2.m23 = 23; matrix2.m24 = 24;
matrix2.m31 = 31; matrix2.m32 = 32; matrix2.m33 = 33; matrix2.m34 = 34;
matrix2.m41 = 41; matrix2.m42 = 42; matrix2.m43 = 43; matrix2.m44 = 44;
var matrix3 = new Object();
matrix3.m11 = 0; matrix3.m12 = 0; matrix3.m13 = 0; matrix3.m14 = 0;
matrix3.m21 = 0; matrix3.m22 = 0; matrix3.m23 = 0; matrix3.m24 = 0;
matrix3.m31 = 0; matrix3.m32 = 0; matrix3.m33 = 0; matrix3.m34 = 0;
matrix3.m41 = 0; matrix3.m42 = 0; matrix3.m43 = 0; matrix3.m44 = 0;
// 行列のかけ算
matrix3.m11 = matrix1.m11 * matrix2.m11 + matrix1.m12 * matrix2.m21 + matrix1.m13 * matrix2.m31 + matrix1.m14 * matrix2.m41;
matrix3.m12 = matrix1.m11 * matrix2.m12 + matrix1.m12 * matrix2.m22 + matrix1.m13 * matrix2.m32 + matrix1.m14 * matrix2.m42;
matrix3.m13 = matrix1.m11 * matrix2.m13 + matrix1.m12 * matrix2.m23 + matrix1.m13 * matrix2.m33 + matrix1.m14 * matrix2.m43;
matrix3.m14 = matrix1.m11 * matrix2.m14 + matrix1.m12 * matrix2.m24 + matrix1.m13 * matrix2.m34 + matrix1.m14 * matrix2.m44;
matrix3.m21 = matrix1.m21 * matrix2.m11 + matrix1.m22 * matrix2.m21 + matrix1.m23 * matrix2.m31 + matrix1.m24 * matrix2.m41;
matrix3.m22 = matrix1.m21 * matrix2.m12 + matrix1.m22 * matrix2.m22 + matrix1.m23 * matrix2.m32 + matrix1.m24 * matrix2.m42;
matrix3.m23 = matrix1.m21 * matrix2.m13 + matrix1.m22 * matrix2.m23 + matrix1.m23 * matrix2.m33 + matrix1.m24 * matrix2.m43;
matrix3.m24 = matrix1.m21 * matrix2.m14 + matrix1.m22 * matrix2.m24 + matrix1.m23 * matrix2.m34 + matrix1.m24 * matrix2.m44;
matrix3.m31 = matrix1.m31 * matrix2.m11 + matrix1.m32 * matrix2.m21 + matrix1.m33 * matrix2.m31 + matrix1.m34 * matrix2.m41;
matrix3.m32 = matrix1.m31 * matrix2.m12 + matrix1.m32 * matrix2.m22 + matrix1.m33 * matrix2.m32 + matrix1.m34 * matrix2.m42;
matrix3.m33 = matrix1.m31 * matrix2.m13 + matrix1.m32 * matrix2.m23 + matrix1.m33 * matrix2.m33 + matrix1.m34 * matrix2.m43;
matrix3.m34 = matrix1.m31 * matrix2.m14 + matrix1.m32 * matrix2.m24 + matrix1.m33 * matrix2.m34 + matrix1.m34 * matrix2.m44;
matrix3.m41 = matrix1.m41 * matrix2.m11 + matrix1.m42 * matrix2.m21 + matrix1.m43 * matrix2.m31 + matrix1.m44 * matrix2.m41;
matrix3.m42 = matrix1.m41 * matrix2.m12 + matrix1.m42 * matrix2.m22 + matrix1.m43 * matrix2.m32 + matrix1.m44 * matrix2.m42;
matrix3.m43 = matrix1.m41 * matrix2.m13 + matrix1.m42 * matrix2.m23 + matrix1.m43 * matrix2.m33 + matrix1.m44 * matrix2.m43;
matrix3.m44 = matrix1.m41 * matrix2.m14 + matrix1.m42 * matrix2.m24 + matrix1.m43 * matrix2.m34 + matrix1.m44 * matrix2.m44;
うわぁ…となります。
一見するとすごく効率が悪そうですが、実際はこちらの方が格段に早いです。
あとは変数名の文字数を訳が分からなくならない程度に短くしてコード量を減らしてみたり、関数呼び出しを減らすように気をつけたりといった感じです。
配列を使わない方法で行列を定義した場合に一番苦労したのは、逆行列の計算。頭がおかしくなるかと思いました。まだバグが残ってるかもしれないという不安が付きまといます。
どなたかライブラリを使ってみてデバッグに協力してもらえないでしょうか。
といってもドキュメント皆無だからなぁ。早くドキュメントを作成せねば。
2012/09/26(Wed) 02:13:42