node.js/v8のgeneratorsのパフォーマンスについてちょっと調べた

  • 投稿日:
  • by

初めに断っておきますが、今回の調査は、node v0.11.5 (Linux)で試したもので、他の環境では異なるかもしれません。さらに、今後のバージョンアップによっては全く異なる結果となることも十分ありえます。ご注意を。

ES6にgeneratorsが入るとのことで、JavaScriptでcontinuationが使えないかなぁと思っていた自分としては、興味を持ちました。

ちなみに、generator, coroutine, continuationの順に記述力が上がるそうです。こちらが参考になるかもしれません。

さて、generatorsの説明は他に任せるとして、いきなりコードです。

function* es6_generator() {
  yield 1;
  yield 2;
  yield 3;
  yield 4;
  return 5;
}

これを複数回実行して時間を計測するコードはこちら。

console.time('es6_generator');
for (i = 0; i < 1000000; i++) {
  iterator = es6_generator();
  obj = {};
  while (!obj.done) {
    obj = iterator.next();
  }
}
console.timeEnd('es6_generator');

実行結果は、

es6_generator: 360ms

でした。うちのマシンは非力なので、最近のマシンならもっと速いかもしれません。

これと同等のコードをgeneratorsを使わずに書くとどうなるでしょうか。おそらく、

function hand_generator1() {
  var iterator = {};
  iterator.next = function() {
    iterator.next = function() {
      iterator.next = function() {
        iterator.next = function() {
          iterator.next = function() {
            return {value: 5, done: true};
          };
          return {value: 4, done: false};
        };
        return {value: 3, done: false};
      };
      return {value: 2, done: false};
    };
    return {value: 1, done: false};
  };
  return iterator;
}

こんな感じになるのでしょう。 これを同じように実行したら、

hand_generator1: 4529ms

となりました。これが等価なコードなのかは問題ですが、 少なくともhand_generator1のように書くよりは、 es6_generatorの方が速いとうことですね。

しかし、この単純な例だとfunctionをイテレーション毎に生成する必要はなくて、もっと効率的に書けます。

function hand_generator2() {
  var array = [1, 2, 3, 4, 5];
  var index = 0;
  var iterator = {
    next: function() {
      return {value: array[index++], done: array.length <= index};
    }
  };
  return iterator;
}

この場合の実行結果は、

hand_generator2: 265ms

となりました。es6_generatorと比べてどちらが読みやすいと思うかは人次第でしょうか。できることが違うので比較の対象にならないですが。

さて、少し話がややこしくなりますが、もともとは末尾再帰をやりたかったのです。末尾再帰の説明は他に任せるとして、factorialをgeneratorsを使って書いてみました。

function fact_tail_loop1(x) {
  var fact_tail_sub = function* (x, r) {
    if (x === 0) {
      return r;
    } else {
      yield fact_tail_sub(x - 1, x * r);
    }
  };
  var c = fact_tail_sub(x, 1);
  var d = {};
  while (!d.done) {
    d = c.next();
    c = d.value;
  }
  return d.value;
}

これを見て、ふーん、とか、おー、とか思わない場合は、この先を読んでもつまらないかもしれません。

実行コードはこちら。

console.time('fact_tail_loop1');
console.log(fact_tail_loop1(3));
console.log(fact_tail_loop1(5));
console.log(fact_tail_loop1(10));
console.log(fact_tail_loop1(100));
console.log(fact_tail_loop1(1000));
console.log(fact_tail_loop1(10000));
console.log(fact_tail_loop1(100000));
console.log(fact_tail_loop1(1000000));
console.timeEnd('fact_tail_loop1');

実行すると次のようになりました。

6
120
3628800
9.332621544394418e+157
Infinity
Infinity
Infinity
Infinity
fact_tail_loop1: 217ms

Infinityになってますが、ちゃんと計算はしているようです。ちなみに普通の再帰やproperでない末尾再帰の場合は、最後の方は計算できずにエラーになります。

さて、generatorsを使わないで書き直してみました。

function fact_tail_loop2(x) {
  var fact_tail_sub = function(x, r) {
    return {
      next: function() {
        if (x === 0) {
          return {
            value: r,
            done: true
          };
        } else {
          return {
            value: fact_tail_sub(x - 1, x * r),
            done: false
          };
        }
      }
    };
  };
  var c = fact_tail_sub(x, 1);
  var d = {};
  while (!d.done) {
    d = c.next();
    c = d.value;
  }
  return d.value;
}

同じように実行すると、

6
120
3628800
9.332621544394418e+157
Infinity
Infinity
Infinity
Infinity
fact_tail_loop2: 796ms

になりました。しかし、このコードはオブジェクトの生成が多すぎます。改良版はこちら。

var LoopCont = function(f) {
  this.f = f;
};

function fact_tail_loop3(x) {
  var fact_tail_sub = function(x, r) {
    if (x === 0) {
      return r;
    } else {
      return new LoopCont(function() {
        return fact_tail_sub(x - 1, x * r);
      });
    }
  };
  var c = fact_tail_sub(x, 1);
  while (c instanceof LoopCont) {
    c = c.f();
  }
  return c;
}

これを実行すると、

6
120
3628800
9.332621544394418e+157
Infinity
Infinity
Infinity
Infinity
fact_tail_loop3: 63ms

となりました。いかがでしょう。

私見ですが、generatorsのパフォーマンスは状況次第といったところでしょうか。v8の最適化が進めば、様々なケースで改善されるかと思われます。

しかし、generatorsを使って末尾再帰やcontinuationを実装できないかなぁ、と期待したのでちょっと残念でした。やっぱり言語レベルでサポートしてほしいですね。

個人的には、yield expressionは構造が分かりにくく感じ、好きになれそうにないので、直接使うことはないかと思います。うまく隠蔽してくれるライブラリがあればいいのかもしれません。

ここまで読んでくれた方は、 https://github.com/dai-shi/continuation.js にも興味を持っていただける可能性がありますので、 よろしければご覧ください。