std::stringはもっと速いはず?

http://d.hatena.ne.jp/shinichiro_h/20100823#1282563465の例は参照カウンタを活用すればstd::stringはもっと輝けるはずだ、clear();append(dir);ではなくてassign(dir);すればもっと速いんじゃないか、という実験。

パターン1

void JoinFilePathStr(string const& dir, string const& base, string* out)
    out->assign(dir);
}

void JoinFilePathSp(StringPiece const& dir, StringPiece const& base, string* out) {
    dir.CopyToString(out);
}
Str(const char*, const char*) 0.665250
Str(string, const char*) 0.236847
Str(const char*, string) 0.308445
Str(string, string) 0.011704
Sp(const char*, const char*) 0.174883
Sp(string, const char*) 0.136190
Sp(const char*, string) 0.139241
Sp(string, string) 0.109931

Str(string, string)が他とケタ違いに速い。これはOK。逆に、このパターンでstd::stringのほうが速いことで、実装が参照カウンタを使っていることも確認できます。(basic_stringのソース見たら参照カウンタを使わない条件とかあって複雑でしたので)

パターン2

void JoinFilePathStr(string const& dir, string const& base, string* out)
{
    out->assign(dir);
    out->push_back('/');
}

void JoinFilePathSp(StringPiece const& dir, StringPiece const& base, string* out) {
    dir.CopyToString(out);
    out->push_back('/');
}
Str(const char*, const char*) 0.837721
Str(string, const char*) 0.512278
Str(const char*, string) 0.499792
Str(string, string) 0.279397
Sp(const char*, const char*) 0.202806
Sp(string, const char*) 0.156834
Sp(const char*, string) 0.161091
Sp(string, string) 0.132171

1文字push_backしてるだけ。再アロケーションが必要になるのでStr(string, string)が遅くなるのはわかります。問題はSp(string, string)で、あまり変わってません。ここで逆転が発生するのはおかしい。この速度差は純粋にstd::stringのせいであってStringPieceあまり関係ないんじゃないか……。
どうやら(gcc 4.0の)basic_stringはC文字列からのassign時に余分な領域を取っているらしいです。JoinFilePathSpのほうはそれを利用しているから再アロケーションが発生していない。逆に実データが共有状態ですと、領域が仮に余っていても、常に共有解除するから遅いのではないかと。で、Str(string, string)がSp(string, string)の2倍遅いのは、共有解除とpush_backで2回コピーが起きてるのではないか?と予想できます。共有解除と連結を一気に行うようにしてしまえば、同じぐらいの速度になるはず。要するに、この例でStringPieceが速いのはStringPieceの手柄ではなくて、単にbasic_stringの実装がタコなせいではないでしょうか……。

パターン3

void JoinFilePathStr(string const& dir, string const& base, string* out)
{
    out->assign(dir);
    out->reserve(dir.size());
}

void JoinFilePathSp(StringPiece const& dir, StringPiece const& base, string* out) {
    dir.CopyToString(out);
    out->reserve(dir.size());
}
Str(const char*, const char*) 0.820524
Str(string, const char*) 0.498222
Str(const char*, string) 0.498238
Str(string, string) 0.273923
Sp(const char*, const char*) 0.185341
Sp(string, const char*) 0.156204
Sp(const char*, string) 0.147269
Sp(string, string) 0.121723

ソースを見るかぎりpush_backはreserve(size() + 1);してるだけでしたので、reserveによる共有解除だけにしてみました。
先の予想はハズレです。同じ長さへのreserveだけでも遅い。なんだこれは。長さが変わらないので純粋に共有解除だけ、つまりアロケーションとコピーが各1回必要で、CopyToStringと同じ=Sp(string, string)と同じになるはず、と信じたかったのですが……。
一方、Sp(string, string)に変化はありません。最初から共有していない状態で、長さも変わらないからreserveは何もしません。当然ですね。
というわけで予想2。reserveの実装が極端に酷い。
……ソース見てるんですが、reserve→_M_cloneと呼ばれてアロケート(_S_create)もコピー(_M_copy)も1回ずつしかやってませんね……なんでしょう??

パターン4

void JoinFilePathStr(string const& dir, string const& base, string* out)
{
    out->clear();
    out->append(dir);
}

void JoinFilePathSp(StringPiece const& dir, StringPiece const& base, string* out) {
    dir.CopyToString(out);
}
Str(const char*, const char*) 0.624683
Str(string, const char*) 0.298058
Str(const char*, string) 0.299669
Str(string, string) 0.055530
Sp(const char*, const char*) 0.178162
Sp(string, const char*) 0.135845
Sp(const char*, string) 0.138761
Sp(string, string) 0.106734

clear();append(dir);に戻してみました。これもアロケーションとコピーが1回ずつというのは同じですので、変わらないはず……と思いきやappendが速い!CopyToStringよりも速い!

謎すぎます。

ここから考えられるのは……ということで予想3。clear();は領域を開放しない。このベンチマークはjoined変数を使い回しているため、clear();append(dir);では再アロケーションが発生していない。つまりこのベンチマークは元々意味がないのでは?shinichiro.hさんごめんなさい。

パターン5

define BENCH(msg, expr) do {                                           \
        time_t start = clock();                                         \
        for (int i = 0; i < 1000000; i++) {                             \
            string joined;                                              \
            expr;                                                       \
        }                                                               \
        int elapsed = clock() - start;                                  \
        /*assert(!strcmp(joined.c_str(), "/tmp/hoge.c"));*/                 \
        printf("%s %f\n", msg, (double)elapsed / CLOCKS_PER_SEC);       \
    } while (0)

joinedをforループ内に移動して、毎回デストラクトされるように。

5-1 assign/CopyToStringのみ

Str(const char*, const char*) 0.678821
Str(string, const char*) 0.358226
Str(const char*, string) 0.359924
Str(string, string) 0.126315
Sp(const char*, const char*) 0.368007
Sp(string, const char*) 0.328823
Sp(const char*, string) 0.323669
Sp(string, string) 0.298406

5-2 push_back

Str(const char*, const char*) 1.079381
Str(string, const char*) 0.684841
Str(const char*, string) 0.679538
Str(string, string) 0.330640
Sp(const char*, const char*) 0.687556
Sp(string, const char*) 0.653732
Sp(const char*, string) 0.646298
Sp(string, string) 0.619009

5-3 reserve

Str(const char*, const char*) 1.063986
Str(string, const char*) 0.674232
Str(const char*, string) 0.663562
Str(string, string) 0.315969
Sp(const char*, const char*) 0.374639
Sp(string, const char*) 0.339220
Sp(const char*, string) 0.342732
Sp(string, string) 0.299357

5-4 clear();append(dir);

Str(const char*, const char*) 1.030788
Str(string, const char*) 0.639979
Str(const char*, string) 0.636695
Str(string, string) 0.286971
Sp(const char*, const char*) 0.367424
Sp(string, const char*) 0.329775
Sp(const char*, string) 0.324559
Sp(string, string) 0.297469

ちゃんとパスを連結するように戻すと

void JoinFilePathStr(string const& dir, string const& base, string* out)
{
    out->assign(dir);
    out->push_back('/');
    out->append(base);
}

void JoinFilePathSp(StringPiece const& dir, StringPiece const& base, string* out) {
    dir.CopyToString(out);
    out->push_back('/');
    base.AppendToString(out);
}
Str(const char*, const char*) 1.452504
Str(string, const char*) 0.998036
Str(const char*, string) 0.999712
Str(string, string) 0.642984
Sp(const char*, const char*) 0.898612
Sp(string, const char*) 0.857780
Sp(const char*, string) 0.849120
Sp(string, string) 0.825539

おお!予想通りの計測時間が出てきました!
見ての通り、いい勝負してます。

2つの引数で変換が発生するとstd::string不利ですが、これも予想通りですしね。元のshinichiro.hさんのベンチマーク程は大差がついていません。結論:暗黙の変換が発生するとしても、(仮に一時的にでも)共有状態を作り出せるならstd::stringを引数にしてOK。

ただしC++0xでは……。