JavaScript のパフォーマンスと Sweet Spot の甘い罠

本文

先日 JavaScript を高速化するには、 VM を知る必要があるんだろうと思い、
以下のような発言をしてみました。

とにかく今は 「V8の最適化の恩恵を受けるための JS の書き方」や「ホットスポットを温めて C よりも速い JS を書こう」という釣りっぽいけど釣りじゃない記事を @Constellation さんや @bad_at_math さんに書いていただく必要があるということでした！

2011-10-23 21:53:44 via Echofon

しかし、釣り針が小さかったためか、誰も釣れず。。
自分で調べろってことですよね、すいません。。

と思っていたら、先日下記のエントリが話題になりました。
そのものずばり、JavaScript を最適化する話。

mraleph-The trap of the performance sweet spot

先に感想を言うと、これはいろんな意味で、JavaScript だけでなく、 VM で動く他の言語においてとても重要になる考え方だと思いました。
最適化の方法の考え方、という意味では有りません。多分重要なのは後半だと思います。
(まあ書いてあること自体は、当たり前と言えば当たり前なんですが)

これはじっくり読まないとと思って読んだので、公開します。
もとがメモなので、「直訳では無い」ことにご注意ください。

また、今回の訳はちょっと急ぎぎみでやったので、決して良いものではないです。
しかし、要点はきちんと押さえて訳したつもりです。
間違っていれば、指摘頂けると幸いです。

ソースとイメージはオリジナルから引用しました。
引用というにはちょっと多いと感じたので、オリジナルの著者に @mraleph 氏に連絡はしています。
ロシアのコンパイラエンジニアのようです。さすがだなぁ。

C プログラマが JavaScript を書いたら。という話

JavaScript のパフォーマンスについて話す。でもまずはCの話。
番号付きの２次元座標の配列から、偶数番号のもののみ取り出し、ベクトルの和を計算する関数を作成する。

typedef struct {
  int32_t n;
  double x;
  double y;
} Point;

Point arrayofpoints_sum(Point* points, size_t n) {
  Point sum = { 0, 0, 0 };

  for (size_t i = 0; i < n; i++) {
    if ((points[i].n & 1) == 0) {
      sum.x += points[i].x;
      sum.y += points[i].y;
    }
  }

  return sum;
}

ついでにベンチマークを。

Point* arrayofpoints_create(size_t n) {
  Point* points = (Point*) malloc(n * sizeof(Point));
  for (size_t i = 0; i < n; i++) {
    points[i].n = i;
    points[i].x = i * 0.1 + 0.1;
    points[i].y = i * 0.9 - 0.1;
  }
  return points;
}

void arrayofpoints_free(Point* array) {
  free(array);
}

static uint64_t now() {
  struct timeval t;
  gettimeofday(&t, NULL);
  return ((uint64_t) t.tv_sec) * 1000000 + (uint64_t) t.tv_usec;
}

void test_arrayofpoints() {
  static const size_t kArraySize = 10000;
  static const size_t kIterations = 10000;

  uint64_t create_total = 0;
  uint64_t sum_total = 0;

  for (size_t i = 0; i < kIterations; i++) {
    uint64_t t1 = now();
    Point* array = arrayofpoints_create(kArraySize);
    uint64_t t2 = now();
    Point sum = arrayofpoints_sum(array, kArraySize);
    uint64_t t3 = now();
    assert((int)sum.x == 2500000);
    assert((int)sum.y == 22495000);
    assert(sum.n == 0);
    arrayofpoints_free(array);

    create_total += (t2 - t1);
    sum_total += (t3 - t2);
  }

  printf("create: %lld [%.2f per iteration] usec, sum: %lld [%.2f per iteration] usec\n",
         create_total, (double)create_total / kIterations,
         sum_total, (double)sum_total / kIterations);
}

int main(int argc, char* argv[]) {
  test_arrayofpoints();
  return 0;
}

実行結果。

% gcc --std=c99 -O3 -o point point.c
% ./point
create: 508075 [50.81 per iteration] usec, sum: 214779 [21.48 per iteration] usec

このコードを JavaScript で書いてみる。
最近の JavaScript は速いはず。

function Point(n, x, y) {
    this.n = n;
    this.x = x;
    this.y = y;
}

function sumArrayOfPoints(points) {
    var sum = new Point(0, 0, 0);

    for (var i = 0; i < points.length; i++) {
        if ((points[i].n & 1) === 0) {
            sum.x += points[i].x;
            sum.y += points[i].y;
        }
    }

    return sum;
}

function createArrayOfPoints(n) {
    var points = new Array(n);
    for (var i = 0; i < n; i++) {
        points[i] = new Point(/* n */ i, /* x */ i * 0.1 + 0.1, /* y */ i * 0.9 - 0.1);
    }
    return points;
}

function now() {
    return Date.now() * 1000;
}

function assertStrictlyEqual(expected, value) {
  if (expected !== value) {
    throw new Error("Assertion failed: expected " + expected + " got " + value);
  }
}

function testArrayOfPoints() {
    var kArraySize = 10000;
    var kIterations = 10000;

    var createTotal = 0;
    var sumTotal = 0;

    for (var i = 0; i < kIterations; i++) {
        var t1 = now();
        var array = createArrayOfPoints(kArraySize);
        var t2 = now();
        var sum = sumArrayOfPoints(array);
        var t3 = now();
        assertStrictlyEqual(2500000, sum.x | 0);
        assertStrictlyEqual(22495000, sum.y | 0);
        assertStrictlyEqual(0, sum.n);

        createTotal += (t2 - t1);
        sumTotal += (t3 - t2);
    }

    console.log("create: " + createTotal + " [" + (createTotal / kIterations) + " per iteration] usec," +
                " sum: " + sumTotal + " [" + (sumTotal / kIterations) + " per iteration] usec\n");
}

testArrayOfPoints();

簡単だけど、思ったほどのパフォーマンスはでない。

% ~/src/v8/d8 point1.js
create: 4629000 [462.9 per iteration] usec, sum: 2056000 [205.6 per iteration] usec

V8 でも C の約 10 倍ほど遅い。

Cが石なら、JavaScriptは霧

C はポータブルなアセンブリと呼ばれるほど低水準な言語だ。
Point は 24byte のメモリを確保して、そこがuint32_tと２つのdoubleを持つと定義したことになる。

n と x の間の小さな領域はx,yを整列させるために使われる。そのほうが CPU に都合がいい。
アーキテクチャによっては整列されてないdoubleを直接レジスタに読もうとすると、エラーになるものもある。

Cの配列は、より大きな領域にPointが順番に敷き詰められている形になる。

しかし、JavaScriptではそうはいかない。フラットなメモリを確保して、そこを Point だと宣言することができない。
そのかわり、オブジェクトという非常にフレキシブルなものを手に入れることができる。
オブジェクトは、(ほぼ)自由に変化させられるプロパティというものを持つ。

コンストラクタは以下のようになる。

function Point(n, x, y) { /* ... */ }

しかし、実際は Point インスタンスを生成後に、その変更を阻止するものはなにもない。
JavaScriptを実行するVMはどんな変更(プロパティの追加、削除、プロパティディスクリプタの変更)も受け入れられるようになっている。
この柔軟性によって、Pointオブジェクトを24バイトにまとめて格納しておくことができない。
実際は以下のような感じになる。(V8を使った例)

V8は、本当はオブジェクトをより構造体に近い形にしようとしている。
これは、コンストラクタを解析して、プロパティのために、オブジェクトにどのくらいのスペースを事前に確保しておくべきか、を読み取る試みである。
VMによっては、固定値の使用や、すべてのプロパティをオブジェクトと切り離して別途配列に格納することもある。
また、V8は常に number が 31bit integer(x64 では 32bit) でない場合 box することがわかる。
他にも、いくつかの(SpriderMonkey や JavaScriptCといった)VMは double を box する代わりに NaN-tagging を使う。

にもかかわらず、 Point オブジェクトは x64 v8 の場合、 C の 3.3 倍の大きさになる。
そして、継続的にメモリに割り当てられる。(double は間接的にアクセスされる。)
また3つの追加フィールドとして、 オブジェクトのレイアウトを表現する hidden class (V8 での Map, SpiderMonkey での Shape, JavaScriptCore での Structure) へのポインタ、
外部オブジェクトのプロパティ用の補助記憶へのポインタ、エレメントの補助記憶へのポインタをもつ。

オブジェクトの生成後も柔軟な変更に対処するため、全てのフィールドは必須。

Point オブジェクトの配列も基本的に同じ構造。

JavaScript では配列もオブジェクトなので、同様に hidden class を持つ。
プロパティの補助記憶へのポインタと、エレメントの補助記憶へのポインタだ。

補助記憶は異なる表現をもつことができる。

例えば、 VM は通常、sparse(nullを含む, 穴のあいた)配列を辞書形式で表現し、non-sparse(nullを含まない)配列をフラットに補助記憶に格納する。
プログラムでは、 points の配列は常に non-sparse で、補助記憶にフラットに格納される。

パフォーマンスの仕組みはシンプルだ。

各 Point の柔軟性と、内部での参照(図の中の矢印) は処理コストがかかる。

points[i].x といった単純に見える参照も実際は「Point は何で、どうプロパティ i を探し、そこらいかに x が取り出せるのか？」
という難問である。

静的解析で完全にこれらの問を解決するにはコストがかかり過ぎる。

モダンな JIT では inline cache や compilation pipelines を適応することで減らしてる。

簡単に言えば、JavaScript は 「points は Point オブジェクトの配列である」、ということを形宣言などを通して JIT にこっそり教える方法を持たない。

だから良いパフォーマンスを得るためには、JIT に色々気づかせるために大声を張り上げないといけない。

要するに、オブジェクトは静的な構造を持ち

プロパティアクセスは単一系であり

言語の変な機能(withやeval)は使わず

適切に普通の配列と typed array を使い分ける。

ある意味では、静的型付けでない言語で静的に型を指定したプログラムを書くようなものである。

前述のコードも十分静的型付けっぽく書いてあるけど、まだ C の10倍遅い。これはまだ速くなる。

しかし、これ以上速くするには JavaScript を C のコンパイラで生成されたアセンブリのように書かないといけない。

手始めに生のメモリを JavaScript からいじるために、WebGLのtyped arrayを使う。

JITが読み込み/書き込みを徹底的に最適化するのは難しくない。そのためのセマンティクスが補助記憶にはあるからだ。

全てのプロパティがプリミティブ値で boxing を不要にすることで、プロトタイプの参照は無くす。

var blocks = [];

function Block(size) {
  this.size = size;
  this.buf = new ArrayBuffer(this.size);
  this.i32 = new Int32Array(this.buf);
  this.f64 = new Float64Array(this.buf);
}

function malloc(N) {
  if (blocks[N] && blocks[N].length) return blocks[N].pop();
  return new Block(N);
}

function free(addr) {
  (blocks[addr.size] || (blocks[addr.size] = [])).push(addr);
}

malloc&free を素直に実装するとこうなる。メモリの最適化を一切行わないが、デモには最適だ。

var $stack = malloc(8 * 1024);
var $sp = 0;

オリジナルの C は加算結果をスタックで返すので、それを再現する疑似スタックを作る。

function createArrayOfPoints(n) {
   var points = malloc(24 * n);
   var points_i32 = points.i32;
   var points_f64 = points.f64;
   for (var i1 = 0, i2 = 1, i = 0; i < n; i++, i1 += 6, i2 += 3) {
       points_i32[i1]     = /* n */ i;
       points_f64[i2]     = /* x */ i * 0.1 + 0.1;
       points_f64[i2 + 1] = /* y */ i * 0.9 - 0.1;
   }
   return points;
}

points 配列の生成はシンプルで、array を malloc して埋めるだけだ。

これは読みにくくて、最初の JavaScript のコードや元の C のコードと比べてどう対応しているのかわかりにくい。

それは C コンパイラがやるような最適化を自分でやっているからだ。"強さの低減"(strength reduction) だ。

(byte*)points + sizeof(Point) * i としての points[i] の計算は重たい。なぜなら乗算は加算にくらべてコストが高いからだ。
そこで良い C コンパイラは points[i] を作為的に用意した p' = points[i] で始まる p' に置き換え、進めるときは p += sizeof(Point) を行う。

function sumArrayOfPoints(points, n) {
   var x = 0;
   var y = 0;

   var points_i32 = points.i32;
   var points_f64 = points.f64;
   for (var i1 = 0, i2 = 1, k = 6 * n; i1 < k; i1 = i1 + 6, i2 = i2 + 3) {
       if ((points_i32[i1] & 1) === 0) {
           x += points_f64[i2];
           y += points_f64[i2 + 1];
       }
   }

   // Caller should have reserved space for the return value.
   var retval_addr = $sp - 24;
   $stack.i32[retval_addr >> 2] = 0;
   $stack.f64[(retval_addr + 8) >> 3] = x;
   $stack.f64[(retval_addr + 16) >> 3] = y;
   return retval_addr;
}

加算ループは createArrayOfPoints によって C と同様、初期化ループに置き換えられた。

しかし、他にも重要な最適化が有る。それが スカラー変換だ。

コンパイラは Point の和がスタック上に存在し続ける必要が無いことに気づく。

代わりに、それは発散し、フィールドの値は分散する可能性がある。(register allocator が後でそれを register にのせる)

sumArrayOfPoints の結果は、元の C と同じように stack に乗る。

コードの土台は変わってないが、 testArrayOfPoints には多少の修正が必要だ。

  var t1 = now();
  var array = createArrayOfPoints(kArraySize);
  var t2 = now();
  $sp += 24;  // Reserve space for return value on the "stack".
  sumArrayOfPoints(array, kArraySize);
  $sp -= 24;
  var sum_n = $stack.i32[$sp >> 2];
  var sum_x = $stack.f64[($sp + 8) >> 3];
  var sum_y = $stack.f64[($sp + 16) >> 3];
  var t3 = now();
  assertStrictlyEqual(2500000, sum_x | 0);
  assertStrictlyEqual(22495000, sum_y | 0);
  assertStrictlyEqual(0, sum_n);
  free(array);

スタック領域のオブジェクトの割当と解放には注意しないとならない
結果として JavaScript をアセンブリとして扱っているわけだ。。

% ~/src/v8/d8 point.c.js
create: 532000 [53.2 per iteration] usec, sum: 988000 [98.8 per iteration] usec

こうして全く読むに耐えない JavaScript が手に入り、オブジェクト生成は9倍、 加算は2倍にスピードアップした。

V8 が生成した加算ループのコードを注意深く見て、 GCC が生成する C のコードと比べれば、

V8 が i32 と f64 を厳密に理解していないために、二つが同じ配列で別々に扱うことがわかる。

C にはない割当のチェックもある。

Sweet Spot に魅せられてはいけない。

おおよそ一週間前に、友人がものすごく興奮した様子で Broadway.js のリンクを送ってきた。

彼は何も考えず罠にはまったのだ。

パフォーマンスが良い、(最適化のかかった C のように)およそ人間には読めないコードは

「JavaScript はまだまだ遅い」ので、Web アプリを C で書こうとでもするか、

もしくは先のような、およそ読めないコードで書くしかないことを証明している。

かわりに、「JavaScript の本来の機能を、本来の用途で使う分には、十分な速度が出る」ことを意味している。

カーネルレベルの計算効率化の考え方は、常に他のレイヤに持ち込めばいいというものではない。これを私は "sweet spot の罠" と呼びたいと思う。

より速く、より速くと求めた結果それは JavaScript ではない。これが JavaScript の sweet spot だ。

そんなことを疑いもせず、 sweet spot を叩くこともできる。

しかし、いくつかのルールに従う必要がある。

これらのルールは厳格(実際はアプリケーションが、振る舞いにおいて非常に静的であることがベストだ) かつ不明だ(VM によって違う指向により成り立ってる)

そして、一番の sweet spot は、前述したような奇妙な最適化技術を必要とする。

JavaScript の性能向上は明らかにまだまだ続く。

そして、言語自身もバイナリ対応といった sweet spot をより簡単に叩くための機能を備えつつある。

しかし、言語のなにもかもが sweet spot だらけになるとは思わない。

現実世界のパフォーマンスは、簡単なベンチマークで測れるほど簡単ではない。

最終的には "speed", "memory", "VM complexity" の3つの重要な要素がある。

既存の JavaScript VM をみると、多くの時間を、非効率な実行やメモリ利用のために使っていることがわかる。

そして実装の複雑さは、複雑さの中でも最も悪な部類だ。

ほんの少しの確率ではあるが、絶妙なバグを仕込みうる。

パフォーマンスを測定しづらくしてしまう。

コンパイラをなだめるための複雑なルールを増やしてしまう。

JavaScript は複雑で高度なコアを持つ言語だ。

それを忘れず、決して sweet spot に惑わされてはいけない。

だたし付け足しておくと、 JavaScript VM の中に sweet spot を増やし、かつ簡単にそれらを叩けるようにする試みは、面白いと思う。

そんなことしたら頭がいかれてしまうかもしれないけどね。 :-)