文字列処理の性能に関する考察
たいへん興味深い結果。いろいろ気になったので、もう少し突っ込んで実験してみました。
実験
1Mバイトの文字列で2通り試してみました。(単位はミリ秒)
| (A)1000文字ごとに改行 | (B)1文字ごとに改行 | |
|---|---|---|
| charAt | 2167 | 2195 |
| Array | 1648 (469) | 1674 (453) |
| split | 5 | 530 |
| match | 14 | 781 |
| match (sentinel) | 16 | 777 |
| indexOf | 3 | 979 |
| replace | 15 | 327 |
- Arrayの括弧内の数値は、split後のループの時間のみを計測したもの
- 実行環境は spidermonkey 1.6
考察
個々の性能は、対象となる文字列によって変わってきます。
indexOf
改行が非常に多い場合(B)は、indexOfを使った実装の性能がガクッと下がります。
これは考えてみれば当たり前で、改行の数だけループが回り、indexOfメソッドが呼び出されることになるからです。
while ((i = s.indexOf("\n", i + 1)) >= 0)
しかし改行がそれほど多くない場合(A)は、外側のループ回数も少なく、余計なオブジェクトを生成しないため非常に高速です。
ループ
次に charAt と Array に注目してみます。
どちらも遅いですが、Arrayの方は前処理として split による文字列の変換を行っており、実はここがボトルネックになっています。
純粋に for ループの中身だけを比べた場合、Arrayの方がずっと速いです。
これは charAt がメソッド呼び出しであるのに対し、配列の[ ]は組み込みの演算だからです。昔ほど気にしなくてよくなったとはいえ、メソッド呼び出しはやっぱ重いんですよね。
これら自前でループを書く方法が、文字列オブジェクトに対するメソッド呼び出し一発で処理を行うという方法に比べて遅いのは、文字列へのメソッド呼び出しはネイティブコードで処理されるからだと思います。特にJavaScriptでのループとネイティブコードでのループでは有意な差が出そうです。
split
split はおそらく個々の部分文字列を新たに生成したりはしません。 JavaScriptの文字列は immutable なので、部分文字列を切り取る場合には元の文字列を表すバイト列と領域をシェアできるからです。つまり余計なコピーが発生せず、substr処理は定数時間でできるし領域量の心配も無用です。新たに生成されるオブジェクトは部分文字列への参照を持った配列のみです。
match
やってることは split と同じような感じなので、計算時間も split と同じように変化します。
replace と split
改行が非常に多い場合(B) に最も性能が良いのが replace でした。
これも走査自体は split や match と同じように行われますが、処理の結果生成されるオブジェクトが違います。split との差は、この新たに生成するオブジェクトの違いに依存しそうです。
(B)のケースでは
- splitは「文字列への参照を n 個持つ配列」を作る
- replace は「長さ n の文字列」を作る
後者の方が生成コストが低く、それが性能に反映されたのだと思います。
まとめ
- JavaScriptのループ + 関数呼び出しは重い。
- splitなどStringのメソッドでは、ループする部分がネイティブコードに落ちるので速い。
- immutableな文字列は部分文字列の切り出しが速い。
- 「関数呼び出しの結果生成されるオブジェクト」を考える。大きなオブジェクトを無駄に生成してしまう処理は避ける。
最後はまぁお約束ですが、速すぎる早すぎる最適化はやめましょうとか、プロファイラ使えとか。読みやすいコードを保つというのが第一ですね。
