RubyとJavascript(の処理系)における文字列の連結

文字列を連結する時に言語処理系が何を行っているかという話．あんまりついていけていないのだがメモ．

発端はここ．

現代のオブジェクト指向言語の処理系で、最もパフォーマンスに影響するのはインスタンスの生成です。そのため、言語仕様として、プリミティブ型を用意することがパフォーマンス上、重要です。
(中略)
それに対して、Ruby はプリミティブ型を用意せずに、全てオブジェクトとしています。HotRuby はここの部分をインチキしました。数値と文字列に関しては、オブジェクトを作らず、プリミティブ型のままにしています。
yukobaのブログ

オブジェクトではなくプリミティブ型として実装することによってHotRubyは高速になっているらしいと言われているのだが，そこまで大きいとは思えなかった．

ベンチマークはおそらくこれ，

startTime = Time.new.to_f
  
sum = ""
50000.times{|e| sum += e.to_s}
  
endTime = Time.new.to_f
puts (endTime - startTime).to_s + ' sec'

Benchmark - HotRuby - Ruby on JavaScript & Flash

で，id:getcharさんが実験をされているのだが，

さらに、HotRubyのサイトにあるスクリプト(String#+を使う)場合に、合計50000回実行するのを10000回ごとに区切って実行時間を表示してみます。
#実行結果
0.266942024230957 sec #最初の10000回
0.818481922149658 sec #10000-20000回
1.30647802352905 sec  #20000-30000回
1.76571893692017 sec  #30000-40000回
2.35495710372925 sec  #40000-50000回
だんだんと時間がかかってきているということは、結局はString#newで他よりも大きい範囲のメモリコピーが多発してしまっている、ということのような気がします。
JavaScriptの結合演算の処理速度 - tabstop upon d.hatena

ようするにa+=bを実行する時に，a+bのサイズのメモリ領域を確保して，aとbをそこにコピーしているのでO(n)かかっているんじゃないのということらしい．

で，さらにid:Gimiteさんが連結するときに文字列のバッファの余りを使っているのではないかという予想をされている．

つまり、a.__nativeのバッファに余裕があったら、そこに詰めてしまう。ただし、個々の変数は文字列の始点と終点を保持してるので、これによってa.__nativeの内容が変わることはない、というもの。この実装ならRubyの<<版と同じで、上のベンチマークはO(N)になります。
HotRubyがC Rubyより速い本当の理由は？ - daily gimite

で，shinhさんがfirefoxのコードを見つけられたらしい．

コードの内容は文字列がmutableかどうかのフラグを持っているので，左辺がmutableかどうかを調べてmutableなら左辺が指す場所にメモリをreallocする，という内容．どうやったらmutable/immutableになるのかはがっつりコードを読まないとよくわからなそう．ちなみに文字列連結直後はmutableになっているみたい．

じゃあ，別のブラウザはどうだろうと思って，WebKitのコードを読んでみると同じようなことをやっているみたい．VMのコードから辿るとたぶんこれ．(JavaScriptCore/kjs/ustring.cpp)

UString::UString(const UString& a, const UString& b)
{
    int aSize = a.size();
    int aOffset = a.m_rep->offset;
    int bSize = b.size();
    int bOffset = b.m_rep->offset;
    int length = aSize + bSize;

    // possible cases:

    if (aSize == 0) {
        // a is empty
        m_rep = b.m_rep;
    } else if (bSize == 0) {
        // b is empty
        m_rep = a.m_rep;
    } else if (aOffset + aSize == a.usedCapacity() && aSize >= minShareSize && 4 * aSize >= bSize &&
               (-bOffset != b.usedPreCapacity() || aSize >= bSize)) {
        // - a reaches the end of its buffer so it qualifies for shared append
        // - also, it's at least a quarter the length of b - appending to a much shorter
        //   string does more harm than good
        // - however, if b qualifies for prepend and is longer than a, we'd rather prepend
        UString x(a);
        x.expandCapacity(aOffset + length);
        if (a.data() && x.data()) {
            memcpy(const_cast<UChar*>(a.data() + aSize), b.data(), bSize * sizeof(UChar));
            m_rep = Rep::create(a.m_rep, 0, length);
        } else
            m_rep = &Rep::null;
    } else if (-bOffset == b.usedPreCapacity() && bSize >= minShareSize  && 4 * bSize >= aSize) {
        // - b reaches the beginning of its buffer so it qualifies for shared prepend
        // - also, it's at least a quarter the length of a - prepending to a much shorter
        //   string does more harm than good
        UString y(b);
        y.expandPreCapacity(-bOffset + aSize);
        if (b.data() && y.data()) {
            memcpy(const_cast<UChar *>(b.data() - aSize), a.data(), aSize * sizeof(UChar));
            m_rep = Rep::create(b.m_rep, -aSize, length);
        } else
            m_rep = &Rep::null;
    } else {
        // a does not qualify for append, and b does not qualify for prepend, gotta make a whole new string
        size_t newCapacity = expandedSize(length, 0);
        UChar* d = allocChars(newCapacity);
        if (!d)
            m_rep = &Rep::null;
        else {
            memcpy(d, a.data(), aSize * sizeof(UChar));
            memcpy(d + aSize, b.data(), bSize * sizeof(UChar));
            m_rep = Rep::create(d, length);
            m_rep->capacity = newCapacity;
        }
    }
}

これを読むと，a+bを行う時にaの後ろにbをコピーするだけでなく，場合によってはbの前にaをコピーするとかやっているような気がするんだが，これまたどうやっているのかよくわからん．同じUString#appendメソッドは文字列(文字列そのものではないのだけども)の被参照数をチェックして1であれば利用していない部分を用いるかreallocするかをしていて分かりやすいのだが，コンストラクタのコードは条件が複雑なので分かりにくい．

てきとうなメモ

本の感想とか技術メモとか

RubyとJavascript(の処理系)における文字列の連結