同じ文字列のn回繰り返しを作る最速の方法を探求してみた

JavaScript benchmark

注意: FF3.1b2の結果が不正確です。取り直したのはこちら。

ちょっとした事情により、ある文字列のn回繰り返しを作る関数 (PHPでいうところのarray_repeat(), Perlで言うところの「"..." x n」、RubyやPythonで言うところの「"..." * n」) を高速に実装しなければならない状況に遭遇したのでベンチマークをとってみたところ、その結果がとても新鮮で驚いたので、これを共有しつつもダメ出ししてもらえないかなーと思って晒してみることに。

あらまし

JavaScriptの文字列型 (およびStringオブジェクト) はJavaのようにイミュータブルなので、こういう文字列構築を行う方法としては、以前から、+や+=演算子を用いるよりも、一旦Array()に入れておき最後にjoin()するという方法が有効だと言われていてですね、まあ確かに、文字列用メモリ領域の確保、開放を結合の度に頻繁に繰り返すよりは、最後に長さが分かっている時点でまとめて領域を確保したほうが戦略的に有効な場合が多い気がするし、と思っていたわけです。

ところが最近は、JSエンジン競争の結果、事情が変わってきているという話をちらほら耳にするようになりました。とうとうこの文字列連結にも、最適化の矢先が向けられたらしい。じゃあこれは比べてみるしかないでしょう、ということで。

ベンチマークの内容

以下のようなコードを

  • s: "0123456789"
  • n: 131071

として2回走らせたときの所要時間の相加平均を結果として比較しました。

hybridとbulkに関しては、まとめて追加する個数を16-63個の間で変えて試してみました。予想に反して (たしかに個数を増やせば増やすほど減少傾向にはあったけど) ほぼ全くといっていいほど代わり映えがしなかったので (しないように見えたので)、項目別での比較では、それぞれのベンチでの最適値を比較対象としました (ちょっとまずいかな)。

concat_op
function concat_op(s, n) {
  var r = '';
  for (var i = n; --i >= 0;) {
    r += s;
  }
  return r;
}

一番ナイーブな実装。

join
function join(s, n) {
  var r = []; for (var i = n; --i >= 0;) {
    r.push(s);
  }
  return r.join('');
}

これもまあ、ナイーブな感じの実装。まともな処理系であれば、配列にはflyweightな文字列型の値かboxedオブジェクトへの参照かどちらかが入るはずなので、メモリ消費量的にはそれほど問題にならないと予想。

hybrid
function hybrid(s, n) {
  var c = s + s + s + ... + s;
  var r = [];
  while ((n -= N) >= 0)
    r.push(c);
  n += N;
  switch (n) {
  case 1:
    r.push(s);
    break;
  ...
  case 5:
    r.push(s + s + s + s + s);
    break;
  ...
  case N-1:
    r.push(s + s + s + ... + s);
    break;
  }
  return r.join('');
}

これはあらかじめN個を連結した文字列を用意しておき、それをひたすらつなげる。最後に余った分はswitch()で分岐した先で埋め合わせる。というまあ古典的な最適化の方法だけど、よく考えたらswitch以下はr.push(c.substring(0, s.length * n));の方が短くて繰り返し回数が少ない場合は圧倒的に速い可能性があるなあと思ったり。とはいえ、今回のベンチは繰り返しが非常に多いのでそれほど問題にならないはず。

bulk
function hybrid(s, n) {
  var c = s + s + s + ... + s;
  var r = '';
  while ((n -= N) >= 0)
    r += c;
  n += N;
  switch (n) {
  case 1:
    r += s;
    break;
  ...
  case 5:
    r += s + s + s + s + s;
    break;
  ...
  case N-1:
    r += s + s + s + ... + s;
    break;
  }
  return r;
}

これは通常の文字列連結でもまとめてつなげたらいくらかましかもなーという希望的観測に基づいてhybridを変形させたもの。

結果

f:id:moriyoshi:20090126060118p:image

Chrome FF/3.0.5 FF/3.1b2 IE/6.0 IE/8.0 Opera/9.63 Safari/3.2.1 WebKit/r40220
concat_op 98 193 167.5 1230820.5 375 172 263.5 175.5
join 109.5 258 222.5 1398.5 398.5 648.5 200 82.5
hybrid 20.5 93.5 113.5 70 39 31.5 36 33
bulk 1 104.5 135 17633 23 15.5 55 54

(追記) 単位は ms です

まあグラフを見てもらえれば分かるように、

  • Chrome (V8) の速さは異常。
  • Chromeは明らかに文字列連結に最適化を行っていて、bulkでの結果が爆速。
  • Firefoxはおしなべて遅い。TraceMonkeyになっても全然変わってない。

やはりjavascript.options.jit.contentが有効になっていないというチョンボが。帰ってやり直す。

  • IE6の文字列連結の遅さは昔の言い伝えどおり (ベンチ全体で一番時間がかかったのがIE6×concat_opのところ)。
  • ところがIE6はhybridでFirefox勢に勝利するという意外過ぎる結果に。
  • IE8も文字列連結に関しては最適化を行っているのか、concat_opとjoinでは差がほとんどない。むしろconcat_opの方が速い傾向にあり、それはhybrid対bulkにも現れている。
  • Operaも文字列連結に対して最適化を行っているようで、bulkで最速となった。
  • Operaはjoin()がやたらと遅いにもかかわらず、hybridではそれなりのスピードを出している。何がボトルネックなんだろう?
  • Safariは3.2.1とnightlyで若干の差が。nightlyが少し速くなっている印象。joinに関しては有意に速くなっている印象。

なお、実験はすべてRAMを1GBに設定したVMware Server + Windows XP SP3上で行いました。初めは実機でやってたんだけど、Firefoxがよく分からない理由でメモリをあっという間に食いつぶしてしまい、スワップが始まってまったくベンチにならなかったので慌てて構成を変えてやりなおした、というわけで。

ベンチマークに使用したコードは以下。ぜひ、ご家庭で試してみてください！

追記: コードの貼り付けに失敗した。以下をコピペしてアドレスバーに張りましょう。

data:text/html;base64,PGh0bWw+CjxoZWFkPgogIDxtZXRhIGh0dHAtZXF1aXY9IkNvbnRlbnQtVHlwZSIgY29udGVudD0idGV4dC9odG1sOyBjaGFyc2V0PVVURi04IiAvPgogIDxzY3JpcHQgdHlwZT0idGV4dC9qYXZhc2NyaXB0Ij4KdmFyIF9ldmFsID0gZnVuY3Rpb24oKSB7IHdpdGgoYXJndW1lbnRzWzBdKSB7IHJldHVybiBldmFsKGFyZ3VtZW50c1sxXSk7IH0gfTsKCnZhciBwcm9jZXNzX3RlbXBsYXRlID0gZnVuY3Rpb24odHBsLCBoZGxyKSB7CiAgdmFyIHMgPSAwLCBicmFjZV9kZXB0aCA9IDAsIGFsdF9idWYgPSBudWxsOwogIHZhciBidWYgPSBbXSwgYnVmX3N0YWNrID0gW107CiAgdmFyIGlfZiA9IHsKICAgIHNhdmVfYnVmZmVyOiBmdW5jdGlvbih4KSB7IGJ1Zl9zdGFjay5wdXNoKGJ1ZiwgdHlwZW9mIHggPT0gdW5kZWZpbmVkID8gbnVsbDogeCk7IGJ1ZiA9IFtdOyB9LAogICAgZ2V0X2J1ZmZlcjogZnVuY3Rpb24oKSB7IHJldHVybiBidWY7IH0sCiAgICByZXN0b3JlX2J1ZmZlcjogZnVuY3Rpb24oKSB7IHZhciByID0gYnVmX3N0YWNrLnBvcCgpOyBidWYgPSBidWZfc3RhY2sucG9wKCk7IHJldHVybiByOyB9LAogICAgYXBwZW5kOiBmdW5jdGlvbihfYnVmKSB7IGJ1Zi5wdXNoKF9idWYuam9pbignJykpOyB9CiAgfTsKICBmb3IgKHZhciBnLCByID0gLyg/OlteJXt9XXwlKD8hWyV7XSkpK3xbe31dfCVce3wlJShbX2EtekEtWl1bX2EtekEtWjAtOS1dKikoPzpccypcKFxzKihbXildKilccypcKSk/KD86WyBcdF0qKD86XHJ8XG58XHJcbikpPy9nOwogICAgICAgKGcgPSByLmV4ZWModHBsKSk7KSB7CiAgICBzd2l0Y2ggKHMpIHsKICAgIGNhc2UgMDoKICAgICAgaWYgKGdbMF0gPT0gJyV7JykgewogICAgICAgIGJyZWFjZV9kZXB0aCA9IDA7CiAgICAgICAgYWx0X2J1ZiA9IFtdOwogICAgICAgIHMgPSAxOwogICAgICB9IGVsc2UgaWYgKGdbMF0uc3Vic3RyKDAsIDIpID09ICclJScpIHsKICAgICAgICBoZGxyLmhhbmRsZV90YWcoaV9mLCBnWzFdLCBnWzJdKTsKICAgICAgfSBlbHNlIHsKICAgICAgICBidWYucHVzaChnWzBdKTsKICAgICAgfQogICAgICBicmVhazsKICAgIGNhc2UgMToKICAgICAgaWYgKGdbMF0gPT0gJ30nKSB7CiAgICAgICAgLS1icmFjZV9kZXB0aDsKICAgICAgICBpZiAoYnJhY2VfZGVwdGggPCAwKSB7CiAgICAgICAgICBzID0gMDsKICAgICAgICAgIChmdW5jdGlvbihfKXsgYnVmLnB1c2goe3RvU3RyaW5nOiBmdW5jdGlvbigpeyByZXR1cm4gX2V2YWwoaGRsciwgXy5qb2luKCcnKSk7IH19KTsgfSkoYWx0X2J1Zik7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgIGFsdF9idWYucHVzaChnWzBdKTsKICAgICAgICB9CiAgICAgIH0gZWxzZSBpZiAoZ1swXSA9PSAneycpIHsKICAgICAgICArK2JyYWNlX2RlcHRoOwogICAgICAgIGFsdF9idWYucHVzaChnWzBdKTsKICAgICAgfSBlbHNlIGlmIChnWzBdLmNoYXJBdCgwKSA9PSAnJScpIHsKICAgICAgICB0aHJvdyB7IG1lc3NhZ2U6ICdTeW50YXggZXJyb3InIH07CiAgICAgIH0gZWxzZSB7CiAgICAgICAgYWx0X2J1Zi5wdXNoKGdbMF0pOwogICAgICB9CiAgICAgIGJyZWFrOwogICAgfQogIH0KICByZXR1cm4gYnVmLmpvaW4oJycpOwp9OwogIDwvc2NyaXB0PgogIDxzY3JpcHQgdHlwZT0idGV4dC9qYXZhc2NyaXB0LXRlbXBsYXRlIiBpZD0idGVtcGxhdGUxIj4KewogIHZhciBjID0gJXtyZXBlYXQoJ3MnLCBubikuam9pbignICsgJyl9LCByID0gW107CiAgd2hpbGUgKChuIC09ICV7bm59KSA+PSAwKQogICAgci5wdXNoKGMpOwogIG4gKz0gJXtubn07CiAgc3dpdGNoIChuKSB7CiUlcmVwZWF0KDEsIG5uIC0gMSwgaSkKICBjYXNlICV7aX06CiAgICByLnB1c2goJXtyZXBlYXQoJ3MnLCBpKS5qb2luKCcgKyAnKX0pOyAKICAgIGJyZWFrOwolJWVuZHJlcGVhdAogIH0KICByZXR1cm4gci5qb2luKCcnKTsKfQogIDwvc2NyaXB0PgogIDxzY3JpcHQgdHlwZT0idGV4dC9qYXZhc2NyaXB0LXRlbXBsYXRlIiBpZD0idGVtcGxhdGUyIj4KewogIHZhciBjID0gJXtyZXBlYXQoJ3MnLCBubikuam9pbignICsgJyl9LCByID0gJyc7CiAgd2hpbGUgKChuIC09ICV7bm59KSA+PSAwKQogICAgciArPSBjOwogIG4gKz0gJXtubn07CiAgc3dpdGNoIChuKSB7CiUlcmVwZWF0KDEsIG5uIC0gMSwgaSkKICBjYXNlICV7aX06CiAgICByICs9ICV7cmVwZWF0KCdzJywgaSkuam9pbignICsgJyl9OyAKICAgIGJyZWFrOwolJWVuZHJlcGVhdAogIH0KICByZXR1cm4gcjsKfQogIDwvc2NyaXB0PgogIDxzY3JpcHQgdHlwZT0idGV4dC9qYXZhc2NyaXB0Ij4KdmFyIHRhcmdldHMgPSBbXTsKdGFyZ2V0cy5wdXNoKHsKICBuYW1lOiAnY29uY2F0X29wJywKICBydW46IGZ1bmN0aW9uKHMsIG4pIHsKICAgIHZhciByID0gJyc7CiAgICBmb3IgKHZhciBpID0gbjsgLS1pID49IDA7KSB7CiAgICAgIHIgKz0gczsKICAgIH0KICAgIHJldHVybiByOwogIH0KfSk7Cgp0YXJnZXRzLnB1c2goewogIG5hbWU6ICdqb2luJywKICBydW46IGZ1bmN0aW9uKHMsIG4pIHsKICAgIHZhciByID0gW107IGZvciAodmFyIGkgPSBuOyAtLWkgPj0gMDspIHsKICAgICAgci5wdXNoKHMpOwogICAgfQogICAgcmV0dXJuIHIuam9pbignJyk7CiAgfQp9KTsKCnZhciBkZWZfZnVuID0gZnVuY3Rpb24odHBsLCBubikgewogIHJldHVybiBuZXcgRnVuY3Rpb24oWydzJywgJ24nXSwKICAgIHByb2Nlc3NfdGVtcGxhdGUoZG9jdW1lbnQuZ2V0RWxlbWVudEJ5SWQodHBsKS5pbm5lckhUTUwsIHsKICAgICAgbm46IG5uLAoKICAgICAgcmVwZWF0OiBmdW5jdGlvbihjLCBuKSB7CiAgICAgICAgdmFyIHJldHZhbCA9IFtdOwogICAgICAgIGZvciAodmFyIGkgPSBuOyAtLWkgPj0gMDsgKQogICAgICAgICAgcmV0dmFsLnB1c2goYyk7CiAgICAgICAgcmV0dXJuIHJldHZhbDsKICAgICAgfSwKCiAgICAgIGhhbmRsZV90YWc6IGZ1bmN0aW9uKHBhcnNlciwgbmFtZSwgYXJncykgewogICAgICAgIHN3aXRjaCAobmFtZSkgewogICAgICAgIGNhc2UgJ3JlcGVhdCc6CiAgICAgICAgICBhcmdzID0gYXJncy5zcGxpdCgvXHMqLFxzKi8pOwogICAgICAgICAgYXJnc1swXSA9IF9ldmFsKHRoaXMsIGFyZ3NbMF0pOwogICAgICAgICAgYXJnc1sxXSA9IF9ldmFsKHRoaXMsIGFyZ3NbMV0pOwogICAgICAgICAgcGFyc2VyLnNhdmVfYnVmZmVyKGFyZ3MpOwogICAgICAgICAgYnJlYWs7CiAgICAgICAgY2FzZSAnZW5kcmVwZWF0JzoKICAgICAgICAgIHZhciBidWYgPSBwYXJzZXIuZ2V0X2J1ZmZlcigpOwogICAgICAgICAgYXJncyA9IHBhcnNlci5yZXN0b3JlX2J1ZmZlcigpOwogICAgICAgICAgZm9yICh2YXIgaSA9IGFyZ3NbMF0sIGUgPSBhcmdzWzBdICsgYXJnc1sxXTsgaSA8IGU7ICsraSkgewogICAgICAgICAgICBpZiAoYXJnc1syXSkKICAgICAgICAgICAgICB0aGlzW2FyZ3NbMl1dID0gaTsKICAgICAgICAgICAgcGFyc2VyLmFwcGVuZChidWYpOwogICAgICAgICAgfQogICAgICAgICAgYnJlYWs7CiAgICAgICAgfQogICAgICB9CiAgICB9KSk7Cn0KCmZvciAodmFyIGkgPSAxNjsgaSA8IDY0OyArK2kpIHsKICB0YXJnZXRzLnB1c2goeyBuYW1lOiAnaHlicmlkJyArIGksIHJ1bjogZGVmX2Z1bigndGVtcGxhdGUxJywgaSkgfSk7Cn0KCmZvciAodmFyIGkgPSAxNjsgaSA8IDY0OyArK2kpIHsKICB0YXJnZXRzLnB1c2goeyBuYW1lOiAnYnVsaycgKyBpLCBydW46IGRlZl9mdW4oJ3RlbXBsYXRlMicsIGkpIH0pOwp9CiAgPC9zY3JpcHQ+CiAgPHN0eWxlIHR5cGU9InRleHQvY3NzIj4KdGFibGUuYm9yZGVyZWQgewogIGJvcmRlcjogMXB4IHNvbGlkIGJsYWNrOwogIGJvcmRlci1jb2xsYXBzZTogY29sbGFwc2U7Cn0KCnRhYmxlLmJvcmRlcmVkIHRkLAp0YWJsZS5ib3JkZXJlZCB0aCB7CiAgYm9yZGVyOiAxcHggc29saWQgYmxhY2s7Cn0KICA8L3N0eWxlPgo8L2hlYWQ+Cjxib2R5PgogIDx0YWJsZSBjbGFzcz0iYm9yZGVyZWQiPgogICAgPHRoZWFkPgogICAgICA8dHI+CiAgICAgICAgPHRoIHJvd3NwYW49IjIiPk5hbWU8L3RoPgogICAgICAgIDx0aD5FbGFwc2VkIHRpbWU8L3RoPgogICAgICA8L3RyPgogICAgICA8dHI+CiAgICAgICAgPHRoPjxzY3JpcHQgdHlwZT0idGV4dC9qYXZhc2NyaXB0Ij4KZG9jdW1lbnQud3JpdGUobmF2aWdhdG9yLnVzZXJBZ2VudCk7Cjwvc2NyaXB0PjwvdGg+CiAgICAgIDwvdHI+CiAgICA8L3RoZWFkPgogICAgPHRib2R5PgogIDxzY3JpcHQgdHlwZT0idGV4dC9qYXZhc2NyaXB0Ij4KICAgIHZhciBydW4gPSBmdW5jdGlvbihmKSB7CiAgICAgIHZhciBzdGFydCA9IG5ldyBEYXRlKCk7CiAgICAgIHZhciByZXN1bHQgPSBmKCcwMTIzNDU2Nzg5JywgMTMxMDcxKS5sZW5ndGggKyBmKCcwMTIzNDU2Nzg5JywgMTMxMDcxKS5sZW5ndGg7CiAgICAgIHZhciBlbmQgPSBuZXcgRGF0ZSgpOwogICAgICByZXR1cm4gcmVzdWx0ID09IDEzMTA3MSAqIDEwICogMiA/IChlbmQuZ2V0VGltZSgpIC0gc3RhcnQuZ2V0VGltZSgpKSAvIDI6IG51bGw7CiAgICB9OwogICAgZm9yICh2YXIgaSBpbiB0YXJnZXRzKSB7CiAgICAgIHZhciByZXN1bHQgPSBydW4odGFyZ2V0c1tpXS5ydW4pCiAgICAgIGRvY3VtZW50LndyaXRlKCc8dHI+PHRkPicpOwogICAgICBkb2N1bWVudC53cml0ZSh0YXJnZXRzW2ldLm5hbWUpOwogICAgICBkb2N1bWVudC53cml0ZSgnPC90ZD48dGQ+Jyk7CiAgICAgIGRvY3VtZW50LndyaXRlKHJlc3VsdCAhPSBudWxsID8gcmVzdWx0ICsgIm1zIjogJ2Vycm9yJyk7CiAgICAgIGRvY3VtZW50LndyaXRlKCc8L3RkPjwvdHI+Jyk7CiAgICB9CiAgPC9zY3JpcHQ+CiAgICA8L3Rib2R5PgogIDwvdGFibGU+CjwvYm9keT4KPC9odG1sPgo=