Note

サイト
最近のコメント
 | 

2011-11-21 週末は雨だった

[] Delphi文字列並の効率を実現できるようにUnbounded_Stringを改造したい

何度も書いてますが、言語組み込みの文字列とライブラリ提供の文字列では効率に天と地の差があります。C++みたいになるべく自然に使えるように努力している言語ですら、その差は到底埋められていません。ましてやAdaのUnbounded_Stringなんて(略)ですよ。

Delphiの文字列のスゴイところと、どうすればおんなじ風にできるかなー、ってのをダラダラやってた話です。あ、ここでいうDelphiの文字列というのは2007以前のAnsiStringのことです。2009以降については正直静的言語なのにコードページを実行時に持つ必要は無いと……どうでもいい。

実はD言語の文字列のほうがもっとスゴイのですが、あのスゴさはGC前提なので省略。

Delphi2〜Delphi2007のAnsiStringの構造

「参照カウンタ、長さ、文字列本体、(C互換用のゼロ終端←以後省略)」というメモリブロックへの「ポインタ」です。

まあこの構造自体はstd::stringでも同じでしょう。0xでは参照カウンタでの共有は許されなくなったんでしたっけ?

で、早速Adaには難点が。Adaでは(C++で言う)デストラクタを実現するためには、Ada.Finalization.Controlledを継承しなければいけないのですが、そうすると当然VMTが必要になるわけです。つまりポインタ2つの組になってしまうわけです。若干メモリの無駄

DelphiC++Ada
×

レジスタに入る

AnsiStringの実体はポインタ1つだけです。ということはレジスタに入ります。

std::string(C++03以前)も、実体はポインタ1つだけにできますが、レジスタに入りません。メンバ関数にthis(ポインタを1個だけ持つクラスへの更にポインタ)を渡さないといけないからですね。*1

もちろん上記のようにAdaでは最低でもポインタ2つ必要になりますので、レジスタには入りません。

DelphiC++Ada
××

文字列定数

AnsiStringの定数は、静的に確保されてます。参照カウンタには-1が入ってます。コンパイラ最初っから文字列の構造を把握してるからこそですね。

一方、std::stringもUnbounded_Stringも、コンストラクタ/To_Unbounded_Stringに定数文字列を渡されても、動的にメモリを確保して中身をコピーする必要があります。C/C++もAdaも文字列定数は単なる文字型の配列であり、参照カウンタも長さデータも持ってないからです。

そのため、ちょっと構造を変えましょう。

「参照カウンタ、長さ、文字列本体」→「参照カウンタ、長さ、文字列本体へのポインタ、(文字列本体)」

動的に確保する時は、「文字列本体」まで一緒に確保して、「文字列本体へのポインタ」メンバには「文字列本体」(要するにすぐ次のアドレス)を入れます。

静的に確保する時は、「文字列本体」は確保せずに、「文字列本体へのポインタ」メンバには実定数へのポインタをそのまま持たせます。

……実はこれだけだとダメです。

仮に引数の型をchar const *やaccess constant Stringにしたとしても、ローカル変数(定数)へのポインタを渡されたりすると、そのまま使うわけにいかないですよね。呼び出し元の関数を抜けると消えちゃいますから。

というわけで安全に文字列定数を作るためには、引数で渡された定数が本当に定数であることの保証が必要になります。D言語ならimmutableって便利なものがあるのですが、C++やAdaにはありません。

ただAdaのaccess型(ポインタ)はスコープに紐付けられた型ですので、ライブラリレベル(一番外)のaccess型を使えば、関数を抜けるなどで消えたりはしないことだけは保証できます。それでも、Adaのaccess constantはC++のconst *と同じで、実際に指しているものは変数かもしれません。中身が書き換わる恐れだけは無くせません。

DelphiC++Ada
××

引数渡し

AnsiStringは参照カウンタで管理されていますが、引数渡しの時は参照カウンタが増減されません。

実引数は関数呼び出しよりも寿命が長いことが確実だからです。

C++やAdaでこれを避けるには参照渡しにするしかなくて、そうするとポインタのポインタになってしまって、無意味な逆参照が1段入ってしまいます。引数として渡ってくるわけですからどんなにコンパイラが賢くてもひとつの関数内だけの最適化では取り除けません。LTOなら話は別。

まあAdaは特に、継承を使っている型は明示しなくても問答無用で参照渡しになってしまうわけですが。

DelphiC++Ada
××

世の中にはStringPieceなんかもありますが、折角の参照カウンタが活用されないため、あんまり意味無いかなあ。(リンク先の例だと中でCopyToStringするのも呼び出し元で一時的なstd::stringを作って中では参照カウンタを増やすだけってのも大して変わらないはず?out->append(dir);をout->assign(dir);に変えたら……と思って試してるのですが……続きは↓↓)

返値

返値も今までの話と似たようなものです。

AnsiStringはレジスタで返せて、その際参照カウントも増減しません。

std::stringはレジスタでは返せずに(暗黙の引数が必要になる)、コピーコンストラクタと一時変数のデストラクタも走ります。(0xならムーブコンストラクタと一時変数のデストラクタ)

Unbounded_Stringもレジスタでは返せずに(暗黙の略)、やっぱりAssignと一時変数のFinalizeが走ります。

もちろん定数を返すとわかっているなら参照返しにすればよいのですが、std::stringやUnbounded_Stringは上記のように定数であっても作成時点で中身全部コピーしたりしますので参照返しにして参照カウンタの操作を省略できたやったー、なんてやっても虚しいだけです。最終的に単なるポインタのレジスタ間コピーだけになるAnsiStringだからこそ活きる最適化ですよね。

DelphiC++Ada
××

連結

文字列を一気に3つ連結したりする時も、AnsiStringならコンパイラが知ってますからまとめて連結してくれたりします。(ランタイムには_LStrCat3とかある)

std::stringやUnbounded_Stringの連結は、演算子オーバーロードで実現されいるわけですが、「A & B & Cを一括で処理するオーバーロード」は定義できませんので、ちまちま連結していくしかないです。

ただ少しだけあがくことは出来て、「A & B」の時点で領域を多めにとっておいて、「& C」がそこに入るなら再アロケート無し、みたいな頑張り方はできます。もちろん「& C」されなれば無駄な領域ですのでふつーの発想だとやらないと思います。後はRopeにするぐらいかなあ。

DelphiC++Ada
××

というわけで結論

Unbounded_Stringをいろいろ弄ってたんですがあまり改善できそうにないです。

要は失敗談でした。

[][] 4.7がStage 3に入ったので試してみた

  • 2012対応状況
    • use all type → 「変数 := 式;」の形の式の部分でのみOK。
    • Implicit_Dereference → 関数呼び出しの返値でのみOK。
    • range-based for(違) → OK、ありえんぐらい酷いコードが出てくるけど動く。Ada.Iterator_Interfacesもちゃんとある
    • operator () (違) → OK、Constant_Referenceが呼ばれないような気もするけど。
    • 後は4.6のときと同じ。
  • その他気になる改善
    • protected型がちゃんとread-write lockしてくれるようになってます
    • Controlled型がリンクリストを作らなくなってます。*2
    • Unbounded_Stringに参照カウンタの実装も追加されたみたいです。*3でもデフォルトでは無効っぽい。

[][] 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では……。

*1:ただしC++Builderには__declspec(delphireturn)なるものがありましてレジスタに入れることができます。

*2:上では余計なデータはVMTだけみたいに書いてますが、実はgcc 4.6までは前後へのリンクも持ってました。

*3:上ではあたかもUnbounded_Stringが参照カウンタで実装されてるように書いてますが、gcc 4.6までは毎回コピーされてました。

2011-11-10

RSSアンテナ作りました

http://panathenaia.halfmoon.jp/birdeyes/

やっぱり何番煎じかわからないのですが……。

愛用させていただいていたI knowが終了してしまって困ったことは、「複数のRSSをまとめた結果をRSSとして再出力できるWeb上のRSSリーダーがない」ということでした。(ダッシュボード上のRSSリーダーで更新チェックしてます)

で、Yahoo Pipes存在を教えていただいて、しばらくそれを使っていました。こいつはGUIプログラミングでRSSを加工できるかなり楽しいツールなのですが、ふつーのRSSリーダーのようにサイトをひとつ追加しようと思えば、Fetch Feedを配置してUnionにつないで……と、まあ、めんどいわけです。そのせいですっかり購読しているサイトが少なくなってしまいました。

次に、無いなら自分で設置しよう、ということでCGIアンテナを探したわけです。その中ではRNAが私の要件を満たしてるっぽいです。

一応I knowでできてRNAでできないことはありまして、RNAはサイトごとに、最新記事だけを表示するか、各記事をばらして表示するかの設定ができません。各サイトの最新記事だけをまとめたRSS、各サイトの各記事を全部含めたRSSは作れます。その設定を混ぜることができません。I knowではできたんですよね。

例えば個人のブログサイトなんかは、更新されていることがわかれば充分ですので最新記事だけでよくて、むしろ過去の記事は混ざってほしくないわけです。

逆に、ニュースサイトなんかは、タイトルを見て開くかどうかを決めますので、全タイトル出てきて欲しくて、ブログとは逆に出元のニュースサイトがどこかは意識しないわけで、バラバラに時系列順に並んで欲しいわけです。

というわけでその機能付きの俺アンテナです。

あとI knowでできたことと言えば、RSSを公開していないサイトもdiff取ってRSSに載せてくれたのですが、はてなアンテナのRSSを取り込めば実現できますので実装していません。負荷ははてなに負わせる作戦。

あとインポート/エクスポート形式は、ふつーOPMLと思うのですが、たまたまI knowのデータをLIRSでしか保存してなかったのでLIRSのみ対応してます。

続きを読む

 | 
カレンダー
2004 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2013 | 01 | 02 | 03 |
Connection: close