JavaScriptの結合演算の処理速度

面白そうなのでトラックバックもつけてみます。

8/1の日記の結果から、どうやら、FirefoxのJavaScriptの文字列処理は+（結合演算）に工夫があるように見えます。特に、文字列が大きくなっても結合の速度が変わりません。これは普通の感覚からするととても奇妙なことです。

なので、ちょこっと調べてみました。

普通はどうなるのか？(Java編)

普通の例、かどうかは別としてまずはJavaで文字列結合するとどうなるか見てみます。

import java.util.Date;
class JavaStr {
  static public String exec(String sum) {
    Date t1 = new Date();
    for (int i = 0; i < 10000; i ++) {
      sum += new Integer(i).toString();
    }
    Date t2 = new Date();

    System.out.println("Time:"+( (t2.getTime() - t1.getTime() )/1000.0) + "sec");
    return sum;
  }

  static public void main(String[] args) {
    String sum = "";
    sum = exec(sum);
    sum = exec(sum);
    sum = exec(sum);
    sum = exec(sum);
    sum = exec(sum);
   }
}

これを実行してみると

Time:2.801sec
Time:14.777sec
Time:35.845sec
Time:61.265sec
Time:110.305sec

なんと、220秒もかかります。
後になるほど遅くなるのはRubyと同じです。

a=a+b

という式は、適当な擬似コードで書き換えると

a=a.clone();a.append(b);

という意味になり、cloneで文字列全体をコピーして、さらにappendでバッファが足りないから文字列全体をコピーして・・・というような実装になってしまうから遅くなるんでしょう。賢いコンパイラなどはa+=bは破壊的でよいと見破ってくれると思いますが、実際どうなっているのかはやってみないと分かりません。
もっとも、他と比べてJavaが遅すぎるような気もしますが。

JavaでStringの結合をするのは有名なダメコードで、実際はStringBuffer/StringBuilderを使って書きましょうとなっています。Rubyの"<<"演算子と同じです。

import java.util.Date;
class JavaStr2 {
  static public void exec(StringBuilder sum) {
    Date t1 = new Date();
    for (int i = 0; i < 10000; i ++) {
      sum.append(new Integer(i).toString());
    }
    Date t2 = new Date();
    System.out.println("Time:"+( (t2.getTime() - t1.getTime() )/1000.0) + "sec");
  }

  static public void main(String[] args) {
    StringBuilder sum = new StringBuilder();
    exec(sum);
    exec(sum);
    exec(sum);
    exec(sum);
    exec(sum);
   }
}

appendすると破壊的になるのでコピー回数は確実に減ります。それに文字列のバッファを実際の文字列の長さよりも余分に確保するようになると速くなります。
よくあるのはバッファが足りなくなったら、一気に文字列の2倍の長さのバッファを確保する方法です。文字列はどんどん長くなるという経験に基づいたヒューリスティクスです。

実行してみると・・・

Time:0.015sec
Time:0.0060sec
Time:0.0070sec
Time:0.0030sec
Time:0.0030sec

合計0.034秒。速くなりすぎ。

JavaScriptだとどうなるのか？

単純な実装

t1=new Date().getTime(); 
sum="";
for(i=0;i<50000;i++) { sum = sum + i; }
t2=new Date().getTime();
document.write(sum);
alert(((t2-t1)/1000)+"sec")

実行すると

0.134sec

だそうです。驚異的な速さです。sum = sum + iを破壊的なメソッドに置き換えるような最適化があるのでしょうか？

強制的に非破壊的にしてみると

ということで、破壊的に出来ないように変えてみました。

t1=new Date().getTime(); 
sum=[""]; 
for(i=0;i<50000;i++) { 
  sum[i+1]=sum[i]+i+" "; 
}
t2=new Date().getTime(); 
document.write(sum[50000]); 
alert(((t2-t1)/1000)+"sec")

すべてのsum[i]を別々に保存するようにしました。これだと、破壊的に結合することは無理になります。Rubyと同じようにコピーが発生するようになるのかなぁ、って期待。

で、実行すると

0.134sec

！？　なんで変わらないのでしょう。非破壊的な演算でも速いっていうのはよく分かりません。

もっと非破壊的に

こうなると、思いつくのはJavaScriptの文字列結合が遅延評価をしているということぐらいです。どいうことかというと、結合したい文字列のそれぞれに対してCopy-on-Writeになるようにして、どちらかの文字列が変更される場合、自分自身を書き換える場合などにコピーするようにします。こうすれば結合も速いはず。
擬似コードだとこんな感じになりそうです。(擬似コードの言語は適当にごちゃ混ぜなのであしからず)

class StringAdd : extends String {
  String a;
  String b;
  bool evaluated;

  event String onChange();

  StringAdd(String a, String b) {
    //文字列の結合は遅延。参照先のバッファが変更される場合のみ
    //文字列を実際に結合。
    evaluated = false;
    this.a = a; this.b = b;
    a.onChange += toString;
    b.onChange += toString;
  }
  String toString() {
    if (!evaluated) {
      //文字列変更時に実際にバッファを確保して文字列を作成
      allocateBuffer(a.length + b.length);
      copyBuffer(from:=a, to:=this.buffer, pos:=0, length:=a.length);
      copyBuffer(from:=b, to:=this.buffer, pos:=a.length, length:=b.length);
      this.length = a.length + b.length;

      evaluated = true;
      this.onChange();
    }
    return this;
  }
}
String String::+(a, b) {
  return new StringAdd(a, b);
}
String StringAdd::=(String a) {
  //自分自身を変更することを他の人に通知
  this.onChange();
  ...
}

こんな実装をしてるのかどうか、遅延評価にとってもっとも意味のないコードを使って確かめてみます。
次のスクリプトは、文字列を結合した直後で、結合前の文字列を書き換えます。

t1=new Date().getTime(); 
sum="";
for(i=0;i<50000;i++) { 
  sum2 = sum;      //結合前の文字列を退避
  sum = sum2 + i;  //文字列を結合
  sum2 += " ";     //結合前の文字列を変更
}
t2=new Date().getTime();
document.write(sum[50000]); 
alert(((t2-t1)/1000)+"sec")

実行すると

24.427sec

予想通り時間がかかります。やっぱり、遅延評価をしてるんですね。

Ajaxなブラウザだと、中〜大サイズの文字列の変更が頻繁にありそうなので、この手の高速化をバンバンしてるんでしょう。

元々のベンチマークでのRubyの実力は文字列操作をメインターゲットの1つとしている処理系としては寂しいものがあります。concat使えって言われるんでしょうけど。