String repeat のアルゴリズムとパフォーマンス

JavaScript

ES6になると、String.prototype.repeatのメソッドが追加されるわけだが、そのアルゴリズムとパフォーマンスを追ってみている。

ES6 String.prototype.repeat の仕様では以下の様な感じでシンプルな書き方をしている。

  • countが 0 より小さい、または 無限大である場合は RangeError
  • count 0 ならば、空文字列
  • そうでない場合は、count回、文字列を繰り返して連結する

単純に実装すれば、以下の様な感じで済む。

String.prototype.repeat = function (count) {
  if (count < 0 || !Number.isFinite(count))
    throw new RangeError();
  var result = "",
      str = this;
  for (var i = 0; i < count; ++i) {
    result += str;
  }
  return result;
};

他にも配列を作ってjoinする方法も考えつく

String.prototype.repeat = function (count) {
  var arr = new Array(count),
      str = this;
  for (var i = 0; i < count; ++i) {
    arr[i] = str;
  }
  return arr.join("");
};

String.prototype.repeat = function (count) {
  return (new Array(count + 1)).join(this);
}

しかし、これらは結局、count回繰り返す処理であり、ループ数が線形的に増加し非効率である。
スピードを求めるならループ数の一次的増加は悪である。

もう少し工夫をしよう。

Firefox(SpiderMonkey)の初期実装

細かいチェックを省くと概ね以下の様な実装であった

String.prototype.repeat = function (count) {
  if (count === 0)
    return "";
  var str = this,
      result = str;
  for (var i = 1; i <= count / 2; i *= 2) {
    result += result;
  }
  for (; i < count; i++) {
    result += str;
  }
  return result;
};
  • 2, 4, 8 ... と 2のべき乗で収まる範囲の回数までは、結果となる値自身を積み上げていく
    • 512回なら 9回のループ、1024回なら10回のループで済む
  • あまりは、単純ループで追加していく

というアルゴリズムであった。

最初のループでは高速道路に乗った気分で気持よく進み、256, 512, 1024 などの綺麗な数値だと速攻で処理される。しかし、1023回などになると、512回までは気持ちよく進んだ後に2番めのループで511回もループするはめになってスピードが極度に下がってしまう。

修正された実装

落差の激しいアルゴリズムだった実装が次の変更で改善される

String.prototype.repeat = function (count) {
  var result = "",
      str = this;
  for (;;) {
    if (count & 1) {
      result += str;
    }
    count >>= 1;
    if (count) {
      str += str;
    } else {
      break;
    }
  }
  return result;
};

わけがわからない…
が、ビット演算をしているので2進数で考えてみたらなんとなく見えてきた。

13回ほどのリピートを考えてみる。13は 1101(2) である。ビットが立っているところでstr += strで積み上げた文字列をresultに追加して行こうという処理である。
結果、ループ数は2進数の桁分で済む。
すばらしい…、自分のような凡俗にはとても思いつかないアルゴリズムだ。感動した。

一方、Chrome(V8)の実装

そうなると、V8エンジンでの実装が気になり始める。もっと凄いことをしているのでは！？

String.prototype.repeat = function (count) {
  var elements = new Array(count),
      str = this;
  for (var i = 0; i < count; i++) {
    elements[i] = str;
  }
  return elements.join("")
};

なんか…とても残念でした。
次に期待することにしましょう。

パフォーマンス

そんなこんなを思いながら、書いてみた jsperf

いろいろ試行錯誤していたので、綺麗なグラフではないけど、String.prototype.repeatにおけるFirefox(SpiderMonkey)の優秀さ/Chrome(V8)の残念さ、1024リピートという綺麗な数値での爆速さがうかがい知れる感じで面白いと思う。