Flashで数値計算を高速化する方法

Flashで3Dなどでシュミレーションをすると、今後ますます高速な数値計算が求められると思います。Adobe MAXでの発表にあたり、数値計算のベンチマークをとっていったら、どんどん速くなっていったので、現状ここまで速くなったというのをまとめます。この件について、id:gyuque さんに激しく色々と教えてもらいました。深くお礼を申し上げます。

テスト内容

テスト内容として、要素数 100K のベクトルの内積を扱います。ベクトルの内積や行列の掛け算は、数値計算の最重要計算であり、かつ、ベクトルの内積は実装しやすいので、これにしました。ベンチマーク環境は、Win XP の Pentium4 3.2GHzです。２次キャッシュは 1MB なので、ベクトルは２次キャッシュに収まりきっていません。また、Flash Player は flashplayer_10_sa_debug.exe を使用しています。

また、ベンチマークをとるにあたって、初回起動と Flash Player で、ファイル(F) -> 1 を入力して、リロードした場合で、大きく実行速度が変わる場合があり、その場合は、実行時間を両方明記しました。変わらない場合がほとんどで、その場合は全体の平均にしています。

パターン１

これが僕が最初に実装した方法。

package 
{
  import flash.display.Sprite;

  public class DotProduct extends Sprite
  {
    public function DotProduct() 
    {
      var ary1:Array = new Array(100 * 1024);
      var ary2:Array = new Array(100 * 1024);
      var i:int;
      for (i = 0; i < 100 * 1024; i++) {
        ary1[i] = i * 0.1;
        ary2[i] = i * 0.1;
      }
      
      var start:Date = new Date();
      var sum:Number = 0;
      for (var j:int = 0; j < 1000; j++) {
        for (i = 0; i < ary1.length; i++) {
          sum += ary1[i] * ary2[i];
        }
      }
      var end:Date = new Date();
      trace("sum = " + sum + ", time = " + (end.getTime() - start.getTime()) + "ms");
    }
  }
}

実行時間 12.8秒。

パターン２

Flash 10 から、Vector. を使えるようになりました。Flex SDK 3.2 から使うには、http://opensource.adobe.com/wiki/display/flexsdk/Targeting+Flash+Player+10 に従って、設定する必要があります。

変更内容は、

var ary1:Vector.<Number> = new Vector.<Number>(100 * 1024);
var ary2:Vector.<Number> = new Vector.<Number>(100 * 1024);

すると、実行時間は 11.6 秒。少し速くなりました。

パターン３

Vector. は固定長配列も作れます。

変更内容は、

var ary1:Vector.<Number> = new Vector.<Number>(100 * 1024, true);
var ary2:Vector.<Number> = new Vector.<Number>(100 * 1024, true);

すると、実行時間は、初回が 15.0秒、リロード後が 10.9 秒です。初回は常に遅く、リロード後は常に速いです。どうなっているんだ？？

パターン４

この処理、実は、ボトルネックは、for (i = 0; i < ary1.length; i++) { の部分にあります。

変更内容は、

var ary1:Array = new Array(100 * 1024);
var ary2:Array = new Array(100 * 1024);
for (i = 0; i < 100 * 1024; i++) {

実行時間は、5.7 秒です。

パターン５

Array を可変長 Vector に変えます。

変更内容は、

var ary1:Vector.<Number> = new Vector.<Number>(100 * 1024);
var ary2:Vector.<Number> = new Vector.<Number>(100 * 1024);
for (i = 0; i < 100 * 1024; i++) {

実行時間は、3.0 秒です。

パターン６

Array を固定長 Vector に変えます。

変更内容は、

var ary1:Vector.<Number> = new Vector.<Number>(100 * 1024, true);
var ary2:Vector.<Number> = new Vector.<Number>(100 * 1024, true);
for (i = 0; i < 100 * 1024; i++) {

実行時間は、初回が 5.1秒、リロード後は 3.0秒。リロード後は可変長 Vector と一緒です。

パターン７

これで終わりかと思っていたんですが、まだ、速くする方法があります。100 * 1024 ではなく、これをローカル変数に入れます。

var ary1:Array = new Array(100 * 1024);
var ary2:Array = new Array(100 * 1024);
var len:int = ary1.length;
for (var j:int = 0; j < 1000; j++) {
  for (i = 0; i < len; i++) {

実行時間は、初回が 7.2秒、リロード後は 4.7秒。なぜか初回が遅く、リロード後はパターン４より少し速くなります。

パターン８

上の可変長 Vector 版。

var ary1:Vector.<Number> = new Vector.<Number>(100 * 1024);
var ary2:Vector.<Number> = new Vector.<Number>(100 * 1024);
var len:int = ary1.length;
for (var j:int = 0; j < 1000; j++) {
  for (i = 0; i < len; i++) {

実行時間は、初回が 4.2秒、リロード後は 2.4秒。

パターン９

上の固定長 Vector 版。

var ary1:Vector.<Number> = new Vector.<Number>(100 * 1024, true);
var ary2:Vector.<Number> = new Vector.<Number>(100 * 1024, true);
var len:int = ary1.length;
for (var j:int = 0; j < 1000; j++) {
  for (i = 0; i < len; i++) {

実行時間は、初回もリロード後も 2.4秒です。僕が探した中では、これが最速でした。

Adobe Alchemy

ちなみに、C言語で書いて、Adobe Alchemy で走らせても、パターン９と同じ実行時間です。Adobe Alchemyが速い理由は、Adobe AlchemyはFlashの隠し命令を使っているみたい - yukobaのブログ。

パターン10

もしやと思い、パターン６を 100 * 1024 -> 102400 にします。

変更内容は、

var ary1:Vector.<Number> = new Vector.<Number>(102400, true);
var ary2:Vector.<Number> = new Vector.<Number>(102400, true);
for (var j:int = 0; j < 1000; j++) {
  for (i = 0; i < 102400; i++) {

実行時間は、初回が 4.3秒、リロード後は 2.6秒。100 * 1024 を 102400 に置き換えると速くなります。おわってる…

JavaScript

あまりちゃんと追っかけていませんが、

function calc1() {
  var i, j;
  var ary1 = new Array(100 * 1024);
  var ary2 = new Array(100 * 1024);
  for (i = 0; i < 100 * 1024; i++) {
    ary1[i] = i * 0.1;
    ary2[i] = i * 0.1;
  }
  
  var start = new Date();
  var sum = 0;
  for (j = 0; j < 1000; j++) {
    for (i = 0; i < 100 * 1024; i++) {
      sum += ary1[i] * ary2[i];
    }
  }
  var end = new Date();
  alert("sum = " + sum + ", time = " + (end.getTime() - start.getTime()) + "ms");
}

が、3.2秒です。var len = 100 * 1024 として、100 * 1024 を len に置き換えても、速度は、変わりません。

Visual C++ や Java

Flash 10 の約4倍速いです。http://llvm.org/devmtg/2008-08/Petersen_FlashCCompiler.pdf でも、行列の掛け算は Visual C++ と比べて 4.0 倍遅いとなっているので、そのとおりなのでしょう。

しかし、http://llvm.org/devmtg/2008-08/Petersen_FlashCCompiler.pdf では、Scimark 2 のベンチマークで、Alchemy は AS3 on AIR に比べて、25倍速いとかかれていますが、ぼくも、色々やっているうちに、これだけ速くなり、Alchemy と同じ速度で動くようになったので、差はもっともっと縮まると思います。LLVM のコンパイラはものすごく最適化をかけるので、その効果もあると思います。それに対して、ActionScript 3 の最適化は、ほとんど何も実装されていないと思われます。

GPU

ベクトルの内積や行列の掛け算は GPU を呼ぶとものすごく速く計算してくれるので、Flash 11 から GPGPU ができたら、すごく嬉しいです！

結論

Array < 可変長 Vector < 固定長 Vector の方が速いことがある。（常にではない）
ActionScript は Array.length や Vector.length が物凄く重い。JavaScript や Java はここまで重くない。
100 * 1024 のような定数は 102400 に置き換えると速くなる。（これ、コンパイラの仕事だろ！）
定数を変数に入れると速くなることがある。うーん。
Adobe Alchemy は ActionScript 3 と比べて、特段速くない可能性がある。
Flash 11では、もっとGPUを呼べるようにして欲しい！

追記１

id:moriyoshiさんにメールで、id:squldさんにコメント欄で同じことを言われたので、追記。

for (var i:int = 1000; --i >= 0; )

の方が、パターン９よりも速いのではないかという案ですが、なんと驚くことに、変わりません。例えば、i >= 5 は i - 5 >= 0 として実装されますが、どうも、i >= 0 は i - 0 >= 0 として、実装されているみたいです。

追記２

id:squld さんに昔教えてもらった、GNU Trove を好きでよく使っているのですが、Trove の TDoubleArrayList ならば、getQuick() を使えば、固定長配列と同じ速度で動くんですね。get() を使うと、17%遅くなります。