for in [] の内包に変数を含む場合の簡単な高速化

"Breaking the JavaScript Speed Limit with V8"というGoogle I/O 2012でのプレゼンテーションを知りました。以下、ポイントの要約です。

インスタンスプロパティはすべてコンストラクタ内で一定順に初期化する

V8は実行時に新しいプロパティへの代入文が実行される度に隠されたクラスを生成します。代入文の実行順序が違えば異なる隠されたクラスに属します。これがパフォーマンスの劣化を招くので、プロパティはすべてコンストラクタ内で一定順で初期化しましょう。

浮動小数点数の配列に他のオブジェクトを混ぜない

V8では、浮動小数点数の配列は、unboxされるので高速になります。

多相より単相

引数の型が変わらないと高速化します。

最適化したくてかつ例外が発生するような処理は処理を関数化し、関数コールの外側で例外処理する。

例外処理のブロックは最適化(インライン化)の適用外なので、ブロック内の処理を関数化して最適化対象にしましょう。
他にも適用外となる場合があるので、--trace-bailoutオプションで見つけましょう。

さて、本題ですが、同じ課題をCoffeeScriptでやってみました。

sys = require('sys')

class Primes
  constructor : ->
    @prime_count = 0
    @primes = new Array(25000)

  getPrimeCount : -> @prime_count
  getPrime : (i) -> @primes[i]
  addPrime : (i) ->
    @primes[@prime_count++] = i

  isPrimeDivisible : (candidate) ->
    for i in [1 ... @prime_count]
      return true if (candidate % @primes[i]) == 0 
    false

# main
p = new Primes()
c = 1
while (p.getPrimeCount() < 25000)
  p.addPrime(c) if not p.isPrimeDivisible(c)
  c++
sys.print p.getPrime(p.getPrimeCount() - 1)

バグフィックス後のオリジナルのJavaScriptと比較して倍以上かかりました。えーっと思って、翻訳されたコードを見ると、以下のように素数チェックのループがひどいことになっていました。ループ１回の度にインデックスが上りか下りか確認してそれぞれの条件と次のインデックスの計算をしています。

    Primes.prototype.isPrimeDivisible = function(candidate) {
      var i, _i, _ref;
      for (i = _i = 1, _ref = this.prime_count; 1 <= _ref ? _i < _ref : _i > _ref; i = 1 <= _ref ? ++_i : --_i) {
        if ((candidate % this.primes[i]) === 0) {
          return true;
        }
      }
      return false;
    };

どうしたらいいか、メーリングリストで聞いてみたところ、簡単なwork aroundを教えていただきました。for inで増分を明示的に指定します。

  isPrimeDivisible : (candidate) ->
    for i in [1 ... @prime_count] by 1
      return true if (candidate % @primes[i]) == 0 
    false

    Primes.prototype.isPrimeDivisible = function(candidate) {
      var i, _i, _ref;
      for (i = _i = 1, _ref = this.prime_count; _i < _ref; i = _i += 1) {
        if ((candidate % this.primes[i]) === 0) {
          return true;
        }
      }
      return false;
    };

オリジナルと遜色ない結果になって満足です。